Can you guys help me? about Quick Sort Algorithm

[vienne]

I'm having a problem with my sorting algorithm.
before I made quick sort which used insertion sort, but I don't want to use this insertion sort. I want to use recursive algorithm.

Also, I want to get new idea, so If you know any quick sort algorithm, reply for me.Please~ :rolleyes:

[Narue]

I'm having a problem with my sorting algorithm. before I made quick sort which used insertion sort, but I don't want to use this insertion sort. I want to use recursive algorithm. Also, I want to get new idea, so If you know any quick sort algorithm, reply for me.Please~ :rolleyes:

Good quicksort implementations use insertion sort as the final step. Or do you mean you wrote an insertion sort algorithm and called it quicksort? :rolleyes: The basic recursive algorithm is simple:

void quicksort ( type a, int l, int r )
{
  int i;

  if ( r <= l )
    return;

  i = partition ( a, l, r );

  quicksort ( a, l, i - 1 );
  quicksort ( a, i + 1, r );
}

Because your post was appropriately vague, I'll do the same and not include the implementation of partition. ;)

[vienne]

hum..... I know that basic recursive algorithm, but i cannot make good quick sort algorithm.

this is my code. I'm having a problem with this code.
there are three pointer( pivot, left, right)

#include <stdio.h>


void spilt(int tab[],int,int*);
void quick(int tab[],int,int);
void swap(int*,int*);
void tab_prn(int tab[],int,char*);
main()
{
int tab[11]= {0,26,5,37,1,61,11,59,15,48,19};
tab_prn(tab,10,"source");
quick(tab,1,10);
tab_prn(tab,10,"result");
}

void quick(tab,p,q)
int tab[11],p,q;
{
int j=q+1;
if(p<=q) return;
spilt(tab,p,&j);
tab_prn(tab,10," step");
quick(tab,p,j-1);
quick(tab,j+1,q);

}

void spilt(tab,m,up);
int tab[],m,*up;
{
int low=m,b=tab[m];
while(1)
{
do low++; while(tab[low]
do --*up; while(tab[*up] >v);
if(low<*up) swap(tab+low,tab+*up);
else break;
}
tab[m]=tab[*up];
tab[*up]=v;
}

void swap(i,j)
int *i,*j;
{
int t;
t=*i;
*i=*j;
*j=t;
}
void tab_prn(tab,n,title)
int tab[11],n;
char *title;
{
int i;
printf("%7s",title);
for(i=2;i<=n;i++)
printf("%3d",tab[i]);
printf("\n");
}

Base on the pivot, I have to sort left side and right side.
The Left side is smaller than the pivot, and the right side is lagger than the pivot. I guess that you guys have more ease way.

[cscgal]

This program that I wrote should be of help to you: http://www.daniweb.com/techtalkforums/thread1689.html

[Narue]

>but i cannot make good quick sort algorithm
There are three immediate improvements to the basic algorithm. First, you want to come up with a partitioning scheme that finds a pivot point as close to the median as possible so that the recursive branching is balanced. Second, you want to avoid recursing for small sets but adding a cutoff when the partitions are small. Lastly, you can partition three or more ways and then work out an elegant handling of duplicate values.

The first improvement is usually made by either choosing a random pivot as cscgal did, or by choosing three values in the partition and using the median of those three as the pivot. You could use more than three, but that means extra work and extra time, just like calling a random number generator. Both are undesirable in an efficient sorting routine. The second improvement is usually made by setting a cutoff in the recursive path and then using insertion sort to finalize the routine. Because insertion sort is zippy on almost sorted files, this increases quicksort's speed.

The last improvement is complicated and I don't see it much, so unless large amounts of duplicate values are a problem for you, you can ignore it. :)

The most obvious problem with your code aside from the syntax errors in spilt is that you mix prototypes with old style function definitions. This is a huge no-no. Let K&R C die and use proper ISO C function definitions please. For help on the actual algorithm, start by throwing away that awful book you're using. The code rarely works without a great deal of tweaking. :rolleyes: The text is wonderful, but the code just sucks.

[vienne]

This program that I wrote should be of help to you: http://www.daniweb.com/techtalkforums/thread1689.html

Thank you Nanue and cscgal! I got idea! and this is the perfect program~

[shashankc]

check this out!!

Qcksort, quick sort [array]

#include <stdio.h>

#define MAXARRAY 10

void quicksort(int arr[], int low, int high);

int main(void) {
 int array[MAXARRAY] = {0};
 int i = 0;

 /* load some random values into the array */
 for(i = 0; i < MAXARRAY; i++)
  array[i] = rand() % 100; 

 /* print the original array */
 printf("Before quicksort: ");
 for(i = 0; i < MAXARRAY; i++) {
  printf(" %d ", array[i]); 
 }
 printf("\n");

 quicksort(array, 0, (MAXARRAY - 1));

 /* print the `quicksorted' array */
 printf("After  quicksort: ");
 for(i = 0; i < MAXARRAY; i++) {
  printf(" %d ", array[i]); 
 }
 printf("\n");

 return 0;
}

/* sort everything inbetween `low' <-> `high' */
void quicksort(int arr[], int low, int high) {
 int i = low;
 int j = high;
 int y = 0;
 /* compare value */
 int z = arr[(low + high) / 2];

 /* partition */
 do {
  /* find member above ... */
  while(arr[i] < z) i++;

  /* find element below ... */
  while(arr[j] > z) j--;

  if(i <= j) {
   /* swap two elements */
   y = arr[i];
   arr[i] = arr[j]; 
   arr[j] = y;
   i++; 
   j--;
  }
 } while(i <= j);

 /* recurse */
 if(low < j) 
  quicksort(arr, low, j);

 if(i < high) 
  quicksort(arr, i, high); 
}