Sorting
Each record contains a eld called the key.
Linear order: comparison.
[a < b and b < c⇒ a < c.]
The Sorting Problem
Given a sequence of records R1,R2, ..., Rn with
key values k1,k2, ..., kn, respectively, arrange the
records into any order s such that records
Rs1,Rs2, ..., Rsn have keys obeying the property
ks1 ≤ ks2 ≤ ... ≤ ksn.
[Put keys in ascending order.]
Measures of cost:
• Comparisons
• Swaps
122
Insertion Sort
static void inssort(Elem[] array) { // Insertion Sort
for (int i=1; i<array.length; i++) // Insertrecord
for (int j=i; (j>0) &&
(array[j].key()<array[j-1].key()); j--)
DSutil.swap(array, j, j-1);
}
15
i=1
3
4
5
6
42
20
17
13
28
14
23
15
20
42
17
13
28
14
23
15
2
17
20
42
13
28
14
23
15
13
17
20
42
28
14
23
13
17
20
28
42
14
23
13
14
17
20
28
42
23
13
14
17
20
23
28
42
13
14
15
17
20
23
28
42
7
15
15
15
Best Case: [0 swaps, n− 1 comparisons]
Worst Case: [n2/2 swaps and compares]
Average Case: [n2/4 swaps and compares]
[Good best case performance.]
123
Bubble Sort
static void bubsort(Elem[] array) {
// Bubble Sort
for (int i=0; i<array.length-1; i++) // Bubble up
for (int j=array.length-1; j>i; j--)
if (array[j].key() < array[j-1].key())
DSutil.swap(array, j, j-1);
}
[Using test \j > i" saves a factor of 2 over \j > 0".]
15
i=0
1
2
3
4
5
6
42
20
17
13
28
14
23
13
42
20
17
14
28
15
13
14
42
20
17
15
28
23
13
14
20
42
15
17
23
28
13
14
15
20
42
17
23
28
13
14
15
17
20
42
23
28
13
14
15
17
20
23
42
13
14
15
17
20
23
28
42
23
28
Best Case: [n2/2 compares, 0 swaps]
Worst Case: [n2/2 compares, n2/2 swaps]
Average Case: [n2/2 compares, n2/4 swaps]
[No redeeming features to this sort.]
124
Selection Sort
static void selsort(Elem[] array) {
// Selection Sort
for (int i=0; i<array.length-1; i++) { // Select i’th
int lowindex = i;
// Remember its index
for (int j=array.length-1; j>i; j--) // Find least
if (array[j].key() < array[lowindex].key())
lowindex = j;
// Put it in place
DSutil.swap(array, i, lowindex);
}
}
[Select the value to go in the ith position.]
42
i=0
1
2
3
4
5
6
42
20
17
13
28
14
23
15
13