Programming C Assignment

Quicksort

Objectives

Learn to sort the values of an array

Practice using recursion

Practice implementing pseudocode

More practice with 1D arrays

Overview

For this lab, you will first populate an array with integer values provided by a user and then you will sort the array. You will implement a recursive quicksort algorithm.

Quicksort Algorithm

Quicksort, also known as the partition-exchange sort, is an efficient algorithm. From Wikipedia:

Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

Pick an element, called a pivot, from the array.

Reorder the array so that all elements with values less than the pivor come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivor is in its final position. This is called the partition operation.

Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

The base case of the recursion is arrays of size zero or one, which never need to be sorted.

Implementation

At the top of your program, define a constant to restrict the maximum size of your array:

 #define MAX_ARRAY_SIZE 50 

You will implement 5 functions as well as your main function. The function prototypes are:

 int populate_array( int array[] ); // Fill array with values from user. void print_array( int array[], int n ); // Print out the array values void swap( int array[], int index1, int index2 ); // Swap two array elements. void quicksort( int array[], int low, int high ); // Sorting algorithm int partition( int array[], int low, int high ); // Find the partition point (pivot) 

These function prototypes will appear near the beginning of the program. Later in the program, you will provide the function implementation (you repeat the function prototype but this time you provide the function body as well).

main Function

In your main function, declare an array of size MAX_ARRAY_SIZE.

Next, call your function populate_array (described below) and save the result as variable n.

Print out the value in the array by calling your function print_array (described below).

Now call your sorting algorithm with the line:

quicksort(array, 0, n-1); 

Now verify that your list is sorted by printing out the list. Once more, call the print_array function.

return 0; to exit with no errors to report.

populate_array Function

Prompt the user for an integer n:

Enter the value of n > 

Validate that n is less than or equal to MAX_ARRAY_SIZE and greater than or equal to 0. f not, repeat Step 1.

Read in n integers from the user. You can assume these will be valid integers: either positive, negative or zero.

Scan in each integer one by one using a for loop. Save each value in the proper position in the array, beginning with index 0.

Return n.

print_array Function

Print the values in the array, one value per line, using a for loop.

TIP: Use the formatting code %+5d to print back each digit. This will slightly indent and display either a positive or negative sign in front of the number as appropriate.

swap Function

You will need to implement a "helper" swap function, which is called by the partition function. This function swaps the values located in index1 and index2 of array. There is nothing to return from this function.

TIP: Recall that an array name is a pointer to the first element Therefore, passing the array to your swap accmplishes pass-by-reference. You do not need to return anything because changes to the array will persist once the swap function returns.

quicksort function

Next, implement the quicksort function. Convert this pseudocode to valid C code.

 Algorithm 1: Quicksort Algorithm procedure QUICKSORT( A, low, high ) if low < high then pivot <- partition( A, low, high ) quicksort( A, low, pivot - 1 ) quicksort( A, pivot + 1, high ) end if end procedure 

TIP: The quicksort function does not have an explicit base case, but it does have one. When low == high, the array is of size 1 and nothing needs to happen. The function merely returns, thereby bottoming out the recursion.

partition Function

Lastly, implement the partition function. Convert this pseudocode to valid C code:

 Algorithm 2: Partition procedure PARTITION( A, low, high ) pivot <- A[high] i <- low for j = low to high-1 do if A[j] <= pivot then swap(A, i, j) i <- i + 1 end if end for swap( A, i, high ) return i end procedure 

Example Execution

Example 1

 [esus] $ ./program2 Enter the value of n > -1 -1 is less than zero. Please try again. Enter the value of n > 100 100 exceeds the maximum array size. Please try again. Enter the value of n > 5 Enter 5 integers (positive, negative, or zero) > 7 0 -3 5 1 The initial array contains: +7 +0 -3 +5 +1 The array is now sorted: -3 +0 +1 +5 +7 

Example 2

 [esus] $ ./program2 Enter the value of n > 8 Enter 8 integers (positive, negative, or zero) > 4 -3 2 -1 0 -9 8 7 The initial array contains: +4 -3 +2 -1 +0 -9 +8 +7 The array is now sorted: -9 -3 -1 +0 +2 +4 +7 +8 

Compile & Test

Compile your program using this gcc command. -std=c99 uses the C99 standard instead of the default C89 standard.

 $ gcc -Wall -std=c99 program2.c -o program2 

NOTE: Make sure you output is very similar to the example execution.