PowerPoint Presentation
Selection sort
19 42 -1 33
0 1 2 3
12 88 2 50
4 5 6 7
61 5 -2 10
8 9 10 11
75 1 14 75
12 13 14 15
Big idea:
We find (select) the smallest value
and move it to the leftmost position.
What do we do with the value that’s there? SWAP
Repeat this N-1 times, moving the target position.
Selection sort
19 42 -1 33
0 1 2 3
12 88 2 50
4 5 6 7
61 5 -2 10
8 9 10 11
75 1 14 75
12 13 14 15
Iteration 0: i = 0, m = 10
Swap array[i] and array[m]
i is index of element where
you want the smallest item to
be placed.
m is the index of the minimum value
to the right of i.
-2 42 -1 33
0 1 2 3
12 88 2 50
4 5 6 7
61 5 19 10
8 9 10 11
75 1 14 75
12 13 14 15
Now array[0] has the smallest value,
and we never need to look at it again.
Selection sort
-2 42 -1 33
0 1 2 3
12 88 2 50
4 5 6 7
61 5 19 10
8 9 10 11
75 1 14 75
12 13 14 15
Iteration 1: i = 1, m = 2
Swap array[i] and array[m]
If i == m, no need to swap.
-2 -1 42 33
0 1 2 3
12 88 2 50
4 5 6 7
61 5 19 10
8 9 10 11
75 1 14 75
12 13 14 15
Now array[1] has the second-smallest value,
and we never need to look at it again.
Selection sort
-2 -1 42 33
0 1 2 3
12 88 2 50
4 5 6 7
61 5 19 10
8 9 10 11
75 1 14 75
12 13 14 15
Iteration 2: i = 2, m = 13
Swap array[i] and array[m]
If i == m, no need to swap.
-2 -1 1 33
0 1 2 3
12 88 2 50
4 5 6 7
61 5 19 10
8 9 10 11
75 42 14 75
12 13 14 15
Now array[1] has the second-smallest value,
and we never need to look at it again.
How to find the minimum value
m = i; // start with assumption that a[i] is min
// look at all values to the right
for (j = i+1; j < n; j++) {
if (a[j] < a[m]) m = j; // if any is smaller,
// it's the new min
}
Note: We're just remembering the minimum index, not
the minimum value. If you want, you can save the min value
and avoid doing a[m].
How to swap
int tmp;
if (m != i) { // is swap needed?
tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
All together...
void selectSort(int a[], int n) {
int i, j, m;
int tmp;
for (i=0; i < n-1; i++) {
m = i;
for (j=i+1; j < n; j++) {
if (a[j] < a[m]) m = j;
}
if (m != i) {
tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
}
}
For each i from 0 to n-2...
m = index of smallest value
at position >= i
Swap element i with smallest value.
End of outer loop
Common error:
void selectSort(int a[], int n) {
int i, j, m, tmp;
for (i=0; i < n-1; i++) {
m = i;
for (j=i+1; j < n; j++) {
if (a[j] < a[m]) {
m = j;
tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
}
}
}
If you swap inside the inner loop, then you're
swapping EVERY TIME you find a new possible min.
Still works, but does a lot of extra swaps.
Runtime analysis
void selectSort(int a[], int n) {
int i, j, m;
int tmp;
for (i=0; i < n-1; i++) {
m = i;
for (j=i+1; j < n; j++) {
if (a[j] < a[m]) m = j;
}
if (m != i) {
tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
}
}
Outer loop executes n-1 times
This loop has (n - (i+1)) steps.
This just happens once per
loop, and does not depend on
the size, so not important.
Runtime analysis
𝑡𝑡 = 𝑛𝑛 − 1 + 𝑛𝑛 − 2 + 𝑛𝑛 − 3 + ⋯+ 2 + 1
𝑡𝑡 = �
𝑘𝑘=1
𝑛𝑛−1
𝑘𝑘 ≈
𝑛𝑛2
2
For an array of size N, time is proportional to N2.
We say selection sort is 𝑂𝑂(𝑁𝑁2).
Sorting non-integers
void selectSort(int a[], int n) {
int i, j, m;
for (i=0; i < n-1; i++) {
m = i;
for (j=i+1; j < n; j++) {
if (a[j] < a[m]) m = j;
}
if (m != i) {
int tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
}
}
What parts of this code
are type-dependent?
Sorting strings -- an array of char*
void selectSort(char* a[], int n) {
int i, j, m;
for (i=0; i < n-1; i++) {
m = i;
for (j=i+1; j < n; j++) {
if (strcmp(a[j],a[m]) < 0) m = j;
}
if (m != i) {
char* tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
}
}
Sorting strings -- an array of char[16]
void selectSort(char a[][16], int n) {
int i, j, m;
char tmp[16];
for (i=0; i < n-1; i++) {
m = i;
for (j=i+1; j < n; j++) {
if (strcmp(a[j],a[m]) < 0) m = j;
}
if (m != i) {
strcpy(tmp,a[i]);
strcpy(a[i],a[m]);
strcpy(a[m],tmp);
}
}
}
Sorting structs -- an array of struct foo
void selectSort(struct foo a[], int n) {
int i, j, m;
struct foo tmp;
for (i=0; i < n-1; i++) {
m = i;
for (j=i+1; j < n; j++) {
if (lessThan(&a[j],&a[m]) m = j;
}
if (m != i) {
tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
}
}
Recommended:
Create a function that
compares two struct values.
Sorting structs -- an array of struct foo *
void selectSort(struct foo * a[], int n) {
int i, j, m;
struct foo *tmp;
for (i=0; i < n-1; i++) {
m = i;
for (j=i+1; j < n; j++) {
if (lessThan(a[j],a[m]) m = j;
}
if (m != i) {
tmp = a[i];
a[i] = a[m];
a[m] = tmp;
}
}
}
Looks the same, but
swap is much cheaper.
Slide Number 1
Slide Number 2
Slide Number 3
Slide Number 4
Slide Number 5
Slide Number 6
Slide Number 7
Slide Number 8
Slide Number 9
Slide Number 10
Slide Number 11
Slide Number 12
Slide Number 13
Slide Number 14
Slide Number 15