Quicksort issues

[vextes]

Hi, I'm new here, and I'm pretty new to c++ as well. I have been attempting to write a function for the quicksort algorithm, but for some reason that I haven't been able to figure out, what I have doesn't work at all. Here is what I have so far.

#include "Sorts.h"
#include <iostream>
#include <time.h>
using namespace std;
#include <cstdlib>

//picks a random pivot point
int Sorts::simple(double *a, int left, int right)
  {
	  srand(time(NULL));
	  int result = (rand() % (right-left)) + 1 + left;
	  return result;
  }

// takes the array to be sorted and its length
void Sorts::quick_sort(double *array, int length)
  {
	quicksort(array, 0, length-1);
  }

  void Sorts::quick(double *array, int left, int right)
  {
	  int length = (right-left+1);

	  if(length < 2) //if size is one or 0 array is already sorted
	  {
		  return;
	  }
	  int pivotIndex = simple(array, left, length-1);
	  int low = left;
	  int up = right;
	  double temp;

	  //saves the value of the pivot and moves the pivot to the far right of the array
	  double pivotVal = array[pivotIndex];
	  array[pivotIndex] = array[up];
	  array[up] = pivotVal;
	  pivotIndex = up;
	  up--;

	  //partitions the elements in the array
	  while(low < up)
	  {
		  while(array[low] < pivotVal)
		  {
			  low++;
		  }
		  while(array[up] > pivotVal)
		  {
			  up--;
		  }
		  if(pivotVal == array[low] && pivotVal == array[up])
		  {
			  low++;
		  }
		  else
		  {
			  temp = array[low];
			  array[low] = array[up];
			  array[up] = temp;
		  }
	  }

	  // swaps the pivot into its proper place in the array
	  temp = array[low];
	  array[low] = array[length-1];
	  array[length-1] = temp;

	  quick(array, left, low); //recursive call for the left side
	  quick(array, low+1, right);  //recursive call for the right side
  }

As far as I can tell everything should be sorting properly but when i print the final results in my main function, it doesnt turn out even remotely close to sorted. I would greatly appreciate any and all help. Thank you!

[w397090770]

Hi, in the line 69,
quick(array, left, low); //recursive call for the left side
should be
quick(array, left, low - 1); //recursive call for the left side . please try again.

[vextes]

Thanks, I made the change that you suggested, and it looks like it helped a little bit, but the array still comes out sorted incorrectly.

[w397090770]

Hi, I write the code in c, this is the random quick sort.

#include <stdio.h> 

#include <stdlib.h> 

int a[]={15,56,2,51,1,59,3};  // the array which hope to sort 

  

void Swap( int *a, int *b) {    //  Swap 

int temp; 

temp=*a;*a=*b;*b=temp; 

} 

  

int Random(int p,int r) {        // generate a random number

int result=p+rand()%(r-p+1); 

return result; 

} 

  

int Partition( int a[], int p, int r) { 

int i=p,j=r+1; int x=a[p]; 

// 将 <x 的元素交换到左边区域 

// 将 >x 的元素交换到右边区域 

while ( true ) { 

while (a[++i]<x&&i<=r); while (a[--j]>x&&j>=p); 

if (i>=j) break ; 

Swap (&a[i],&a[j]); 

} 

a[p]=a[j]; a[j]=x; return j; 

} 

  

int RandomizedPartition( int a[], int p, int r) { 

int i=Random(p,r); 

Swap (&a[i],&a[p]); 

return Partition(a,p,r); 

} 

  

void RandomizedQuickSort( int a[], int p, int r) { 

if (p<r) { 

int q= RandomizedPartition (a,p,r); 

RandomizedQuickSort (a,p,q-1); RandomizedQuickSort(a,q+1,r); 

} 

} 

  

void main() { 

for ( int i=0;i<7;i++)  printf("%d ",a[i]); 

printf ("\n"); 

RandomizedQuickSort (a,0,6); 

for (i=0;i<7;i++)  printf("%d ",a[i]); 

printf ("\n"); 

}