Java - How to implement a hybrid QuickSort and Insertion sort method

Question

Trying to code a hybrid quickSort with insertion sort when quickSort when the size of the partition falls under a certain threshold (using 10 below). I can't seem to get it working. The array will always come back with a few numbers out of order.

Here is my partial code:

public static void quickSort(int[] list) {
quickSort(list, 0, list.length - 1);
}  

private static void quickSort(int[] list, int first, int last) { 
 int size = (last+1) - first;
 if (size <= 10){ // insertion sort if 10 or smaller
   insertionSort(list, first, size);
 }
 else // quicksort if large
 {
   int pivotIndex = partition(list, first, last);
   quickSort(list, first, pivotIndex - 1);
   quickSort(list, pivotIndex + 1, last);
 }
}

public static void insertionSort(int[] list, int first, int size) {
 for (int i = first+1; i < size; i++) {
   int currentElement = list[i];
   int k;
   for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
     list[k + 1] = list[k];
   }

   // Insert the current element into list[k+1]
   list[k + 1] = currentElement;
 }
}

Expected output: random array ordered in ascending order.

sample output contains errors: 9 18 34 36 53 61 87 89 117 115 109 120 129 154 163 136 131 164 175 193 206 182 259 243 181 165 216 261 274 276 281 320 338 341 322 322 379 372 382 392 397 419 401 402 479 508 512 494 518 558 578 588 606 660 657 665 617 674 698 728 683 692 684 685 737 738 741 745 753 777 799 816 824 791 807 823 762 761 825 845 833 854 860 934 886 933 880 864 879 915 939 970 948 972 952 953 945 968 977 995

Answer 1

The issue is when you call the insertion sort

 int size = (last+1) - first;
 if (size <= 10){ // insertion sort if 10 or smaller
   insertionSort(list, first, size);
 }

Lets say at some point first = 5 and last = 7 so then size = 2. You would end up calling insertionSort(list, 5, 2)

So then in your insertionSort() method your initial for loop will look like this:

for (int i = 5+1; i < 2; i++) {

when it should probably look like:

for (int i = 5+1; i < 7; i++) {

I didn't test it out but it looks like that is the issue.

Answer 2

Made it work by changing the following:

 private static void quickSort(int[] list, int first, int last) {

 int size = (last +1) - first;

 if (first < last){
     if (last < 11){ // insertion sort if 10 or smaller
        insertionSort(list, first, size);
     }
     else // quicksort if large
     {
     int pivotIndex = partition(list, first, last);
     quickSort(list, first, pivotIndex - 1);
     quickSort(list, pivotIndex + 1, last);
     }
 }    
}

Answer 3

I can't comment because I don't have 50 rep yet. I don't think your solution is going to work the way you think it will. You are going to end up running the insertion sort on only the first 10 elements.

Go back to your initial code and change your call to insertionSort(list, first, size); to: insertionSort(list, first, last);

Answer 4

Ok i made this work...

First change method quickSort:

private static void quickSort(int[] list, int first, int last) { 
        int size = (last+1) - first;
        if (first < last){
            if (size <= 10){
                insertionSort(list, first, last); //Changed this line
            }
            else{
                int pivotIndex = partition(list, first, last);
                quickSort(list, first, pivotIndex); //Changed this line just because i used the partition method from Hoare and not Lomuto
                quickSort(list, pivotIndex + 1, last);
            }
        }
    }

And then in method insertionSort:

public static void insertionSort(int[] list, int first, int last) {
        for (int i = first+1; i <= last; i++) { // Change i <= last 
            int currentElement = list[i];
            int j = i-1;
            while (j>=0 && list[j]>currentElement) {
                list[j+1] = list[j];
                j--;
            }
            list[j+1] = currentElement;
        }
    }

Hope will be the answer you wanted.