LAB 3: SORTING ALGORITHMS

DUE MON FEB 17, 2pm

Sorting is one of the most common and useful tasks computers perform. The purpose of this lab is two fold. Firts you implement a number of sorting algorithms. Second, you compare the relative performance of these algorithms.

The algorithms you will implement are:

1. Selection Sort

2. Bubble Sort

3. Insertion Sort

4. Merge Sort

5.Quick Sort

In the implementation of Bubble Sort and Insertion Sort, your algorithm should be able to take advantage of a sorted array (if array is already sorted to begin with or if it becomes sorted before the final iteration).

In the implementation of Merge Sort and Quick Sort, do NOT use pointers (use the prototypes given in class).

In addition to sorting, keep track of how many comparisons (not swaps) are being made for each algorithm. We will use this count to compare these algorithms.

Define a global variable called MAX in your program, which will be the size of the array, say data, to be sorted by all these algorithms. Initialize data according to each method described below and run all the sorting algorithms on the array. Each algorithm should report how many comparions it made.

Ways to initiliaze the array data:

1. for(int i = 0; i < MAX; i++)

data[i] = i;

2. for(int i = 0; i < MAX; i++)

data[i] = MAX-i;

3. for(int i = 0; i < MAX/2; i++)

data[i] = MAX/2-i;

for(int i = MAX/2; i < MAX; i++)

data[i] = MAX-i;

Note: Once you run one of the algorithms on the array, it is sorted. Before running another one, you need to initiliaze the array again (with the same scheme) so that all the algorithms will run on exactly the same array.

Assign different values to MAX (like 100, 1000, 10000, 20000, 30000) and observe the outputs. Are they somewhat close to theoretical running times?

Below is a sample main part. It is NOT meant to be complete (or the best way of doing this lab). Among other incompletenesses, it is only showing one way of initializing data.

int data[MAX]; // Array of integers to be sorted

for(int i=0;i<MAX/2;i++)

data[i]=MAX/2-i;
for(int i=MAX/2+1;i<MAX;i++)

data[i]=MAX-i;



mergesort(data,0,MAX-1);
cout<<"Mergesort finished with "<<m_count<<" comparisons"<<endl;

//Remember to initialize again after running one sorting algorithm!

for(int i=0;i<MAX/2;i++)

data[i]=MAX/2-i;

for(int i=MAX/2;i<MAX;i++)

data[i]=MAX-i;

bubblesort(data,0,MAX-1);

cout<<"Bubble sort finished with "<<b_count<<" comparisons"<<endl;

for(int i=0;i<MAX/2;i++)

data[i]=MAX/2-i;

for(int i=MAX/2;i<MAX;i++)

data[i]=MAX-i;



insertionsort(data,0,MAX-1);
cout<<"Insertion sort finished with "<<i_count<<" comparisons"<<endl;

for(int i=0;i<MAX/2;i++)

data[i]=MAX/2-i;
for(int i=MAX/2;i<MAX;i++)

data[i]=MAX-i;

selectionsort(data,0, MAX-1 );
cout<<"Selection sort is done with "<<s_count<<" comparisons "<<endl;

for(int i=0;i<MAX/2;i++)

data[i]=MAX/2-i;
for(int i=MAX/2;i<MAX;i++)

data[i]=MAX-i;
quicksort(data,0,MAX-1);
cout<<"Quick Sort finished with "<<q_count<<" comparisons"<<endl;

system("PAUSE");
return 0;