Data Structures & Algorithms - Topic 15 - Selection, Insertion, Bubble & Shell Sort - Lecture Slides
Document Details
Uploaded by SnazzyConnemara3448
Hamdard University
Tags
Summary
These slides cover fundamental sorting algorithms, including Selection, Insertion, Bubble, and Shell Sort. The document provides explanations and pseudocode examples, demonstrating how to implement these algorithms. They are suitable for an undergraduate-level computer science course.
Full Transcript
DATA STRUCTURES AND ALGORITHMS Topic 15 Selection, Insertion, Bubble & Shell Sort 1 Basic Sorting Block 3 Before starting to learn sorting algorithms, lets start with a very basic sorting...
DATA STRUCTURES AND ALGORITHMS Topic 15 Selection, Insertion, Bubble & Shell Sort 1 Basic Sorting Block 3 Before starting to learn sorting algorithms, lets start with a very basic sorting 4 4 block. It takes two numbers as an 3 input and tells which one is smaller and vice versa. 2 Basic Sorting Block num1 If num1 List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 21 6 8 5 100 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 21 6 8 5 i 101 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 21 6 8 5 j i 102 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 21 6 8 5 j i 103 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 21 6 8 5 j i 104 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 21 6 8 5 j i 105 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 21 8 5 j i 106 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 21 8 5 j i 107 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 21 8 5 j i 108 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 8 21 5 j i 109 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 8 21 5 j i 110 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 8 21 5 j i 111 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 8 5 21 j i 112 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 8 5 21 j i 113 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 8 5 21 j i 114 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 8 5 21 j i 115 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 12 6 8 5 21 j i 116 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 12 8 5 21 j i 117 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 12 8 5 21 j i 118 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 12 8 5 21 j i 119 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 12 5 21 j i 120 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 12 5 21 j i 121 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 12 5 21 j i 122 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 5 12 21 j i 123 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 5 12 21 j i 124 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 5 12 21 j i 125 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 5 12 21 j i 126 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 5 12 21 j i 127 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 5 12 21 j i 128 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 8 5 12 21 j i 129 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 5 8 12 21 j i 130 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 5 8 12 21 j i 131 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 5 8 12 21 j i 132 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 5 8 12 21 j i 133 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 6 5 8 12 21 j i 134 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 5 6 8 12 21 j i 135 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 5 6 8 12 21 j i 136 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 5 6 8 12 21 j i 137 3rd Sorting Algorithm : Bubble Sort Algorithm BubbleSort(List[L…U]) For i = U-1 to L For j = L to i If List[ j ] > List[ j+1 ] Swap List[ j ] = List[ j+1 ] L U 5 6 8 12 21 j i 138 4th Sorting Algorithm: Shell Sort Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else Swap List[ i+gap ] ↔ List[ i ] 139 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 140 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 141 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 142 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 143 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 144 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 145 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 146 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 147 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 148 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 149 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 150 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 151 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 152 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 153 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 154 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 155 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 156 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 157 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 158 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 159 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 160 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 4 2 7 9 5 23 29 15 9 31 j i i+gap 10 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 161 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 7 9 5 23 29 15 9 31 j i i+gap 10 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 162 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 7 9 5 23 29 15 9 31 j i i+gap 3 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 163 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 7 9 5 23 29 15 9 31 j i i+gap 3 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 164 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 7 9 5 23 29 15 9 31 j i i+gap 3 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 165 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 7 9 5 23 29 15 9 31 j i i+gap 3 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 166 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 7 9 5 23 29 15 9 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 167 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 7 9 5 23 29 15 9 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 168 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 7 9 5 23 29 15 9 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 169 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 170 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 171 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 172 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 173 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 174 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 175 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 176 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 177 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 178 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 179 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 180 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 181 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 23 29 15 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 182 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 29 23 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 183 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 29 23 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 184 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 29 23 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 185 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 29 23 9 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 186 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 29 23 9 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 187 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 29 23 9 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 188 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 29 23 9 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 189 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 190 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 191 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 192 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 193 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 194 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 195 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 196 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 197 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 2 2 5 9 7 15 9 23 29 31 j i i+gap 10 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 198 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 10 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 199 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 2 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 200 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 2 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 201 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 2 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 202 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 2 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 203 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 3 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 204 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 3 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 205 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 3 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 206 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 3 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 207 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 208 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 209 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 9 7 15 9 23 29 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 210 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 211 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 212 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 213 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 4 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 214 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 215 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 216 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 217 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 5 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 218 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 219 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 220 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 15 9 23 29 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 221 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 222 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 223 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 224 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 6 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 225 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 226 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 227 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 7 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 228 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 229 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 230 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 8 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 231 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 232 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 233 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 9 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 234 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 1 2 5 7 9 9 15 23 29 31 j i i+gap 10 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 235 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 0 2 5 7 9 9 15 23 29 31 j i i+gap 10 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 236 gap L U 1 2 3 4 5 6 7 8 9 Shell Sort 0 2 5 7 9 9 15 23 29 31 j i i+gap 10 Algorithm ShellSort(List[L…U]) For gap = U/2 to 1: gap=gap/2 For j = gap+1 to U For i = j – gap to L: i = i - gap If List[ i+gap ] > List[ i ] break Else List[ i+gap ] ↔ List[ i ] 237 Class Activity Find the Worst Case Time Complexity of all sorting algorithms in this lecture except: – Shell’s Sort Note: Do analysis to count total number of: – Swaps/Shifts – Comparisons – All basic operations 238 End of Lecture THANK YOU 239
