CSSE 2 Data Structures and Algorithms III

Worksheet 2: Sorting Problems

Date: 10/10/2001

Question 1

Write a function that takes two parameters and swaps their values. The function prototype should be as follows:

void swap(int & x, int & y);

Show how this function could be used in main().

Question 2

Given an integer array A[N], N >= 0 derive the O(N2) algorithm known as bubble sort that sorts the elements into ascending order. This algorithm should use the function swap defined in Question 1.

Question 3

Rewrite the solution to question 2 above so that your main function calls a function Bubble that sorts the array using bubble sort and has the following function prototype and main() as follows:

void Bubble(int * Array, const int N);

void main()

{

const int N = 5;

int A[N] = {5,6,4,1,3};

Bubble(A,N); //sort the array using the function Bubble

Print(A,N); //function call to print the final array

}

Question 4

Given an integer array f[N], N ³ 0, derive an O(N) algorithm to partition the elements so that all elements less than the first element are stored in the first section of the array and all elements greater than the first element are stored in the second section of the array.

Example:

Array 10, 9, 12, 14, 11, 5, 7, 13, 15 becomes Array 5, 9 , 7, 10, 11, 14, 12, 13, 15

Question 5

Given an integer array f[N], N ³ 0 containing only 1’s and 0’s , derive an O(N) algorithm to partition the elements so that all 0’s precede all 1’s.

Question 6

Write a Quicksort algorithm to sort a linear sequence of values (using the solution to Q5 as the code for the partition function?)

Question 7

Write functions Insertion and Selection which sort a given integer array into ascending order. Show how these function may be called in main().