problem with quicksort

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Helldrake
Posts: 18
Joined: Fri Mar 26, 2010 4:20 am UTC

problem with quicksort

Postby Helldrake » Tue Jul 12, 2011 6:54 am UTC

i am using this C++ quicksort code that i got from some webpage:

Code: Select all

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

int Partition(int low,int high,int arr[]);
void Quick_sort(int low,int high,int arr[]);

int main(){
using namespace std;
int *a,n,low,high,i;

cout<<"/**************************Quick Sort AlgorithmImplementation*****************/";
cout<<"Enter number of elements:";
cin>>n;

a=new int[n];
/* cout<<"enter the elements:
";
for(i=0;i<n;i++)
cin>>a;*/
for(i=0;i<n;i++)
a[i]=rand()%100;
cout<<"Initial Order of elements";
 for(i=0;i<n;i++)
  cout<<a[i]<<"   ";
cout<<"";

high=n-1;
low=0;
Quick_sort(low,high,a);
cout<<"Final Array After Sorting:";

  for(i=0;i<n;i++)
  cout<<a[i]<<"   ";

getch();
return 0;
}

/*Function for partitioning the array*/

int Partition(int low,int high,int arr[])
{ int i,high_vac,low_vac,pivot;
   pivot=arr[low];
   while(high>low)
{ high_vac=arr[high];

  while(pivot<high_vac)
  {
    if(high<=low) break;
    high--;
    high_vac=arr[high];
  }

  arr[low]=high_vac;
  low_vac=arr[low];
  while(pivot>low_vac)
  {
    if(high<=low) break;
    low++;
    low_vac=arr[low];
  }
  arr[high]=low_vac;
}
  arr[low]=pivot;
   return low;
}

void Quick_sort(int low,int high,int arr[])
{
  int Piv_index,i;
  if(low<high)
  {
   Piv_index=Partition(low,high,arr);
   Quick_sort(low,Piv_index-1,arr);
   Quick_sort(Piv_index+1,high,arr);
  }
}


First i tried it on a really slow computer, and it could only function up until 22 numbers to sort. More than 22 and it would get 100% stuck.

i thought "Hey, this computer is bs. I'll try a better one." But i did on a really powerful one and it only works with up to 18 numbers!

So, my question is...is there a problem with the code? I've checked and it seems to be standard Quicksort. If not, what is the problem with the computers?.

For reference, in the crappy computer i used a C++ compiler which i have no idea the name. Looks oldschool, with the blue screen and yellow letters.
In the second computer i used Dev C++.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: problem with quicksort

Postby jaap » Tue Jul 12, 2011 8:51 am UTC

I think the problem is that as written it cannot deal with repeated numbers. The Partition routine can end in an infinite loop trying to partition a section of an array that contains only one value. I think that if you change the first of those while conditions to pivot<=high_vac then it will work with repeats too.

Helldrake
Posts: 18
Joined: Fri Mar 26, 2010 4:20 am UTC

Re: problem with quicksort

Postby Helldrake » Tue Jul 12, 2011 12:13 pm UTC

jaap wrote:I think the problem is that as written it cannot deal with repeated numbers. The Partition routine can end in an infinite loop trying to partition a section of an array that contains only one value. I think that if you change the first of those while conditions to pivot<=high_vac then it will work with repeats too.


I think i love you.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 9 guests