Quicksort Objectives Learn to sort the values of an array Practice using recursi
ID: 3865221 • Letter: Q
Question
Quicksort
Objectives
Learn to sort the values of an array
Practice using recursion
Practice implementing pseudocode
More practice with 1D arrays
UPDATE: The pseudocode for this algorithm has been updated as of 3/6/2017
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:
You will implement 5 functions as well as your main function. The function prototypes are:
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:
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:
Validate that n is less than or equal to MAX_ARRAY_SIZE. If 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.
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:
Example Execution
Example 1
Example 2
Compile & Test
Compile your program using this gcc command. c99 is a shortcut for running gcc -std=c99, which uses the C99 standard instead of the default C89 standard.
Explanation / Answer
/* C implementation QuickSort */
#include<stdio.h>
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf(" ");
}
// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.