•
•
•
•
What is DaniWeb IT Discussion Community?
You're currently browsing the C section within the Software Development category of DaniWeb, a massive community of 391,582 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 2,665 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our C advertiser:
Views: 3995 | Replies: 5
 |
•
•
Join Date: Jul 2004
Posts: 6
Reputation: 
Rep Power: 0
Solved Threads: 0
Newbie Poster
Can you guys help me? about Quick Sort Algorithm 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:
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: 6,017
Reputation: 
Rep Power: 26
Solved Threads: 414
•
•
•
•
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:
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 );
}
Member of: Beautiful Code Club.
•
•
Join Date: Jul 2004
Posts: 6
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
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)
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.
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.
•
•
Join Date: Feb 2002
Location: Lawn Guylen, NY
Posts: 10,879
Reputation:
Rep Power: 32
Solved Threads: 106
This program that I wrote should be of help to you: http://www.daniweb.com/techtalkforums/thread1689.html
Dani the Computer Science Gal
Do you run a computer-related website? Feature it in our niche link directory!
Do you run a computer-related website? Feature it in our niche link directory!
•
•
Join Date: Sep 2004
Posts: 6,017
Reputation:
Rep Power: 26
Solved Threads: 414
>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.
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.
Member of: Beautiful Code Club.
•
•
Join Date: Jul 2004
Posts: 6
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
•
•
•
•
Originally Posted by cscgal
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~
|
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
•
•
•
•
•
•
•
•
DaniWeb C Marketplace
Linear Mode
- quick Sort (C)
- Code for Quick Sort (using Recursion) (Assembly)
- quick sort question (C)
- Index array & sort algorithm??? (Java)
Other Threads in the C Forum
- Previous Thread: End of file function
- Next Thread: address book i need it now!!!!!
