Implement the following algorithms: 1. Insertion Sort 2. Merge Sort 3. In-place
ID: 3893002 • Letter: I
Question
Implement the following algorithms: 1. Insertion Sort 2. Merge Sort 3. In-place quicksort (any random item or the first or the last item of your input can be pivot). 4. Modified quicksort:
a. Use median-of-three as pivot. b. For small subproblem size ( ), you must use insertion sort.
Execution instructions: 1. Run these algorithms for different input sizes (e.g. = 500, 1000, 2000, 4000, 5000, 10000, 20000, 30000, 40000 and 50,000). You will randomly generate numbers for your input array. Record the execution time (need to take the average as discussed in the class) in a table and later plot them all in a single graph against input size. Note that you will compare these sorting algorithms for the same data set.
2. In addition, observe and present performance of the following two special cases:
a. Input array is already sorted.
b. Input array is inversely sorted.
Explanation / Answer
ALGORITHM FOR INSERTION SORT:
This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of ?(n2), where n is the number of items
Algorithm
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]
ALGORITHM FOR MERGE SORT:
Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems. To sort A[p .. r]: 1. Divide Step If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r]. 2. Conquer Step Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r]. 3. Combine Step Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence.
With worst-case time complexity being ?(n log n), it is one of the most respected algorithms.
Algorithm: Merge Sort
void mergesort(int a[], int p, int r) { int q; if(p < r) { q = floor( (p+r) / 2); mergesort(a, p, q); mergesort(a, q+1, r); merge(a, p, q, r); } }
void merge(int a[], int p, int q, int r) { int b[5]; //same size of a[] int i, j, k; k = 0; i = p; j = q+1; while(i <= q && j <= r) { if(a[i] < a[j]) { b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++; } else { b[k++] = a[j++]; } } while(i <= q) { b[k++] = a[i++]; } while(j <= r) { b[k++] = a[j++]; } for(i=r; i >= p; i--) { a[i] = b[--k]; // copying back the sorted list to a[] }
}
ALGORITHM FOR IN PLACE QUICK SORT.
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
Quick sort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst case complexity are of ?(nlogn), where n is the number of items.
Algorithm:
algorithm quicksort(A, lo, hi) is if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p) quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do: i := i + 1 while A[i] < pivot do do: j := j - 1 while A[j] > pivot do if i >= j then return j swap A[i] with A[j]