bodom_lx at task3 dot cc|

As assignment for Data Structures and Algorithms course, we had to work with a modified version of the quicksort algorithm. It came obvious that for modifying a qsort you need to implement it

It is difficult to find a clear quicksort algorithm implemented, so I wrote it.

Here is the generic C implementation of the Quicksort Algorithm, which sorts an array in place, following the Divide And Conquer design.

Download: quicksort qsort in C language

Interesting methods (look at the source code for comments):

int partition( int A[], int left, int right) {
	int pivot; 
	pivot = A[right];									
	while(1){
		while( A[right] > pivot){
			right--;
		}
		while( A[left] < pivot){	
			left++;					
		}
		if( left < right ){								
			swap(A,left,right);
		}else{
			return left;					
		}
	}
}
 
void quicksort( int A[], int left, int right){
	int m;
	if( left < right ) {				
		m = partition( A, left, right);		
		quicksort( A, left, m-1);		
		quicksort( A, m+1, right);
	}	
}

As you see, there is nothing optimized in this implementation. It just looks elegant and easy to be understood.
If you would like to have a more optimized version of this algorithm, take a look at this one.

Tags: algorithms, C language, code, data structures, Design, Download, HTTP, java, javascript, language, page, pageTracker, php, rest, source, source code, version, Wiki, wikipedia

This entry was posted on Monday, April 7th, 2008 at 11:58 and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.