1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
|
[\<- 05/29](05-29.md)
---
## Sorting
- Different ways to classify sorting algorithms
- **Internal**
- All data to be sorted is in memory
- **External**
- the data is kept on disk and small pieces of data are brought into memory to be processed
- For example, a file of 20,000 records may be sorted using an array that holds only 1000 records. During the sorting process, only 1000 records are in memory at any one time
- Another way to classify sorting algorithms:
- **Stable**: if two records to be sorted, r1 and r2 have identical sort keys, and if r1 comes before r2 in the original input, then r1 comes before r2 in the sorted output
- **Unstable**: the order of the records with identical keys is not guaranteed
- Example:
- sort students according to their age. student A - 20 and student B - 20 (don't want subsequent sort to mess up previous sort)
- Yet another way to classify sorting algorithms (based on how they work):
- **Selection-based**: repeatedly select the smallest (or largest) remaining item and place it in the output
- e.g., selection sort, heap sort
- **Insertion-based**: you take the next available item and insert it in its proper place in a sorted list
- e.g., insertion sort, shell sort, tree sort
- **Exchange-based**: intelligently exchange or swap two items in the list until the list is sorted
- e.g., bubble sort, quick sort
- **other**: doesn't fit into any of the above categories
- e.g., radix sort, merge sort (sometimes called "sortless sort" algorithms)
# Sorting Algorithms
- We're starting with the easiest algorithm in each category first
- **Selection-based**: selection sort
- **Insertion-based**: insertion sort
- **Exchange-based**: bubble sort
- Note that, like with data structures, there is no one ideal sorting algorithm
## Selection Sort
- How it works?
- the array is logically partitioned into two sections: sorted and unsorted
- the sorted section is also in the correct location
- repeatedly find the next smallest item from the unsorted section and then move it into its correct position
### One Sort Pass
- One sort pass: each time an element moves from the unsorted sublist to the sorted sublist
- Ex. sort 44, 10, 21, 78, 53, 92, 37, 85
|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|44 |10 |21 |78 |53 |92 |37 |85 |
- Swap 10 and 44
|Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |44 |21 |78 |53 |92 |37 |85 |
- Swap 44 and 21
|Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |44 |78 |53 |92 |37 |85 |
- Swap 44 and 37
|Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |37 |78 |53 |92 |44 |85 |
- Swap 78 and 44
|Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |37 |44 |53 |92 |78 |85 |
- 53 is already in the right place, so it would just swap with itself
|Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |37 |44 |53 |92 |78 |85 |
- Swap 92 and 78
|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |37 |44 |53 |78 |92 |85 |
- Swap 92 and 85
|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |37 |44 |53 |78 |85 |92 |
- The array is sorted!
```
void selectionSort(int a[], int n){
int i, j, min, temp;
for(i=0; i<n-1; i++){
min = i; //slot of smallest value
for(j=i+1; j<n; j++){
if(a[j] < a[min]) min = j;
}
//swap
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
```
- Big-O runtime: O(n^2)
- Stable? Unstable?
- Ex. 4 2 3 4 1
- Algorithm is unstable
- What is the space overhead? (the what?)
- How much extra space is needed by our algorithm?
- We sort the array in place
- All we need is a few integers, so the overhead is O(1)
### Can we make it stable?
- Selection sort can be made stable by shifting rather than swapping
- This change is typically not made, because as we coded it, selection sort does the fewest number of memory writes of any sorting algorithm
## Insertion Sort
- Card players: Each time they pick up a card, **insert it into the proper sequence** in their hand
- How it works? take the next item in the array and place it in an already sorted list of items
- In this case, the sorted partition will not necessarily in the proper final position
- ex. Sort 44, 10, 21, 78, 53, 92, 37, 85
|Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|44 |10 |21 |78 |53 |92 |37 |85 |
- 10 should be inserted before 44
|Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |44 |21 |78 |53 |92 |37 |85 |
- 21 should be inserted between 10 and 44
|Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |44 |78 |53 |92 |37 |85 |
- 78 is already sorted
|Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |44 |78 |53 |92 |37 |85 |
- 53 should be inserted between 44 and 78
|Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |44 |53 |78 |92 |37 |85 |
- 92 is already sorted
|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |44 |53 |78 |92 |37 |85 |
- 37 should be inserted between 21 and 44
|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Unsorted|
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |37 |44 |53 |78 |92 |85 |
- 85 should be inserted between 78 and 92
|Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |Sorted |
|--------|--------|--------|--------|--------|--------|--------|--------|
|10 |21 |37 |44 |53 |78 |85 |92 |
- The Array is Sorted!
```
void insertionSort(int a[], int n){
int i, j, temp;
for(i=1; i<n; i++){
temp = a[i];
for(j=i-1; j>=0 && temp>a[i]; j--){
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
```
- Big-O Runtime:
- Worst Case: O(n^2)
- Best Case: O(n) (When the array is already sorted)
- Average: O(n^2)
- Stable? Unstable?
- Stable: the loop uses a `<` instead of `<=`
- Space overhead?
- Again, we sort the array in place
- All we need are a few integers, so O(1) overhead
## Exchange Sort
- Concept: exchange elements that are out of order until the entire list is sorted
- Feature: use exchange extensively
## Bubble Sort
- What is bubble sort:
- The list at any moment is divided into two sublist: sorted and unsorted
- The smallest element is bubbled from the unsorted sublist and moved to the sorted sublist
- After moving the smallest to the sorted list the wall moves one element to the right, increasing the number of sorted elements and decreasing the number of unsorted ones
- Ex. sort 44, 10, 21, 78, 53, 92, 37, 85
- Comapre 85 and 37: correct order
- Compare 37 and 92: they should be swapped
- 44, 10, 21, 78, 53, 37, 92, 85
- Compare 37 and 53: they should be swapped
- 44, 10, 21, 78, 37, 53, 92, 85
- Compare 37 and 78: they should be swapped
- 44, 10, 21, 37, 78, 53, 92, 85
- Compare 37 and 32: correct order
- Compare 21 and 10: correct order
- Compare 10 and 44: they should be swapped
- 10, 44, 21, 37, 78, 53, 92, 85
- This is the array after the first pass
- Only one item is in the right place (10)
- Continue to do passes until the entire array is sorted
```
bool sorted = false; //flag to avoid unneccessary looping
for(i = 0; i < (n-1) && !sorted; i++){
sorted = true;
for(j = n-1; j>i; j--){ //don't go over elements already in position
if(a[j] < a[j-1]){
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
sorted = false;
}
}
}
```
- What's the best-case big-O? O(n) (if we use the sorted flag
- Worst Case? O(n^2)
- Average? O(n^2)
- Is it stable?
- Yes: only swap if `<` rather than `<=`
- Space overhead? O(1)
- Statistically, this looks just as good as insertion sort, but it involves much more writing, so it is slower in actuality
## Check Out These Sorting Algorithm Visualizations
- [sorting.at](http://sorting.at)
- [cs.usfca.edu/~galles/visualization/ComparisonSort.html](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
---
[06/03 ->](06-03.md)
|
