what is Shell Sort?
GIAN Tutorials
11:19 PM
Shell Sort Shell sort is the generalization of insertion sort which overcomes the drawbacks of insertion sort by comparing elements separated by a gap of several positions. In general, Shell sort performs the following steps. Step 1 : Arrange the elements in the tabular form and sort the columns by using insertion sort. Step 2 : Repeat Step 1; each time with smaller number of longer columns in such a way that at the end, there is only one column of data to be sorted. Complexity Complexity Best Case Average Case Worst Case Time Complexity Ω(n log(n)) θ(n log(n) 2 ) O(n log(n) 2 ) Space Complexity O(1) Algorithm Shell_Sort(Arr, n) Step 1 : SET FLAG = 1, GAP_SIZE = N Step 2 : Repeat Steps 3 to 6 while FLAG = 1 OR GAP_SIZE > 1 Step 3 :SET FLAG = 0 Step 4 :SET GAP_SIZE = (GAP_SIZE + 1) / 2 Step 5 :Repeat Step 6 for I = 0 to I < (N -GAP_SIZE) Step 6 :IF Arr[I + GAP_SIZE] > Arr[I] SWAP Arr[I + GAP_SIZE], Arr[I] SET FLAG = 0 Step 7 : END C Program
