Description

Quicksort is a sorting algorithm. It first picks a number as the pivot, and divides the input array into two sub-arrays: one sub-array has all numbers that is smaller than the pivot, and the other sub-array has all numbers that is larger than the pivot. Next, the same algorithm is applied recursively to sort those two sub-arrays.

void qsort(int arr[], int start, int end)
/* Array arr is the input array.  Integer start and end
are the indices of starting and ending positions of
the input.
*/
/* The stopping step is when the end <= start, which means
 the input has 1 or zero elements, so nothing to do.
*/
     if end > start
         pivotIndex = partition(arr, start, end)
         qsort(arr, start, pivotIndex-1)
         qsort(arr, pivotIndex+1, end)

The partition function is to arrange all the elements so that the numbers in arr[start..pivot-1] are smaller than arr[pivot] and arr[pivot+1 … end] are larger than arr[pivot].  For example, if the input array arr = {1, 4, 2, 5, 3}, start = 0, end = 4, the partition function must return pivotIndex = 2, and arr = {1, 2, 3, 5, 4}. 
   
Your job is to implement the partition function.
1.    Let pivot = arr[end]
2.    Use a temporary array tmp.
3.    For i = start to end-1
4.       If arr[i] < pivot, record arr[i] to tmp from the front of tmp
5.       If arr[i] >= pivot, record arr[i] to tmp from the end of tmp.
6.    Find the correct pivotIndex and place pivot to tmp[pivotIndex]
7.    Copy tmp back to arr
8.    return the correct pivotIndex

An incomplete code is shown below. 
==================================================================

#include 

void show( int arr[], int start, int end){
        int i;
        for( i = start; i <=end ; ++i )
                printf( "%d ", arr[i] );
        printf("\n");
}

int partition( int arr[], int start, int end ){

	int pivot = arr[end];
	int pivotIndex;
	
	/* Insert your code here.*/
	int i;
	int greaterIdx = end, lessIdx = start;
	int tmp[100];

	for( i = start; i < end ; ++i ){
		if( pivot > arr[i] ){
                /* Insert your code here.*/
                }
		else{
                /* Insert your code here.*/
                }
	}
	
	/* Find the correct pivotIndex and place pivot to tmp[pivotIndex]. */

	for( i = start ; i <= end ; i++ )
		arr[i] = tmp[i];

	return pivotIndex;

}
void quick_sort( int arr[], int start, int end ){
        int pivotIndex;
        if( start < end ){
		pivotIndex = partition( arr, start, end );
		show(arr, start, end);
		quick_sort( arr, start, pivotIndex-1 );
		quick_sort( arr, pivotIndex+1, end );
        }
}

int main(){

        int arr[100];
        int n, i;

        // Get array
        scanf( "%d", &n );
        for( i = 0 ; i < n ; ++i )
                scanf( "%d", &arr[i] );

        // Sort
        quick_sort( arr, 0, n-1 );

	//show the final results
	show(arr, 0, n-1);

        return 0;

}

 

Input

The input contains two lines:

First line contains an integer N indicating the number of elements which are unsorted. ( 1 ≤ N ≤ 100 )

Second line contains a list of the positive integer of the N elements, which are separated by blanks
( Becareful, the number may appear more than once. )

Output

Please follow the output of program

Sample Input  Download

Sample Output  Download

Tags

Discuss