2. The analysis part (40%).

a. Describe a method for finding both the maximum and minimum of n numbers using

fewer than 3n/2 comparisons.

b. Suppose each row of an nxn array A only consists of 1's and 0's such that, in any

row i of A, all the 1's come before any 0's. Assuming A is already in memory,

describe a method running in O(nlog n) time for counting the number of 1's in A.

Here is a simple example of bubble sort.

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm.

First Pass:

( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.

( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

( 1 4 2 5 8 ) ( 1 4 2 5 8 )

( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2 ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 5 8 ) ( 1 2 4 5 8 )

( 1 2 4 5 8 ) ( 1 2 4 5 8 )

( 1 2 4 5 8 ) ( 1 2 4 5 8 )

( 1 2 4 5 8 ) ( 1 2 4 5 8 )

Finally, the array is sorted, and the algorithm can terminate.

Merge Sort

The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list. Like most recursive sorts, the merge sort has an algorithmic complexity of O(n log n).

Elementary implementations of the merge sort make use of three arrays - one for each half of the data set and one to store the sorted list in. The below algorithm merges the arrays in-place, so only two arrays are required. There are non-recursive versions of the merge sort, but they don't yield any significant performance enhancement over the recursive algorithm on most machines.

Pros: Marginally faster than the heap sort for larger sets.

Cons: At least twice the memory requirements of the other sorts; recursive.

Merge Sort Efficiency

The merge sort is slightly faster than the heap sort (to be covered) for larger sets, but it requires twice the memory of the heap sort because of the second array. This additional memory requirement makes it unattractive for most purposes - the quick sort is a better choice most of the time and the heap sort is a better choice for very large sets.

Like the quick sort, the merge sort is recursive which can make it a bad choice for applications that run on machines with limited memory.

Source Code

Below is the basic merge sort algorithm.

void mergeSort(int numbers[], int temp[], int array_size) {

m_sort(numbers, temp, 0, array_size - 1); }

void m_sort(int numbers[], int temp[], int left, int right) {

int mid;

if (right > left)

{

mid = (right + left) / 2;

m_sort(numbers, temp, left, mid);

m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);

}

}

void merge(int numbers[], int temp[], int left, int mid, int right) {

int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;

tmp_pos = left;

num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))

{

if (numbers[left] <= numbers[mid])

{

temp[tmp_pos] = numbers[left];

tmp_pos = tmp_pos + 1;

left = left +1;

}

else

{

temp[tmp_pos] = numbers[mid];

tmp_pos = tmp_pos + 1;

mid = mid + 1;

}

}

while (left <= left_end)

{

temp[tmp_pos] = numbers[left];

left = left + 1;

tmp_pos = tmp_pos + 1;

}

while (mid <= right)

{

temp[tmp_pos] = numbers[mid];

mid = mid + 1;

tmp_pos = tmp_pos + 1;

}

for (i=0; i <= num_elements; i++)

{

numbers[right] = temp[right];

right = right - 1;

}

}