Sorting Problems

Question 1

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

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 an O(N^{2}) algorithms 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:

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

main() should look similar to the following:

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

Using the function Bubble defined in Question 3 above, sort a two-dimensional array so that each row of the array is sorted.

Question 2

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 less than the first element are stored in the first 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 4

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 5

Derive the Quicksort algorithm to sort a linear sequence of values.

Question 6

Add questions on Selection Sort and Insertion sort.