Unknown QuickSort Error

[aquamongoose]

Hi everybody, I was writing a quicksort algorithm to better understand it, but for some reason it will output a non-sorted array. I have searched the internet and found some sample programs, but mine seems to be doing the same thing, just with the wrong results. Here is the code.
[cpp]
#include <iostream>
using namespace std;

void swap(int&,int&);
void quickSort(int*,int,int);
int partition(int*,int,int);

int main()
{
int num;
cout << "How many numbers are there to be sorted?\n";
cin >> num;
cin.ignore();
int* number = new int[num];
for(int i=0; i<num; i++)
{
cout << "Enter number " << i+1 << endl;
cin >> number[i];
cin.ignore();
}
quickSort(number,0,num-1);
cout << "The sorted array is: " << endl;
for(int i=0; i<num; i++)
cout << number[i] << endl;
delete[] number;
return 0;
}

void quickSort(int* data, int first, int last)
{
if(first >= last) return;
int mid = partition(data,first,last);
quickSort(data,first,mid);
quickSort(data,mid+1,last);
}

int partition(int* data, int first, int last)
{
int pivot = ((last + first) / 2), i = first, j = last;
while(i < j)
{
while(i < j && data[i] < data[pivot]) i++;
while(j > i && data[j] >= data[pivot]) j--;
if(i < j) swap(data[i],data[j]);
i++;
j--;
}
return pivot;
}

void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
[/cpp]
Please help me in finding the error in this code. Thanks in advance.

[jumper007]

O.O

use the code tag -.-

#include <iostream>
using namespace std;

void swap(int&,int&);
void quickSort(int*,int,int);
int partition(int*,int,int);

int main()
{
     int num;
     cout << "How many numbers are there to be sorted?\n";
     cin >> num;
     cin.ignore();
     int* number = new int[num];
     for(int i=0; i<num; i++)
     {
          cout << "Enter number " << i+1 << endl;
          cin >> number[i];
          cin.ignore();
     }
     quickSort(number,0,num-1);
     cout << "The sorted array is: " << endl;
     for(int i=0; i<num; i++)

// HERE ! where are your { } ??

          cout << number[i] << endl;
          delete[] number;

// HERE ! where are your { } ??

     return 0;
}

void quickSort(int* data, int first, int last)
{
     if(first >= last) return;
     int mid = partition(data,first,last);
     quickSort(data,first,mid);
     quickSort(data,mid+1,last);
}

int partition(int* data, int first, int last)
{
     int pivot = ((last + first) / 2), i = first, j = last;
     while(i < j)
     {
          while(i < j && data[i] < data[pivot]) i++;
          while(j > i && data[j] >= data[pivot]) j--;
          if(i < j) swap(data[i],data[j]);
          i++;
          j--;
     }
     return pivot;
}

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

your problem is on line 25 and 30

[savavampir]

Just to see better, use 'code' instead 'cpp':

#include <iostream>
using namespace std;

void swap(int&,int&);
void quickSort(int*,int,int);
int partition(int*,int,int);

int main()
{
	int num;
	cout << "How many numbers are there to be sorted?\n";
	cin >> num;
	cin.ignore();
	int* number = new int[num];
	for(int i=0; i<num; i++)
	{
		cout << "Enter number " << i+1 << endl;
		cin >> number[i];
		cin.ignore();
	}
	quickSort(number,0,num-1);
	cout << "The sorted array is: " << endl;
	for(int i=0; i<num; i++)
		cout << number[i] << endl;
	delete[] number;
	return 0;
}

void quickSort(int* data, int first, int last)
{
	if(first >= last) return;
	int mid = partition(data,first,last);
	quickSort(data,first,mid);
	quickSort(data,mid+1,last);
}

int partition(int* data, int first, int last)
{
	int pivot = ((last + first) / 2), i = first, j = last;
	while(i < j)
	{
		while(i < j && data[i] < data[pivot]) i++;
		while(j > i && data[j] >= data[pivot]) j--;
		if(i < j) swap(data[i],data[j]);
		i++;
		j--;
	}
	return pivot;
}

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

[jumper007]

PROBLEM ON LINE 25 and 30 (in this code)
and would be easier if you tell us what the problem is ( what does the compiler say ? )

#include <iostream>
using namespace std;

void swap(int&,int&);
void quickSort(int*,int,int);
int partition(int*,int,int);

int main()
{
     int num;
     cout << "How many numbers are there to be sorted?\n";
     cin >> num;
     cin.ignore();
     int* number = new int[num];
     for(int i=0; i<num; i++)
     {
          cout << "Enter number " << i+1 << endl;
          cin >> number[i];
          cin.ignore();
     }
     quickSort(number,0,num-1);
     cout << "The sorted array is: " << endl;
     for(int i=0; i<num; i++)

// HERE ! where are your { } ??

          cout << number[i] << endl;
          delete[] number;

// HERE ! where are your { } ??

     return 0;
}

void quickSort(int* data, int first, int last)
{
     if(first >= last) return;
     int mid = partition(data,first,last);
     quickSort(data,first,mid);
     quickSort(data,mid+1,last);
}

int partition(int* data, int first, int last)
{
     int pivot = ((last + first) / 2), i = first, j = last;
     while(i < j)
     {
          while(i < j && data[i] < data[pivot]) i++;
          while(j > i && data[j] >= data[pivot]) j--;
          if(i < j) swap(data[i],data[j]);
          i++;
          j--;
     }
     return pivot;
}

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

your problem is on line 25 and 30

[savavampir]

I just test it and it works fine:
input: 4 numbers (20, 18, 21, 17)
output: 17, 18, 20, 21

EDIT: Sorry, just tried other inputs and it fails.

[aquamongoose]

Sorry, on other forums the cpp tag works too. And jumper007, there is no problem on line 25 and 30. That's just outputting the array. You say I don't have braces (I think?) but I don't need them since I am only looping over the one cout statement. The way you wrote it, it would include the delete statement in the loop, which would be wrong. The compiler gives no error, because the problem is not in a syntax error, but some algorithmic problem in the quickSort or partition functions.

[savavampir]

Here is some link: http://www.algolist.net/Algorithms/Sorting/Quicksort

[NallePuh1983]

sorry, was complete rubbish

[aquamongoose]

So, the only change you're making is to swap i and j if either of them is equal to pivot, but that doesn't make sense to me. Please explain why if you don't mind. Consequently, it doesn't help.

[ne555]

The idea of partition is that you will end with an array where the elements to the left of the pivot are lesser than it, and the ones to the right are greater or equal than the pivot. [ lesser | pivot | greater or equal ]
However you are doing

int pivot = (first+last)/2;
//...
return pivot;

There is no guarantee that the pivot will end in the middle of the array (is desirable for complexity reasons, but you can't obtain that easily)

Also

          while(i < j && data[i] < data[pivot]) i++;
          while(j > i && data[j] >= data[pivot]) j--;

What will happen when i==pivot ?
http://en.wikipedia.org/wiki/Quicksort#In-place_version
That is why the algorithm put the pivot element to the end of the array when it starts, and then swaps it to the right position at the end.

[webJose]

I see that you dynamically retrieve the value of the pivot by using data[pivot], but the provided link by savavampir shows it is sampled once and then unaltered even after swapping. This must be incurring in misbehavior as well.