6.2. Sorting: Quadratic Sorts¶

6.2.1. Quadratic Sorts¶

6.2.1.1. Sorting¶

Each record contains a field called the key.

Linear order: comparison.

Measures of cost:

Comparisons

Swaps

6.2.1.2. Insertion Sort¶

What would you do if you have a stack of phone bills from the past two years and you want to order by date? A fairly natural way to handle this is to look at the first two bills and put them in order. Then take the third bill and put it into the right position with respect to the first two, and so on.

6.2.1.3. Initial Step¶

Consider this start to the process.

1 / 11 Settings
<<<>>>

Insertion Sort starts with the record in position 1.

200
101
152
543
554
115
786
147

Saving...
Server Error
Resubmit

6.2.1.4. Analysis: Worst Case¶

1 / 24 Settings
<<<>>>

We first examine the worst case cost.

static <T extends Comparable<T>> void inssort(T[] A) {
for (int i=1; i<A.length; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--)
swap(A, j, j-1);
}
60
51
42
33
24
15
$i=1$
$i=2$
$i=3$
$i=4$
$i=5$
$n - 1$
$n - 1$

Saving...
Server Error
Resubmit

6.2.1.5. Analysis: Best Case¶

1 / 5 Settings
<<<>>>

Now we will consider the best case cost.

static <T extends Comparable<T>> void inssort(T[] A) {
for (int i=1; i<A.length; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--)
swap(A, j, j-1);
}
10
21
32
43
54
65
$i=1$
$i=2$
$i=3$
$i=4$
$i=5$
$n - 1$

Saving...
Server Error
Resubmit

6.2.1.6. Analysis: Average Case¶

1 / 8 Settings
<<<>>>

Finally, consider the average case cost.

static <T extends Comparable<T>> void inssort(T[] A) {
for (int i=1; i<A.length; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--)
swap(A, j, j-1);
}
0
1
...
i-1
i
...
n-1
$\displaystyle\sum_{i=1}^{n-1}\frac{i}{2}$
$n - 1$
$\displaystyle\sum_{i=1}^{n-1}\frac{i}{2} = \frac{n(n+1)}{4}$

Saving...
Server Error
Resubmit

6.2.1.7. Bubble Sort¶

1 / 13 Settings
<<<>>>

Moving from left to right, compare adjacent elements and swap if the left one is bigger than the right one.

200
101
152
543
554
115
786
147

Saving...
Server Error
Resubmit

1 / 10 Settings
<<<>>>

Moving from left to right, compare adjacent elements and swap if the left one is bigger than the right one.

100
151
202
543
114
555
146
787

Saving...
Server Error
Resubmit

6.2.1.8. Analysis¶

1 / 24 Settings
<<<>>>

What is the cost of Bubblesort?

static <T extends Comparable<T>> void bubblesort(T[] A) {
for (int i=0; i<A.length-1; i++) // Insert i'th record
for (int j=1; j<A.length-i; j++)
if (A[j-1].compareTo(A[j]) > 0)
swap(A, j-1, j);
}
40
161
52
153
134
85
$i = 0$
$i = 1$
$i = 2$
$i = 3$
$i = 4$
$n - 1$
$n - 1$

Saving...
Server Error
Resubmit

6.2.1.9. Selection Sort¶

1 / 15 Settings
<<<>>>

Moving from left to right, find the element with the greatest value.

200
101
152
543
554
115
786
147

Saving...
Server Error
Resubmit

1 / 13 Settings
<<<>>>

Second pass: moving from left to right, find the element with the second greatest value.

200
101
152
543
554
115
146
787

Saving...
Server Error
Resubmit

6.2.1.10. Analysis¶

1 / 40 Settings
<<<>>>

What is the cost for Selection Sort?

10
81
72
193
44
135
Number of Comparisons
Number of Swaps
Big-index
$i=0$
$i=0$
$i=1$
$i=1$
$i=2$
$i=2$
$i=3$
$i=3$
$i=4$
$i=4$
$n - 1$
$n - 1$
$n - 1$

Saving...
Server Error
Resubmit

6.2.1.11. Summary¶

$\begin{split}\begin{array}{rccc} &\textbf{Insertion}&\textbf{Bubble}&\textbf{Selection}\\ \textbf{Comparisons:}\\ \textrm{Best Case}&\Theta(n)&\Theta(n^2)&\Theta(n^2)\\ \textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\ \textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n^2)\\ \\ \textbf{Swaps:}\\ \textrm{Best Case}&0&0&\Theta(n)\\ \textrm{Average Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\ \textrm{Worst Case}&\Theta(n^2)&\Theta(n^2)&\Theta(n)\\ \end{array}\end{split}$

6.2.1.12. Code Tuning (1)¶

General strategy: Test to avoid work

Balance test cost, success probability, work saved

“Optimizations” for quadratic sorts:

Insertion Sort shift vs swaps: Works

Selection Sort viewed as an optimization of Bubble Sort: Works

Selection Sort avoid self-swaps: Does not work

Bubble Sort “i” vs “1”: Works

Bubble Sort count comparisons/avoid unnecessary iterations: Does not work

Bubble Sort O(n) best case claim: Bogus

6.2.1.13. Exchange Sorting¶

All of the sorts so far rely on exchanges of adjacent records: Inversions

1 / 16 Settings
<<<>>>

What is the average number of inversions?

$x_1$
$x_2$
$x_3$
...
$x_{n-1}$
$x_n$
$L$
$x_n$
$x_{n-1}$
...
$x_3$
$x_2$
$x_1$
$L_R$
3
4
1
2
2
1
4
3

Saving...
Server Error
Resubmit

DSA Coursenotes

Chapter 6 Week 7

6.2. Sorting: Quadratic Sorts¶

6.2.1. Quadratic Sorts¶

6.2.1.1. Sorting¶

6.2.1.2. Insertion Sort¶

6.2.1.3. Initial Step¶

6.2.1.4. Analysis: Worst Case¶

6.2.1.5. Analysis: Best Case¶

6.2.1.6. Analysis: Average Case¶

6.2.1.7. Bubble Sort¶

6.2.1.8. Analysis¶

6.2.1.9. Selection Sort¶

6.2.1.10. Analysis¶

6.2.1.11. Summary¶

6.2.1.12. Code Tuning (1)¶

6.2.1.13. Exchange Sorting¶