Decrease-and-Conquer: Implementation of Insertion Sort algorithm
Problem Definition:
Sort an array of student records (a record is a structure with a “serial number” and a “score” field) using Insertion Sort in nondecreasing order on the “serial number” field of the records. Compare the running time and number of element-to-element comparisons with the implementations of Bubble Sort, Selection Sort.
Input: Input begins with n (1 ≤ n ≤ 220) of number of records indicating the size of the input array. The following n lines has a record per line with a 9-digit “serial number” field and a 4-digit integer “score” field separated by a space.
Output: Output to have five lines, one line for each of Insertion Sort, Bubble Sort, Selection Sort. A line to have the name of the algorithm, element-to-element comparison count and running time (in seconds upto 6 decimal places) separated by spaces as shown in the sample output. For the set of 8 test-cases of random numbers (of input sizes 32k, 64k, 96k, 128k, 160k, 192k, 224, and 256k), plot two curves of an algorithm per graph sheet; one curve for the comparison counts and the other for the running times. So five graph sheets for the set of 8 test-cases to be used. Let the x-axis to have input sizes 32k per unit, and two different units for the y-axis; one being comparison count and the other being time in seconds. Mention about the correlation between comparison counts and running times in your conclusion.
Sample Input:
5
2123456 100
1234 92
1 1
123123123 9999
9 99
Sample Output:
Insertion Sort: 6 0.000000
Bubble Sort: 7 0.000000
Selection Sort: 10 0.000000
Algorithms:
Algorithm InsertionSort(A[0..n-1])
for i ← 1 to n-1
temp ← A[i]
j ← i-1
while(j ≥ 0 and A[j] > temp)
A[j+1] ← A[j]
j ← j-1
A[j+1] ← temp
Algorithm BubbleSort(A[0..n-1])
for i ← 0 to n - 2
noSwaps ← TRUE
for j ← 0 to n - 2 - i
if(A[j] > A[j+1])
swap A[j] and A[j+1]
noSwaps ← FALSE
if (noSwaps = TRUE) return
Algorithm SelectionSort(A[0..n-1])
for i ← 0 to n-2
min ← i
for j ← i+1 to n-1
if(A[j] < A[min]) min ← j
Swap A[i] with A[min]
Practice-Problems:
1. Just like the set of 8 test-cases of random numbers, generate sets of test-cases with sorted numbers, sorted in reverse order, almost sorted, a lot of repeated entries, etc. Some algorithms are expected to perform better than the others on specific kinds of inputs.
Write main.c file by yourself (No Auto script evaluation for this Program)
