javaalgorithmdata-structuresinsertquicksort

Why is my quicksort and insertion sort hybrid algorithm not working properly?



public class QuicksortFixedPivotInsertion implements IntSorter{
    InsertionSort insert = new InsertionSort();

    public int partition(int [] array, int first, int last){
        int middle = (first+last)/2;   
        swap(array, middle, last);        
        int pivot = array[last];
        int i = first-1;

        for (int j = first; j < last; j++){
            if (array[j]<pivot){
                i++;
                swap(array, i, j);               
    
            }
        } 
        swap(array, i+1, last);
        return i+1;
    }

    private void quickSort(int [] array, int first, int last){
     if(first < last){
        if ((last - first) < 10){
            insert.insertionSort(array, first, last);
        }
        else {
            int pivot = partition(array, first, last);
            quickSort(array, first, pivot - 1);
            quickSort(array, pivot + 1, last);
        }
     }
    }

    public void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

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

Here is the insertion method that is used for this

public class InsertionSort {

    public void insertionSort(int [] arr, int first, int last){
        for(int i = first + 1; i<last ; i++){
            int temp;
            int j = i;
            while(j > first && arr[j-1] > arr[j]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;

            }
        } 
    }

    public void sort(int[] v){
        insertionSort(v, 0, v.length);

    }

So the problem is that it doesn't work properly, as in when I try it with array with different sizes and different types of data (sorted array, shuffled array, random) it doesn't always work. By it doesn't work, I mean that it doesn't sort the array correctly. For example it doesn't sort shuffled or random arrays. Here is an example:

int[] a ={1,13,53,3,646,75,4,4646,332,2,124,3563,242,234,35,2,1};

This is the sorted version that gets printed:

[1, 1, 2, 2, 3, 4, 13, 35, 75, 124, 234, 242, 53, 332, 3563, 4646, 646]

Can someone help me solve this issue. I have checked that my insertion method and quicksort algorithm (partition method) works perfectly fine so the issue has to be somewhere in the quicksort method. Btw I have seen some similar posts on stack overflow and none of them worked in my case. One of the tips I tried there worked better but it was not consistent. As in when it comes to even & odd arrays, sometimes it works and sometimes it doesn't when using random data.

Thanks in advance


Solution

  • This one's a classic: Off-by-one error. Let's have a look at your two sorter classes:

    public class QuicksortFixedPivotInsertion implements IntSorter{
        /* ... */
        private void quickSort(int [] array, int first, int last){
            /* ... */
        }
      
        public void sort(int [] v){
            quickSort(v, 0, v.length - 1);
        }
    }
    
    public class InsertionSort {
    
        public void insertionSort(int [] arr, int first, int last){
            /* ... */
        }
    
        public void sort(int[] v){
            insertionSort(v, 0, v.length);
        }
    }
    

    See the difference? That -1? That's not where the error is, but that is giving us a hint, at what is wrong here: Your last parameter means two different things! In the QuickSort case, it's the index of the last element to sort, in the InsertionSort case, it's one past the last element to sort.

    And now look what happens when QuickSort calls InsertionSort:

                insert.insertionSort(array, first, last);
    

    You need to translate from one convention to the other, so that last parameter needs to be last+1.