Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 274

# Quick Sort Help.

I wrote the following code for Quick Sort. It doesn't work as its supposed to and it goes into an infinite loop. Can someone point out where Im going wrong?

#include<iostream.h>
#include<conio.h>

int array[10] = {9,8,7,6,5,4,3,2,1,0};
int temp[10] = {0,0,0,0,0,0,0,0,0,0};

void quicksort(int start, int end)
{
cout<<"Set to Sort:\n";
for(int i=start;i<=end;i++)
cout<<array[i]<<" ";

cout<<endl;

int middle = (end-start)/2;
int pivot = array[middle];
int pos=start;
int size = (end-start)+1;

for(int i=start; i<=end; i++)
if(array[i] < pivot)
temp[pos++] = array[i];

temp[pos++] = pivot;

for(int i=start; i<=end; i++)
if(array[i] > pivot)
temp[pos++] = array[i];

for(int i=start;i<=end;i++)
array[i]=temp[i];

if (size == 1 || size < 1)
{
cout<<"Sorting Set Ends!\n\n";
return;
}
else
{
cout<<"\nSorting Results and Attributes\n";
cout<<"Size:"<<size<<"   Middle:"<<middle<<"   Pivot:"<<pivot<<endl;
for(int i=start; i<=end; i++)
cout<<array[i]<<" ";
cout<<"\n\n-----------------------------------------\n\n";
getch();cout<<endl;

quicksort(start, middle);
cout<<"\n\n----------------drill ends---------------\n\n";
quicksort(middle+2, end);
}
}

void main()
{
int start = 0;
int end = 9;

quicksort(start,end);

cout<<"\n\n\nSorting End Results:\n";
for(int i=start; i<=end; i++)
cout<<array[i]<<" ";

getch();
}
0
lexxwern
1 Solution

Commented:
Here is the code for Quick Sort.

void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}

void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}

You can find the Algorithm Analysis Here
http://linux.wku.edu/~lamonml/algor/sort/quick.html

Good Luck
0

Commented:
Here is a fixed version of your code, your problems seem to be in working out the 'middle' value correctly and in the selection of the pivot point.

void quicksort(int start, int end)
{
cout<<"Set to Sort:\n";
for(int i=start;i<=end;i++)
cout<<array[i]<<" ";

cout<<endl;

int middle = (end-start)/2 + start;
int pivot = array[middle];
int pos=start;
int size = (end-start)+1;

for(int i=start; i<=end; i++)
{
if(array[i] < pivot)
temp[pos++] = array[i];
}

int pivotPoint = pos;
temp[pos++] = pivot;

for(int i=start; i<=end; i++)
{
if(array[i] > pivot)
temp[pos++] = array[i];
}

for(int i=start;i<=end;i++)
array[i]=temp[i];

if (size == 1 || size < 1)
{
cout<<"Sorting Set Ends!\n\n";
return;
}
else
{
cout<<"\nSorting Results and Attributes\n";
cout<<"Size:"<<size<<"   Middle:"<<middle<<"   Pivot:"<<pivot<<endl;
for(int i=start; i<=end; i++)
cout<<array[i]<<" ";
cout<<"\n\n-----------------------------------------\n\n";
getch();cout<<endl;

quicksort(start, pivotPoint-1);
cout<<"\n\n----------------drill ends---------------\n\n";
quicksort(pivotPoint+1, end);
}
}
0

Commented:
Why don't you just use qsort() in stdlib.h?
0

Author Commented:
roshmon, thanks but i wanted to write my own code.

jasonclarke, that worked perfectly ... thanks for pointing "int middle = (end-start)/2 + start;" out ... points goto you.

arjkane, as mentioned earlier i had to write my own code ...

once again thankyou everybody!
0

Commented:
i tried that program and it works fine, thats cool.
0

## Featured Post

Tackle projects and never again get stuck behind a technical roadblock.