What is wrong with this snippet for quick sort?

Question

#include <iostream>
using namespace std;
int f(int a[],int low,int high){
    int pivot,i,j,t;
    if(low<high){
        pivot=a[low];
        i=low+1;
        j=high;
        while(i<pivot && j>pivot){
            while(a[i]<=pivot){
                i++;
            }
            while(a[j]>pivot){
                j--;
            }
        }
        if(i<j){
        t=a[i];
        a[i]=a[j];
        a[j]=t;

    a[low]=a[j];
    a[j]=pivot;
    f(a,low,j-1);
    f(a,j+1,high);  
    }
    } 
}

int main(){
    int a[100],i,n,low,high;
    cout<<"Enter size of array"<<endl;
    cin>>n;
    cout<<"Enter elements in array"<<endl;
    for(i=0;i<n;i++){
        cin>>a[i];
    }low=0;
    high=n-1;
    f(a,low,high);
    cout<<"Sorted array:"<<endl;
    for(i=0;i<n;i++){
        cout<<a[i]<<" ";
    }

  return 0;
}

What correction do i need here?

I followed the algorithm for quicksort and wrote this code. However it fails to print the correct sorted array. I checked thoroughly all the iterations and loops but can't found a mistake. Please help.

Answer 1

There are multiple logical bugs in the shown code.

        pivot=a[low];
        i=low+1;
        j=high;

As we've observed here, pivot is a value in the array, while i and j are indexes.

while(i<pivot && j>pivot){

Here, this ends up comparing values in the array with the indexes of values in the array. This makes no logical sense. Values in the array bear no logical relationship to indices of the same array, in any sorting algorithm.

In a typical quicksort implementation, this is probably intended to be just i<j, but that's also will be wrong here, for the reasons that will become obvious. Let's assume that's what you intended, and proceed further:

            while(a[i]<=pivot){
                i++;
            }

This can potentially run off the end of the array, resulting in undefined behavior. If, for the sake of argument, the array had two values, both zero. low is 0, high is 1, therefore, after initializing: both i and j will be 1, and pivot will be 0.

Since a[1] <= 0 this while loop iterates once, and on the next iteration a[2] becomes undefined behavior (there is no a[2], of course).

Other edge conditions will also result in the 2nd while loop producing undefined behavior, as well, but that's an excersize that can be left as a homework assignment.

I checked thoroughly all the iterations and loops but can't found a mistake.

The mistake is that the pivoting logic, the core of the quicksort algorithm, is logically flawed. There is no single error that can be fixed, here. Most of the shown logic is incorrect, and needs to be rewritten from scratch, very carefully, and closely following a working quicksort algorithm logic, step by step.