-
Quicksort
Hi,
I tried to write the source code myself but there're tons of errors. And even if i can compile i bet it doesn't work. I need a solution. I need to study. Pls help. Thnx. Note that i need to use recursive techniques.
THis is what i have just to prove that i really tried myself:
Code:
/* Quicksort */
#include <stdio.h>
#define SIZE 10
void quicksort( int array[], int starting, int ending );
void partition( int array, int arraySize, int starting, int ending );
int main()
{
int array[ SIZE ] = { 37, 2, 6, 4, 89, 8, 10, 12, 68, 45 };
int i;
quicksort( array, 0, 9 );
for ( i = 0; i < SIZE; i++ )
printf( "%d ", array[ i ] );
printf( "\n" );
getch();
return 0;
}
void partition( int array, int arraySize, int starting, int ending )
{
int temp;
int i, end = 0;
int rightmost = ending;
int ele = starting;
int swapsMade = 0;
int leftmost;
while ( end != 1 ) {
for ( i = rightmost; i >= 0; i-- ) {
if ( array[ i ] < array[ ele ] ) {
temp = array[ ele ];
array[ ele ] = array[ i ];
array[ i ] = temp;
temp = ele;
ele = i;
leftmost = temp;
swapsMade++;
break;
}
}
for ( i = leftmost; i < arraySize; i++ ) {
if ( array[ i ] > array[ ele ] ) {
temp = array[ ele ];
array[ ele ] = array[ i ];
array[ i ] = temp;
temp = ele;
ele = i;
rightmost = temp;
swapsMade++;
break;
}
}
if ( swapsMade == 0 )
end = 1;
}
}
void quicksort( int array[], int starting, int ending )
{
int i;
int inOrder = 0;
for ( i = 0; i < SIZE - 2; i++ )
if ( array[ i ] < array[ i + 1 ] )
inOrder = 1;
if ( inOrder != 1 )
partition( array, SIZE, starting, ending );
}
-
I worked on this quickly because I have my own work to do, but this is the idea.
Code:
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int IsLess(int x, int mid)
{
if(x < mid)
return -1;
else
return 1;
}
int GetRecord(int a[], int x)
{
return a[x];
}
void QSort(int a[], int left, int right)
{
int i = left;
int j = right;
//get middle record
int temp = GetRecord(a, (i+j) / 2);
do
{
while (IsLess(GetRecord(a,i), temp) < 0 && i < right)
i++;
while (IsLess(temp,GetRecord(a,j)) < 0 && j > left)
j--;
//swap
if( i <= j)
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}while( i <= j);
//recursive calls
if(left < j)
QSort(a,left,j);
if(i < right)
QSort(a,i,right);
}
int main()
{
const int size = 10;
int array[size] = { 37, 2, 6, 4, 89, 8, 10, 12, 68, 45 };
QSort(array, 0, size - 1);
for(int i = 0; i < size; i++)
printf("%d ",array[i]);
return 0;
}