CSC 2200 Lecture Notes - Lecture 24: Shellsort, Sorting Algorithm, Insertion Sort
19 Jul 2018
School
Department
Course
Professor
Document Summary
How shell sort works: we compare values in each sub-list and swap them (if necessary) in the original array. After this step, the new array should look like this : then, we take interval of 2 and this gap generates two sub-lists - {14, 27, 35, 42}, {19, 10, 33, 44: we compare and swap the values, if required, in the original array. After this step, the array should look like this : finally, we sort the rest of the array using interval of value 1. Shell sort uses insertion sort to sort the array: following is the step-by-step depiction . We see that it required only four swaps to sort the rest of the array. Step 1 initialize the value of h. Step 2 divide the list into smaller sub-list of equal interval h. Step 3 sort these sub-lists using insertion sort. Step 3 repeat until complete list is sorted.
