Jeswin Jacob Jeswin Jacob - 1 month ago 10
C++ Question

What is wrong with my implementation of quicksort?

The program below is for sorting a list using quicksort C++.The code typed below has compiled successfully in code::blocks and in http://cpp.sh/, but unfortunately it hangs after entering in the elements,any help will be appreciated..

#include <iostream>
#include<vector>
using namespace std;

void print(vector<int> v)
{
cout<<"The sorted list is:"<<endl;
for(int i=0;i<(int)v.size();i++)
cout<<v[i]<<' ';
}
void swap(vector<int> v,int left,int right)
{
int temp=v[left];
v[left]=v[right];
v[right]=temp;
}

void quicksort(vector<int> v,int left_index,int right_index)
{
if(left_index>=right_index)
return;
int pivot=(right_index+left_index)/2;

int left=left_index;
int right=right_index;
while(left<=right)
{
while(v[left]<v[pivot])
left++;
while(v[right]>v[pivot])
right--;
if(left<=right)
{
swap(v,left,right);
left++;right--;
}
}
quicksort(v,left_index,right);
quicksort(v,left,right_index);
print(v);
}

int main()
{
int no;
vector<int> v;
cout << "Please enter the elements in your list" << endl;
cout << "Enter 0 to exit..."<<endl;
while(cin >> no)
{
if(no==0)
break;
v.push_back(no);
}
quicksort(v,0,v.size()-1);
return 0;
}

ee2 ee2
Answer
  1. Passing by reference is must as others have pointed out.
  2. Keep pivot constant during a partition. pivot = v[pivot] ensures that.
  3. outer loop bounds changed to left<=right from left<right.

The running code.

#include <iostream>
#include<vector>
using namespace std;

void print(const vector<int> &v)
{
    cout<<"The sorted list is:"<<endl;
    for(int i=0;i<(int)v.size();i++)
        cout<<v[i]<<' ';
    cout<<endl;
}
void swap(vector<int> &v,int left,int right)
{
    int temp=v[left];
    v[left]=v[right];
    v[right]=temp;
}

void quicksort(vector<int> &v,int left_index,int right_index)
{
    if(left_index>=right_index)
        return;
    int pivot=(right_index+left_index)/2;

    pivot = v[pivot];
    int left=left_index;
    int right=right_index;
    while(left<right)
    {
        while(v[left]<=pivot)
            left++;
        while(v[right]>pivot)
            right--;
        if(left<right){
            swap(v,left,right);
            left++;
            right--;
        }
    }
    quicksort(v,left_index,right);
    quicksort(v,left,right_index);
    print(v);
}

int main()
{
    int no;
    vector<int> v;
    cout << "Please enter the elements in your list" << endl;
    cout << "Enter 0 to exit..."<<endl;
    while(cin >> no)
    {
        if(no==0)
            break;
        v.push_back(no);
    }
    quicksort(v,0,v.size()-1);
    return 0;
}
Comments