Java Quick Sort

Question

I am implementing quicksort in Java with the following requirements:

Use recursion (in your quicksort implementation) down to a stopping case of a partition of size k or smaller. For these partitions, use an insertion sort to finish.

I'm confused as to how to implement this or even what it is asking. Here is what I have for the normal quicksort. How could I modify this to meet the requirements?

public static void quick_srt(int array[],int low, int n){
    int lo = low;
    int hi = n;
    if (lo >= n) {
      return;
    }

    int mid = array[(lo + hi) / 2];

    while (lo < hi) {
      while (lo<hi && array[lo] < mid) {
        lo++;
      }
      while (lo<hi && array[hi] > mid) {
        hi--;
      }

      if (lo < hi) {
        int T = array[lo];
        array[lo] = array[hi];
        array[hi] = T;
      }
    }

    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
    quick_srt(array, low, lo);
    quick_srt(array, lo == low ? lo+1 : lo, n);
}

Elliott Frisch · Accepted Answer · 2015-12-08 04:27:17Z

3

The partition size is hi - lo. So you could add something like,

int k = 7;
// ...
if (hi - lo < k) {
    insertion_srt(array, lo, hi);
    return;
}

before int mid. Implementing insertion_srt(int[], int, int) left as an exercise for the reader.

answered Dec 8, 2015 at 4:27

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user3498593 Over a year ago

So then after the mid variable there would be nothing since the insertion sort would take care of the sorting?

Elliott Frisch Over a year ago

The rest of the method would do nothing, because the condition of the partiion being smaller than k triggers the insertion sort (and then returns).

user3498593 Over a year ago

Oh. I got it. Because the insertion sort would take place then the rest would have nothing to sort essentially.

Collectives™ on Stack Overflow

Java Quick Sort

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related