Question

1) For the list shown below, illustrate each of following sorts as shown in the slide(s) listed: 68, 12, 46, 23, 97, 38, 76, 64 :

a) Insertion sort :

b) Shell sort with sequence 5,3,1

c) Merge sort

e) Radix sort

Note: continue each until the final list is sorted!

Answer 1

(a) Insertion sort:

• It is a simple sorting algorithm that builds the final sorted array one item at a time.
• It is less efficient than heap sort, merge sort and quick sort.
• It is based on the idea that one element from the input elements is consumed in each iteration to find its correct position.

Finally the sorted array is 12,23,38,46,64,68,76,97

(b) Shell sort:

• The shell sort is also called diminishing increment sort.
• It improves on the insertion sort by breaking the original list into number of smaller sub lists.
• By sorting the sub lists we have moved the items closer to where they actually belong.
• We should calculate the gap value recursively until we get the value of gap as '1'.
• The method starts by sorting elements far apart from each other and progressively reducing the gap between them.

Finally we have sorted the array.

(c) Merge sort:

• It is a sorting technique based on divide and conquer technique.
• It first divides the array into equal halves and then combine them in sorted manner.

(e) Radix sort:

• Radix sort is an integer sorting algorithm.
• It uses radix or digit as a key.
• It implements counting sort to do the work of sorting.