Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

executable file 76 lines (61 sloc) 1.879 kb
#include <stdio.h>
#include <stdlib.h>
void swap(int A[], int key1, int key2); /* swaps two array elements */
int partition( int A[], int left, int right); /* partition an array such that: lower_part<= higher part. */
void quicksort( int A[], int left, int right); /* uses partition to sort the array */
/*void print(); *//* auxiliary: to print the array */
void swap(int A[], int key1, int key2){
int tmp;
tmp = A[key2];
A[key2] = A[key1];
A[key1] = tmp;
}
int partition( int A[], int left, int right) {
int pivot;
pivot = A[right];
while(1){
while( A[right] > pivot){ // while the elements starting from right are > than the last element
right--; // divide the problem
}
while( A[left] < pivot){ // while the elements starting from left are < than the last element
left++; // divide the problem (A[] considered becomes smaller)
}
if( left < right ){
swap(A,left,right); // swap the elements OR
}else{
return left; // return a new left "pointer"
}
}
}
void quicksort( int A[], int left, int right){
int m;
if( left < right ) { // make sure that we are trying to sort a subarray
m = partition( A, left, right); // divide and conquer
quicksort( A, left, m-1); // sort both subarrays
quicksort( A, m+1, right);
}
}
const int MAX=20;
size_t ARRAY_SIZE;
int main() {
int A[MAX];
printf("How many elements? (MAX: %i)",MAX);
scanf("%i",&ARRAY_SIZE);
int i;
printf("Enter the Elements:\n");
for (i=0; i<ARRAY_SIZE; ++i)
scanf("%i",A+i);
quicksort( A, 0, ARRAY_SIZE - 1);
printf("\n\nSorted array is: ");
for(i = 0; i < ARRAY_SIZE; ++i)
printf(" %d ", A[i]);
printf("\n");
}
/*
void print(int A[]){
int i;
for(i = 0; i < ARRAY_SIZE; ++i)
printf(" %d ", A[i]);
printf("\n");
}
*/
Jump to Line
Something went wrong with that request. Please try again.