Not Yet Answered # Can you guys help me? about Quick Sort Algorithm

Narue 5,707 Discussion Starter vienne Dani 1,477 Narue 5,707 Discussion Starter vienne shashankc Write a C program that should create a 10 element array of random integers (0 to 9). The program should total all of the numbers in the odd positions of the array and compare them with the total of the numbers in the even positions of the array and indicate ...

0

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

0

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.

0

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

0

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

0

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

-1

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);
}
```

*Edited 5 Years Ago by shashankc*: code change

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hi. so this is actually a continuation from another question of mineHere but i was advised to start a new thread as the original question was already answered.

This is the result of previous question answered :

code for the listbox - datagridview interaction

At the top of the code ...

the function that I created to find the ...