06: sorting #1

Bubble Sort | Insertion Sort | Selection Sort | Shell Sort | Best Sorting Complexity
Sort Performances | Mergesort | Heapsort | Smoothsort

Sorting

A sorting algorithm takes any ordered input and makes the output either ascending or descending order (or some other set specified order).
  • Input Sequence: (5, 8, 1, 2, 20)
  • Ascending Order: (1, 2, 5, 8, 20)
  • Descending Order: (20, 8, 5, 2, 1)
General purpose sorting code usually depends on the user of the library to specify the order criteria.

Bubble Sort

  • Worst Case Time Complexity: O(n^2)

  • Best Case Time Complexity: O(n)
    • When does this happen?

  • Average Case Time Complexity: O(n^2)

  • Worst Case Space Complexity: O(1) auxiliary

Basic Bubble Sort (does not have O(n) best case time complexity)
1:  
// bubbleSort.cpp - download here

2:  

3:  
void
 
bubbleSort(
int
 
array, 
int
 
n)
{

4:  
 
 
for
(
int
 
=
 
0;
 
<
 
n;
 
++i)
{

5:  
 
 
 
 
for
(
int
 
=
 
1;
 
<
 
n;
 
++j)
{

6:  
 
 
 
 
 
 
int
 
lhs 
=
 
array[
i]
;

7:  
 
 
 
 
 
 
int
 
rhs 
=
 
array[
j]
;

8:  
 
 
 
 
 
 
if
(
rhs 
<
 
lhs)
{

9:  
 
 
 
 
 
 
 
 
array[
i]
 
=
 
rhs;

10: 
 
 
 
 
 
 
 
 
array[
j]
 
=
 
lhs;

11: 
 
 
 
 
 
 
}

12: 
 
 
 
 
}

13: 
 
 
}

14: 
}


A Bubble Sort that breaks out early if sorted (does have O(n) best case time complexity)
1:  
// bubbleSort2.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  
#include
 
<
vector>

5:  

6:  
void
 
swap(
std:
:
vector<
int
>
&
 
a, 
int
 
index1, 
int
 
index2)
{

7:  
 
 
int
 
lhs 
=
 
a[
index1]
;

8:  
 
 
int
 
rhs 
=
 
a[
index2]
;

9:  
 
 
a[
index1]
 
=
 
rhs;

10: 
 
 
a[
index2]
 
=
 
lhs;

11: 
}

12: 

13: 
void
 
bubbleSort2(
std:
:
vector<
int
>
&
 
a)
{

14: 
 
 
bool
 
swapped 
=
 
true;

15: 
 
 
while
(
swapped)
{

16: 
 
 
 
 
swapped 
=
 
false;

17: 
 
 
 
 
for
(
size_t
 
=
 
1;
 
<
 
a.size(
)
;
 
++i)
{

18: 
 
 
 
 
 
 
if
(
a[
1]
 
>
 
a[
i]
)
{

19: 
 
 
 
 
 
 
 
 
swap(
a, 
i-1, 
i)
;

20: 
 
 
 
 
 
 
 
 
swapped 
=
 
true;

21: 
 
 
 
 
 
 
}

22: 
 
 
 
 
}

23: 
 
 
}

24: 
}

25: 

26: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

27: 

28: 
 
 
std:
:
vector<
int
>
 
array;

29: 
 
 
array.push_back(
10)
;

30: 
 
 
array.push_back(
5)
;

31: 
 
 
array.push_back(
15)
;

32: 
 
 
array.push_back(
7)
;

33: 
 
 
array.push_back(
1)
;

34: 

35: 
 
 
bubbleSort2(
array)
;

36: 
 
 

37: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
array.size(
)
;
 
++i)
{

38: 
 
 
 
 
std:
:
cout 
<
<
 
array[
i]
 
<
<
 
" "
;

39: 
 
 
}

40: 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

41: 
 
 
//prints: 1 5 7 10 15 

42: 

43: 
 
 
return
 
0;

44: 
}


Optimizing Bubble Sort.
1:  
// bubbleSort3.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  
#include
 
<
vector>

5:  

6:  
void
 
swap(
std:
:
vector<
int
>
&
 
a, 
int
 
index1, 
int
 
index2)
{

7:  
 
 
int
 
lhs 
=
 
a[
index1]
;

8:  
 
 
int
 
rhs 
=
 
a[
index2]
;

9:  
 
 
a[
index1]
 
=
 
rhs;

10: 
 
 
a[
index2]
 
=
 
lhs;

11: 
}

12: 

13: 
void
 
bubbleSort3(
std:
:
vector<
int
>
&
 
a)
{

14: 
 
 
size_t
 
n, 
newn;

15: 
 
 
=
 
a.size(
)
;

16: 
 
 
while
(
>
 
0)
{

17: 
 
 
 
 
newn 
=
 
0;

18: 
 
 
 
 
for
(
size_t
 
=
 
1;
 
<
 
n;
 
++i)
{

19: 
 
 
 
 
 
 
if
(
a[
1]
 
>
 
a[
i]
)
{

20: 
 
 
 
 
 
 
 
 
swap(
a, 
i-1, 
i)
;

21: 
 
 
 
 
 
 
 
 
newn 
=
 
i;

22: 
 
 
 
 
 
 
}

23: 
 
 
 
 
}

24: 
 
 
 
 
=
 
newn;

25: 
 
 
}

26: 
}

27: 

28: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

29: 

30: 
 
 
std:
:
vector<
int
>
 
array;

31: 
 
 
array.push_back(
10)
;

32: 
 
 
array.push_back(
5)
;

33: 
 
 
array.push_back(
15)
;

34: 
 
 
array.push_back(
7)
;

35: 
 
 
array.push_back(
1)
;

36: 

37: 
 
 
bubbleSort3(
array)
;

38: 
 
 

39: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
array.size(
)
;
 
++i)
{

40: 
 
 
 
 
std:
:
cout 
<
<
 
array[
i]
 
<
<
 
" "
;

41: 
 
 
}

42: 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

43: 
 
 
//prints: 1 5 7 10 15 

44: 

45: 
 
 
return
 
0;

46: 
}

Bubble Sort In Practice

  • Even though both Bubble Sort and Insertion Sort have the same asymptotic running time, experimental evidence shows that Insertion Sort performs much better on random lists [1]

Bubble Sort Quote [2]

When campaigning at Google, future President Burack Obama was asked: "What is the most efficient way to sort a million 32-bit integers?"

He replied: "I think bubble sort would be the wrong way to go".

Eric Schmidt replied: "C'mon, who told him that?"

Insertion Sort

Insertion sort maintains the invarient that everything in the array at indicies less than j is sorted. Each insert loop starts at the key index and copies new items right until the new item is less than the key.
  • Worst Case Time Complexity: O(n^2)

  • Best Case Time Complexity: O(n)
    • When does this happen?

  • Average Case Time Complexity: O(n^2)

  • Worst Case Space Complexity: O(1) auxiliary

Insertion Sort Invarient

insert-before


insert-before

(images from wikipedia [3])

Insertion Sort Code
1:  
// insertionSort.cpp - download here

2:  

3:  
// array - the unsorted input array

4:  
// len   - the length of the unsorted input array

5:  
// the result is stored in array 

6:  
void
 
insertionSort(
int
 
array, 
int
 
len)
{

7:  
 
 
for
(
int
 
=
 
1;
 
<
 
len;
 
++j)
{

8:  
 
 
 
 
int
 
key 
=
 
array[
j]
;

9:  
 
 
 
 
int
 
=
 
1;

10: 
 
 
 
 
//insert key into sorted sequence

11: 
 
 
 
 
while
(
(
>
=
 
0)
 
&
&
 
(
array[
i]
 
>
 
key)
)

12: 
 
 
 
 
 
 
array[
1]
 
=
 
array[
i]
;

13: 
 
 
 
 
 
 
--i;

14: 
 
 
 
 
}

15: 
 
 
 
 
array[
1]
 
=
 
key;

16: 
 
 
}

17: 
}

Input Sequence:
8
2
4
9
3
6




2
8
4
9
3
6




2
4
8
9
3
6




2
4
8
9
3
6




2
3
4
8
9
6




Sorted Sequence:
2
3
4
6
8
9




Analysis of Insertion Sort [3]

  • Running time depends on input sequence
    • If input is sorted, there is not much work to do
    • If input is reverse-sorted, there is a lot of work to do
  • Running time also depends on input sequence size

Analysis of Insertion Sort

  • Worst case: Input Reverse Sorted

  • T(n) =

  • If len = 6,
  • T(n) = Ɵ(6) + Ɵ(5) + Ɵ(4) + Ɵ(3) + Ɵ(2) + Ɵ(1)
  • T(n) = Ɵ(n) + Ɵ(n-1) + Ɵ(n-2) + Ɵ(n-3) + Ɵ(n-4) + Ɵ(n-5)

  • This is an arithmetic progression
  • The summation of an arithmatic progression is:
  • Sum = n*(a1 + an)/2, where: a1 := 1, an := len, n := len
  • Sum = len*(1 + len)/2 = (len^2 + len)/2
  • Sum = c1*len^2 + c2*len, where: c1 := 1/2 and c2 := 1/2

  • Drop Lower and Constant Terms
  • T(n) = Ɵ(len^2)
  • T(n) = Ɵ(n^2)
Other properties of insertion sort:
  • Good for data sets that are already mostly sorted
  • Stable
  • In-place
  • Online: can sort a list as it receives it. Can place the element at the end of the array and sort once to add a single element.

Selection Sort

Selection sort first finds the smallest element and places it in the 0th position. It then finds the second smallest and places it in the 1st position, and so on.

It has O(n^2) worst/best/avg time complexity, but can be done faster with many cores (or on GPUs)

1:  
// selectionSort.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  
#include
 
<
vector>

5:  

6:  
void
 
swap(
std:
:
vector<
int
>
&
 
a, 
int
 
index1, 
int
 
index2)
{

7:  
 
 
int
 
lhs 
=
 
a[
index1]
;

8:  
 
 
int
 
rhs 
=
 
a[
index2]
;

9:  
 
 
a[
index1]
 
=
 
rhs;

10: 
 
 
a[
index2]
 
=
 
lhs;

11: 
}

12: 

13: 
void
 
selectionSort(
std:
:
vector<
int
>
&
 
a)
{

14: 
 
 
size_t
 
j, 
least;

15: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
(
a.size(
)
 
1)
;
 
++i)
{

16: 
 
 
 
 
for
(
=
 
1, 
least 
=
 
i;
 
<
 
a.size(
)
;
 
++j)
{

17: 
 
 
 
 
 
 
if
(
a[
j]
 
<
 
a[
least]
)
{

18: 
 
 
 
 
 
 
 
 
least 
=
 
j;

19: 
 
 
 
 
 
 
}

20: 
 
 
 
 
}

21: 
 
 
 
 
swap(
a, 
least, 
i)
;

22: 
 
 
}

23: 
}

24: 

25: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

26: 

27: 
 
 
std:
:
vector<
int
>
 
array;

28: 
 
 
array.push_back(
10)
;

29: 
 
 
array.push_back(
5)
;

30: 
 
 
array.push_back(
15)
;

31: 
 
 
array.push_back(
7)
;

32: 
 
 
array.push_back(
1)
;

33: 

34: 
 
 
selectionSort(
array)
;

35: 
 
 

36: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
array.size(
)
;
 
++i)
{

37: 
 
 
 
 
std:
:
cout 
<
<
 
array[
i]
 
<
<
 
" "
;

38: 
 
 
}

39: 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

40: 
 
 
//prints: 1 5 7 10 15 

41: 

42: 
 
 
return
 
0;

43: 
}

  • Input Sequence:

    8
    2
    4
    9
    3
    6
    10
    5




  • Swap 0th Smallest:

    2
    8
    4
    9
    3
    6
    10
    5




  • Swap 1st Smallest:

    2
    3
    4
    9
    8
    6
    10
    5




  • Swap 2nd Smallest (do nothing here):

    2
    3
    4
    9
    8
    6
    10
    5




  • Swap 3rd Smallest:

    2
    3
    4
    5
    8
    6
    10
    9




  • Swap 4th Smallest:

    2
    3
    4
    5
    6
    8
    10
    9




  • Swap 5th Smallest (do nothing here):

    2
    3
    4
    5
    6
    8
    10
    9




  • Swap 6th Smallest (done):

    2
    3
    4
    5
    6
    8
    9
    10




Analysis of Selection Sort

  • Selection sort has two for loops that are bounded proportional to n

  • lec06_01 = (n - 1) + (n - 2) + (n - 3) + ... + 1
  • lec06_01 = n(n - 1) / 2
  • lec06_01 = O(n^2)

Shell Sort

Shell Sort divides the collection into h partitions and sorts the sub-collections (usually with bubble sort or insertion sort).
1:  
// shellSort.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  
#include
 
<
vector>

5:  

6:  
void
 
insertionSort(
int
 
inc, 
int
 
start, 
std:
:
vector<
int
>
&
 
data)
{

7:  
 
 
for
(
int
 
key_index 
=
 
start;
 
key_index 
<
 
data.size(
)
;
 
key_index 
+=
 
inc)
{

8:  
 
 
 
 
int
 
key 
=
 
data[
key_index]
;

9:  
 
 
 
 
int
 
other_index 
=
 
key_index 
inc;

10: 
 
 
 
 
while
(
other_index 
>
=
 
&
&
 
data[
other_index]
 
>
 
key)
{

11: 
 
 
 
 
 
 
data[
other_index 
inc]
 
=
 
data[
other_index]
;

12: 
 
 
 
 
 
 
other_index 
-=
 
inc;

13: 
 
 
 
 
}

14: 
 
 
 
 
data[
other_index 
inc]
 
=
 
key;

15: 
 
 
}

16: 
}

17: 

18: 
void
 
shellSort(
std:
:
vector<
int
>
&
 
data)
{

19: 
 
 
std:
:
vector<
int
>
 
increments;

20: 
 
 
//produce the h's

21: 
 
 
for
(
int
 
=
 
1;
 
<
 
data.size(
)
;
 
)
{

22: 
 
 
 
 
increments.push_back(
h)
;

23: 
 
 
 
 
=
 
(
h)
 
1;

24: 
 
 
}

25: 
 
 
//loop over the different h's

26: 
 
 
for
(
int
 
=
 
increments.size(
)
 
1;
 
>
=
 
0;
 
--i)
{

27: 
 
 
 
 
int
 
=
 
increments[
i]
;

28: 
 
 
 
 
//loop over the number of sub-arrays produced by the current h

29: 
 
 
 
 
for
(
int
 
start 
=
 
0;
 
start 
<
=
 
h;
 
++start)
{

30: 
 
 
 
 
 
 
insertionSort(
h, 
start, 
data)
;

31: 
 
 
 
 
}

32: 
 
 
}

33: 
}

34: 

35: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

36: 

37: 
 
 
std:
:
vector<
int
>
 
array;

38: 
 
 
array.push_back(
10)
;

39: 
 
 
array.push_back(
5)
;

40: 
 
 
array.push_back(
15)
;

41: 
 
 
array.push_back(
7)
;

42: 
 
 
array.push_back(
1)
;

43: 
 
 
array.push_back(
6)
;

44: 
 
 
array.push_back(
8)
;

45: 
 
 
array.push_back(
3)
;

46: 
 
 
array.push_back(
2)
;

47: 
 
 
array.push_back(
4)
;

48: 
 
 
array.push_back(
16)
;

49: 
 
 
array.push_back(
12)
;

50: 
 
 
array.push_back(
13)
;

51: 
 
 
array.push_back(
11)
;

52: 
 
 
array.push_back(
9)
;

53: 
 
 
array.push_back(
14)
;

54: 
 
 
array.push_back(
17)
;

55: 

56: 
 
 
shellSort(
array)
;

57: 

58: 
 
 
for
(
size_t
 
=
 
0;
 
<
 
array.size(
)
;
 
++i)
{

59: 
 
 
 
 
std:
:
cout 
<
<
 
array[
i]
 
<
<
 
" "
;

60: 
 
 
}

61: 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

62: 
 
 
//prints: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

63: 

64: 
 
 
return
 
0;

65: 
}

66: 

  • Input Sequence (h = 13):

    10
    5
    15
    7
    9
    6
    8
    14
    2
    17
    16
    12
    13
    0
    1
    3
    4




  • Insertion Sort with h = 13:

    0
    1
    3
    4
    9
    6
    8
    14
    2
    17
    16
    12
    13
    10
    5
    15
    7




  • Divide array into partitions of size h = 4;

    0
    1
    3
    4
    9
    6
    8
    14
    2
    17
    16
    12
    13
    10
    5
    15
    7




  • Insertion Sort with h = 4

    0
    1
    3
    4
    2
    6
    5
    12
    7
    10
    8
    14
    9
    17
    16
    15
    13




  • Divide array into partitions of size h = 1

    0
    1
    3
    4
    2
    6
    5
    12
    7
    10
    8
    14
    9
    17
    16
    15
    13




  • Insertion Sort with size h = 1

    0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    12
    13
    14
    15
    16
    17




Notes about Shell Sort

  • Empirical studies have shown that h=3h+1 is a good choice for the increments
  • The time complexity of shell sort for any increment function is an open problem in computer science
  • Shell Sort usually performs more operations and has a higher cache miss ratio than quicksort. However it does not use a call stack so in embedded systems and in the linux kernel shell sort can be used instead of quicksort. [1]

What is the lower bound on the worst case time complexity of a sorting algorithm?

  • Here we are concerned with the number of comparisons
A decision tree for insertion sort applied the the array [a b c]:

DecisionTree
  • Left nodes: TRUE
  • Right nodes: FALSE
The number of leaves for a sorting algorithm is never less than n!.
Since each step walking down the decision tree is a binary choice, the minimum time complexity for a comparison sorting algorithm is O(lg(n!)).

According to Drozdek, O(lg(n!)) grows at the same rate as O(nlg(n)), therefore the minimum number of comparisons to sort any random input using a comparison sort is: O(n*lg(n)).

A faster sort: Merge Sort

The Merge Sort algorithm is as follows:
  1. Divide the given unsorted list into two parts, each half the size
  2. Sort each sublist recursively using merge sort. Stop the recursion when the input list size is 1
  3. Merge the two sublists back into one sorted list
1:  
// mergeSort.cpp - download here

2:  

3:  
#include
 
<
iostream>

4:  

5:  
int
 
merge(
int
 
left, 
int
 
right, 
int
 
len)
{

6:  
 
 
int
 
ret 
=
 
new
 
int
[
len 
len]
;

7:  
 
 
int
 
left_position 
=
 
0;

8:  
 
 
int
 
right_position 
=
 
0;

9:  
 
 
int
 
ret_position 
=
 
0;

10: 
 
 
while
(
left_position 
<
 
len 
&
&
 
right_position 
<
 
len)
{

11: 
 
 
 
 
int
 
left_value 
=
 
left[
left_position]
;

12: 
 
 
 
 
int
 
right_value 
=
 
right[
right_position]
;

13: 
 
 
 
 
if
(
left_value 
<
 
right_value)
{

14: 
 
 
 
 
 
 
ret[
ret_position]
 
=
 
left_value;

15: 
 
 
 
 
 
 
ret_position++;

16: 
 
 
 
 
 
 
left_position++;

17: 
 
 
 
 
}
 
else
 
{

18: 
 
 
 
 
 
 
ret[
ret_position]
 
=
 
right_value;

19: 
 
 
 
 
 
 
ret_position++;

20: 
 
 
 
 
 
 
right_position++;

21: 
 
 
 
 
}

22: 
 
 
}

23: 
 
 
while
(
left_position 
<
 
len)
{

24: 
 
 
 
 
ret[
ret_position]
 
=
 
left[
left_position]
;

25: 
 
 
 
 
ret_position++;

26: 
 
 
 
 
left_position++;

27: 
 
 
}

28: 
 
 
while
(
right_position 
<
 
len)
{

29: 
 
 
 
 
ret[
ret_position]
 
=
 
right[
right_position]
;

30: 
 
 
 
 
ret_position++;

31: 
 
 
 
 
right_position++;

32: 
 
 
}

33: 
 
 
return
 
ret;

34: 
}

35: 

36: 
int
 
mergeSort(
int
 
input, 
int
 
len)
{

37: 
 
 
if
(
len 
=
=
 
1)
{

38: 
 
 
 
 
return
 
input;

39: 
 
 
}

40: 
 
 
int
 
middle 
=
 
len 
2;

41: 
 
 
int
 
left 
=
 
new
 
int
[
middle]
;

42: 
 
 
int
 
right 
=
 
new
 
int
[
middle]
;

43: 
 
 
for
(
int
 
=
 
0;
 
<
 
middle;
 
++i)
{

44: 
 
 
 
 
left[
i]
 
=
 
input[
i]
;

45: 
 
 
}

46: 
 
 
for
(
int
 
=
 
0;
 
<
 
middle;
 
++i)
{

47: 
 
 
 
 
right[
i]
 
=
 
input[
i+middle]
;

48: 
 
 
}

49: 
 
 
left 
=
 
mergeSort(
left, 
middle)
;

50: 
 
 
right 
=
 
mergeSort(
right, 
middle)
;

51: 
 
 
int
 
ret 
=
 
merge(
left, 
right, 
middle)
;

52: 
 
 
delete
 
[
]
 
left;

53: 
 
 
delete
 
[
]
 
right;

54: 
 
 
return
 
ret;

55: 
}

56: 

57: 
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

58: 

59: 
 
 
int
 
array 
=
 
new
 
int
[
8]
;

60: 
 
 
array[
0]
 
=
 
8;

61: 
 
 
array[
1]
 
=
 
2;

62: 
 
 
array[
2]
 
=
 
4;

63: 
 
 
array[
3]
 
=
 
9;

64: 
 
 
array[
4]
 
=
 
3;

65: 
 
 
array[
5]
 
=
 
6;

66: 
 
 
array[
6]
 
=
 
10;

67: 
 
 
array[
7]
 
=
 
5;

68: 

69: 
 
 
int
 
sorted 
=
 
mergeSort(
array, 
8)
;

70: 
 
 
for
(
int
 
=
 
0;
 
<
 
8;
 
++i)
{

71: 
 
 
 
 
std:
:
cout 
<
<
 
sorted[
i]
 
<
<
 
" "
;

72: 
 
 
}

73: 
 
 
std:
:
cout 
<
<
 
std:
:
endl;

74: 

75: 
 
 
return
 
0;

76: 
}

Input Sequence:
8
2
4
9
3
6
10
5




Recurse:
8
2
4
9
 
3
6
10
5




Recurse:
8
2
 
4
9
 
3
6
 
10
5




Recurse:
8
 
2
 
4
 
9
 
3
 
6
 
10
 
5




Merge:
2
8
 
4
9
 
3
6
 
5
10




Merge:
2
4
8
9
 
3
5
6
10




Sorted Sequence:
2
3
4
5
6
8
9
10




Analysis of Merge Sort

Recurance:

lec06_02

Omit base case that is constant time:
  • T(n) = 2T(n/2) + Ɵ(n)

Recusion Tree:
RecursionTree

What is the height of this tree?
What is the number of leaves in this tree?

The total ammount of work is:
  • T(n) = work_at_each_level * number_of_levels
  • T(n) = Ɵ(nlg(n))
If you run insertion sort versus merge sort for sufficiently large input with insertion on a super computer and merge sort on a regular laptop, the laptop will win. Insertion sort has been found to be faster than merge sort for element sizes approximately less than 30 because of the constant times. [4]

Sort performance comparisons

(each sort was executed 100 times)


Heap Sort

Heap sort is a worst case O(nlg(n)) algorithm that takes no additional space.

The algorithm is as follows:
  1. Create a heap in place by calling fixDown from the back of the array to the front
  2. Repeatedly exchange the largest element with the back of the array and call fixDown from the new root
1:  
algorithm
 
fixDown(
array 
d, 
int
 
k, 
int
 
size)

2:  
 
 
while
 
leftChild(
k)
 
<= 
size

3:  
 
 
 
 
leftChild(
k)
;

4:  
 
 
 
 
if
 
there 
is 
right 
child 
and 
the 
right 
child 
is 
larger

5:  
 
 
 
 
 
 
rightChild(
k)

6:  
 
 
 
 
if
 
d[
k]
 
is 
less 
than 
d[
j]

7:  
 
 
 
 
 
 
exchange(
d[
k]
d[
j]
)

8:  
 
 
 
 
j;

9:  

10: 
algorithm
 
createHeap(
array 
d)

11: 
 
 
for
 
d.length 
to 
0

12: 
 
 
 
 
fixDown(
d, 
i, 
d.length)

13: 
 
 

14: 
algorithm
 
heapSort(
array 
d)

15: 
 
 
createHeap(
d)
;

16: 
 
 
for
 
d.length 
to 
1

17: 
 
 
 
 
exchange(
d[
0]
d[
i]
)
;

18: 
 
 
 
 
fixDown(
d, 
0, 
i)
;

19: 

  1. Start
    HeapSort
  2. Build Heap 1
    HeapSort
  3. Build Heap 2
    HeapSort
  4. Build Heap 3
    HeapSort
  5. Build Heap 4
    HeapSort
  6. Exchange 1
    HeapSort
  7. fixDown 1
    HeapSort
  8. Exchange 2
    HeapSort
  9. fixDown 2
    HeapSort
  10. Exchange 3
    HeapSort
  11. fixDown 3
    HeapSort
  12. Exchange 4
    HeapSort
  13. fixDown 4
    HeapSort
  14. Exchange 5
    HeapSort
  15. ... Final Result
    HeapSort

Smoothsort [1]

Smoothsort uses Leonardo heaps instead of binary heaps and operates similar to heapsort.
  • L(0) = 1
  • L(1) = 1
  • L(n+2) = L(n) + L(n+1) + 1
L(n) = 1, 1, 3, 5, 9, 15, 25, 41, 67, 109

Smoothsort is worst case O(nlgn) like heapsort but O(n) when the input is sorted

Algorithm with unsorted data:
  • Start:
    Smoothsort
  • Increase Size By One:
    Smoothsort
  • Increase Size By One and Selection Sort the Roots:
    Smoothsort
  • Increase Size By One and Merge:
    Smoothsort
  • Increase Size By One, Selection Sort and Push Down:
    Smoothsort
  • Increase Size By One, Merge and Push Down:
    Smoothsort
  • Increase Size By One, Selection Sort the Roots and Push Down:
    Smoothsort
  • Increase Size By One, Selection Sort the Roots and Push Down:
    Smoothsort
  • Increase Size By One, Push Down, Selection Sort the Roots and Push Down:
    Smoothsort
  • Increase Size By One, Push Down:
    Smoothsort
  • Increase Size By One, Selection Sort the Roots:
    Smoothsort
  • Decrease Size By One:
    Smoothsort
  • Decrease Size By One:
    Smoothsort
  • Decrease Size By One, Selection Sort the Roots and Push Down:
    Smoothsort
  • Decrease Size By Three, Selection Sort the Roots and Push Down:
    Smoothsort
  • Decrease Size and selection sort the roots:
    Smoothsort
  • Sort Complete:
    Smoothsort

References

  1. http://en.wikipedia.org/wiki/Bubble_sort
  2. http://overstated.net/2008/02/11/obama-not-bubble-sort
  3. http://en.wikipedia.org/wiki/Insertion_sort
  4. Leiserson, Charles, and Erik Demaine. 6.046J Introduction to Algorithms (SMA 5503), Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed 14 Nov, 2011). License: Creative Commons BY-NC-SA
  5. http://en.wikipedia.org/wiki/Arithmetic_series
  6. http://en.wikipedia.org/wiki/Merge_sort
  7. http://en.wikipedia.org/wiki/Category:Stable_sorts