Quick sort -- What am i doing wrong?

Gautam Prasad 0
Viewed 28

Trying to do Quick sort. logic -> maintaining two variables to place pivot element at correct index. Taking 1st element as pivot. int i for RHS of pivot and Int j for LHS, if they cross each other then j is correct index for pivot.

#include<iostream>
using namespace std;

int partition(int arr[], int low, int high){
        int pivot = arr[low];
        int i = low+1;
        int j = high;

        while (i<j)
        {
            while(arr[i]<=pivot) i++;
            while(arr[j]> pivot) j--;
            if(i<j) {
            swap(arr[i], arr[j]);
        }

        swap(arr[j], arr[low]);
        return j;
    
    }
    }

    void QuickSort(int arr[], int low , int high){
        if(low >= high ) return;
        if(high>low){
            int pivotindx = partition(arr,  low ,  high);
        QuickSort(arr,low, pivotindx-1);
        QuickSort( arr, pivotindx+1, high);
        }
    }

    void printquicksort(int arr[] , int n){
        cout << " Quick SORT IS HERE BROOOO "  << endl; 
        
        for (int i = 0; i < n; i++)
        {
            cout << " "  << arr[i] << " " ;
        }

    }



int main()
{
    int arr []={3,4,5,1};
    int n= sizeof (arr)/ sizeof (arr[0]);


    QuickSort(arr,0,n-1);
    printquicksort(arr,n);
    
    return 0;
}
quicksort sorting
1 Answers

Using i and j for LHS and RHS is type of Hoare partition scheme. The code has a potential issue when using low for the pivot, the while(arr[i]<=pivot) i++; may never encounter an element > pivot and scan past the end of the array. For Hoare partition scheme, the pivot and elements equal to the pivot can end up anywhere, and the partition index separate elements <= pivot and elements >= pivot, so the index needs to be included in one of the recursive calls. Example of a post-increment and post-decrement version of Hoare with the partition code included in QuickSort:

void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
    if(lo >= hi)
        return;
    p = a[lo + (hi-lo)/2];
    i = lo;
    j = hi;
    while (i <= j){
        while (a[i] < p)i++;
        while (a[j] > p)j--;
            if (i > j)
                break;
            t = a[i];        // swap 
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
    }
    QuickSort(a, lo, j);
    QuickSort(a, i, hi);
}

Example of a classic pre-increment and pre-decrement version of Hoare with the partition code included in QuickSort:

void QuickSort(int a[], int lo, int hi)
{
    if(lo >= hi)
        return;
    int p = a[lo+(hi-lo)/2];
    int i = lo-1;
    int j = hi+1;
    int t;
    while(1){
        while (a[++i] < p);
        while (a[--j] > p);
        if(i >= j)
            break;
        t = a[i];            // swap
        a[i] = a[j];
        a[j] = t;
    }
    i = j++;
    QuickSort(a, lo, i);
    QuickSort(a, j, hi);
}
rcgldr0
Related