DaniWeb Forum Index > Software Development > C

C RSS

Can you guys help me? about Quick Sort Algorithm

•

Join Date: Jul 2004

Posts: 6

Reputation: vienne is an unknown quantity at this point

Solved Threads: 0

vienne

Offline

Newbie Poster

Can you guys help me? about Quick Sort Algorithm

Oct 1st, 2004

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:

•

Join Date: Sep 2004

Posts: 7,596

Reputation: Narue has a reputation beyond repute

Solved Threads: 712

Narue

Offline

Code Goddess

Re: Can you guys help me? about Quick Sort Algorithm

Oct 1st, 2004

•

Originally Posted by 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:

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:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
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 );
}
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.

I'm here to prove you wrong.

•

Join Date: Jul 2004

Posts: 6

Reputation: vienne is an unknown quantity at this point

Solved Threads: 0

vienne

Offline

Newbie Poster

Re: Can you guys help me? about Quick Sort Algorithm

Oct 1st, 2004

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)

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
#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");
}
#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.

•

Join Date: Feb 2002

Posts: 12,036

Reputation: cscgal is a glorious beacon of light

Solved Threads: 130

cscgal

Offline

The Queen of DaniWeb

Re: Can you guys help me? about Quick Sort Algorithm

Oct 1st, 2004

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

Dani the Computer Science Gal

Follow my Twitter feed! twitter.com/daniweb

•

Join Date: Sep 2004

Posts: 7,596

Reputation: Narue has a reputation beyond repute

Solved Threads: 712

Narue

Offline

Code Goddess

Re: Can you guys help me? about Quick Sort Algorithm

Oct 2nd, 2004

>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.

I'm here to prove you wrong.