CODEWITHSUNDEEP
sortingscopeimplementationquicksort
Veneet Reddy
Veneet Reddy

Reputation: 2907

Why is my quick sort implementation not working?

Here's my code:

#include<iostream>
using namespace std;

//Array that needs to be sorted
int a[]={234,45,234,65,234,65,234,567,234,123,11,23,43,45,6,7,7,4,233,4,6,4,3,11,23,556,7,1,2,3,4,5,6,7,};

//Calculate the size of the array
int n=sizeof(a)/sizeof(a[0]); 

//Swap utility function to swap two numbers
void swap(int a,int b)
{
      int t=a;
      a=b;
      b=t;
}

//Partion the array into two according to the pivot,i.e a[r]
int partion(int p,int r)
{
      int x=a[r],i=p-1;
      for(int j=p;j<r;j++)
            if(a[j]<=x)
            {
                  i++;
                  swap(a[i],a[j]);
            }
      swap(a[r],a[i+1]);
      return i+1;
}

//Recursive method to sort the array
void quick_sort(int p,int r)
{
      if(p<r)
      {
            int q=partion(p,r);
            quick_sort(p,q-1);
            quick_sort(q+1,r);
      }
}

int main()
{
      cout<<"\nOriginal array:\n";
      for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
      cout<<endl;
      quick_sort(0,n-1);
      cout<<"Sorted array:\n";
      for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
      cout<<endl;
}

It outputs:

Original array:
234 45 234 65 234 65 234 567 234 123 11 23 43 45 6 7 7 4 233 4 6 4 3 11 23 556 7 1 2 3 4 5 6 7 
Sorted array:
234 45 234 65 234 65 234 567 234 123 11 23 43 45 6 7 7 4 233 4 6 4 3 11 23 556 7 1 2 3 4 5 6 7

I'm not sure what the problem is. Is it an quicksort implementation mistake or a mistake in the scope of the array 'a[]' or something else.

The array 'a[]' is a global variable, so I presume partition and quicksort to operate on it. It seems that the array remains unchanged.

Upvotes: 1

Views: 48

Answers (1)

JHobern
JHobern

Reputation: 864

Have a look at your swap function:

void swap(int a,int b)
{
      int t=a;
      a=b;
      b=t;
}

It is changing the values of the copied variables. You want to pass a and b in by reference so their value gets changed instead.

void swap(int &a,int &b)
{
      int t=a;
      a=b;
      b=t;
}

Upvotes: 1

Related Questions