Searching, Sorting and Merging
Sorting Algorithms
animations of algorithms
Lecture 26
Data Structures and Abstractions
*
Bubble Sort
Bubble sort is the most commonly coded of the simple sorts.
It is a stable exchange sort.
Whilst not particularly fast—O(n2)—it is very simple to code and easy to understand.
For anything less than 1000 items, bubble sort is fine.
Its name derives from the fact that large numbers ‘bubble’ to the ‘top’ of the container.
*
Bubble Sort Algorithm
ArrayBubbleSort
integer target, lastSwap
boolean swapDone, sortDone
Initialise lastSwap to 0
Initialise sortDone to false
IF array size > 1
target = size-1
WHILE not sortDone
swapDone = false
FOR index = 0 to target-1
IF element[index] > element[index+1]
Swap them
lastSwap = index
swapDone = true
ENDIF
ENDFOR
sortDone = not swapDone
target = lastSwap
ENDWHILE
ENDIF
END BubbleSort
*
Bubble Sort Animation
2
9
0
7
8
6
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
9
0
7
8
6
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
9
7
8
6
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
9
7
8
6
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
9
8
6
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
9
8
6
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
9
6
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
9
6
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
9
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
9
5
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
9
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
9
1
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
1
9
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
1
9
4
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
1
4
9
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
1
4
9
3
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
2
0
7
8
6
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
0
2
7
8
6
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
0
2
7
8
6
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
8
6
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
8
6
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
8
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
8
5
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
8
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
8
1
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
8
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
8
4
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
4
8
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
4
8
3
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
7
6
5
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
7
5
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
7
5
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
7
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
7
1
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
7
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
7
4
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
4
7
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
4
7
3
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
6
5
1
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
6
1
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
6
1
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
6
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
6
4
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
4
6
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
4
6
3
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
4
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
4
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
4
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
4
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
5
1
4
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
1
5
4
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
1
5
4
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
1
4
5
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
1
4
5
3
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
1
4
3
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
1
4
3
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
1
4
3
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
2
1
4
3
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
4
3
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
4
3
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
4
3
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
3
4
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
3
4
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
3
4
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
3
4
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
3
4
5
6
7
8
9
index
target
lastSwap
*
Bubble Sort Animation
* of 234
0
1
2
3
4
5
6
7
8
9
Done!!
index
target
lastSwap
*
Merge Sort
Merge sort is a divide and conquer sort.
It has complexity O(log n) on average and O(n2) in the worst case.
It is a simple merge to implement.
It is most easily implemented using recursion.
It is the only efficient sort to implement for a large amount of data on disk (that does not fit into RAM).
* of 234
*
Merge Sort Algorithm
MergeSort
IF there are more than two elements in the container
Divide the container into two
Merge Sort the first part // call again
Merge Sort the second part // call again
Merge the two sorted parts into a temp file
Put merged temp array back into array being sorted
ELSE IF two elements in the container
Swap them if necessary
ENDIF
END MergeSort
* of 234
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
in order
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
in order
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
in order
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
0
in order
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
0
in order
in order
*
Merge Sort Animation
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
0
in order
in order
7
8
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
0
in order
in order
7
8
in order
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
0
in order
7
8
merge back
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
0
in order
7
8
merge back
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
in order
merge back
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
9
0
7
8
2
9
0
7
8
in order
0
2
7
8
9
merge back
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
6
5
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
4
3
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
4
3
1
in order
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
4
3
1
in order
4
3
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
4
3
1
in order
3
4
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
4
3
1
3
4
merge
back
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
4
3
1
3
4
merge
back
3
4
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
3
4
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
3
4
merge
back
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
5
6
1
3
4
merge
back
6
5
1
4
3
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
*
Merge Sort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
2
7
8
9
merge
back
6
5
1
4
3
0
2
7
8
9
6
5
1
4
3
*
Merge Sort Animation
* of 234
0
2
7
8
9
6
5
1
4
3
Done!!
*
The Abstract Heap
A ‘heap’ is a data structure in the form of a binary tree.
A binary tree is one where each node contains data plus 0-2 pointers to nodes underneath it.
* of 234
A heap is a binary tree where the data in a node is guaranteed to be either less than (a min heap) or greater than (a max heap) all of the data below it.
4
5
9
8
6
7
*
The Actual Heap
Clearly such a structure can be used to sort data.
However, in actual fact, the data structure used is simply another array.
This is because we end up doing a lot of data swapping in a heap, which is difficult to code in an actual tree.
Also it turns out that in an array, the parent-child relationships is mathematical, making swaps particularly easy.
* of 234
*
Abstract View vs Actual View
* of 234
9
7
8
6
5
4
4
5
9
8
6
7
*
Abstract View vs Actual View
* of 234
9
7
8
6
5
4
5
4
3
2
1
0
parentIndex = (childIndex – 1) / 2
4
5
9
8
6
7
*
Abstract View vs Actual View
* of 234
9
7
8
6
5
4
5
4
3
2
1
0
childIndex1 = parentIndex * 2 + 1 [1]
childIndex2 = parentIndex * 2 + 2
4
5
9
8
6
7
*
[1] formula for converting array to tree location
Heap Sort Algorithm
* of 234
Heap sort is an unstable selection sort.
It utilises a greedy algorithmic technique.
It has complexity O(log n).
But is more complicated to code than a merge sort.
*
Heap Sort Algorithm
HeapSort
FOR each member of the array
Place it at the bottom end of the heap
WHILE it is smaller than the parent
Exchange it with the parent
ENDWHILE
ENDFOR
index = 0
WHILE the heap is not empty
Put the top of the heap at index in the array
Increment index
Delete the top of the heap
ENDWHILE
END HeapSort
* of 234
Put on the heap
Take off the heap
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
Actual Heap
Abstract Heap
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
Actual Heap
Abstract Heap
2
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
Actual Heap
Abstract Heap
9
Inserts go at left-most bottom row
2
9
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
2
Actual Heap
Abstract Heap
9
0
Inserts go at left-most bottom row
2
9
0
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
Actual Heap
Abstract Heap
9
2
Values then ‘percolate’ up if smaller
0
9
2
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
9
2
7
Actual Heap
Abstract Heap
9
2
7
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
7
2
9
Actual Heap
Abstract Heap
7
2
9
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
7
2
9
8
Actual Heap
Abstract Heap
7
2
9
8
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
7
2
9
8
6
Actual Heap
Abstract Heap
7
2
9
8
6
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
7
2
9
8
6
5
Actual Heap
Abstract Heap
7
2
9
8
6
5
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
7
2
9
8
6
5
1
Actual Heap
Abstract Heap
7
2
9
8
6
5
1
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
7
2
1
8
6
5
9
Actual Heap
Abstract Heap
7
2
1
8
6
5
9
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
1
2
7
8
6
5
9
Actual Heap
Abstract Heap
1
2
7
8
6
5
9
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
1
2
7
8
6
5
9
4
Actual Heap
Abstract Heap
1
2
7
8
6
5
9
4
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
1
2
4
8
6
5
9
7
Actual Heap
Abstract Heap
1
2
4
8
6
5
9
7
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
1
2
4
8
6
5
9
7
3
Actual Heap
Abstract Heap
1
2
4
8
6
5
9
7
3
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
1
2
4
3
6
5
9
7
8
Actual Heap
Abstract Heap
1
2
4
3
6
5
9
7
8
*
Heap Insert Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
1
2
4
3
6
5
9
7
8
Actual Heap
Abstract Heap
1
2
4
3
6
5
9
7
8
*
Heap Delete Animation
* of 234
2
9
0
7
8
6
5
1
4
3
0
0
1
2
4
3
6
5
9
7
8
Actual Heap
Abstract Heap
1
2
4
3
6
5
9
7
8
*
Heap Delete Animation
* of 234
0
9
0
7
8
6
5
1
4
3
0
0
1
2
4
3
6
5
9
7
8
Actual Heap
Abstract Heap
1
2
4
3
6
5
9
7
8
The top value goes onto the next space in the array
*
Heap Delete Animation
* of 234
0
9
0
7
8
6
5
1
4
3
1
1
1
2
4
3
6
5
9
7
8
Actual Heap
Abstract Heap
1
2
4
3
6
5
9
7
8
The smallest value below then moves upwards
*
Heap Delete Animation
* of 234
0
9
0
7
8
6
5
1
4
3
1
1
3
2
4
3
6
5
9
7
8
Actual Heap
Abstract Heap
3
2
4
3
6
5
9
7
8
And again
*
Heap Delete Animation
* of 234
0
9
0
7
8
6
5
1
4
3
1
1
3
2
4
8
6
5
9
7
8
Actual Heap
Abstract Heap
3
2
4
8
6
5
9
7
8
And again
*
Heap Delete Animation
* of 234
0
9
0
7
8
6
5
1
4
3
1
1
3
2
4
8
6
5
9
7
Actual Heap
Abstract Heap
3
2
4
8
6
5
9
7
As we just moved the value in the right-most bottom node upwards, we simply ‘delete’ that node
*
Heap Delete Animation
* of 234
0
1
0
7
8
6
5
1
4
3
1
1
3
2
4
8
6
5
9
7
Actual Heap
Abstract Heap
3
2
4
8
6
5
9
7
The top value goes onto the next space in the array
*
Heap Delete Animation
* of 234
0
1
0
7
8
6
5
1
4
3
2
2
3
2
4
8
6
5
9
7
Actual Heap
Abstract Heap
3
2
4
8
6
5
9
7
The smallest value below then moves upwards
*
Heap Delete Animation
* of 234
0
1
0
7
8
6
5
1
4
3
2
2
3
5
4
8
6
5
9
7
Actual Heap
Abstract Heap
3
5
4
8
6
5
9
7
And again
*
Heap Delete Animation
* of 234
0
1
0
7
8
6
5
1
4
3
2
2
3
5
4
8
6
7
9
7
Actual Heap
Abstract Heap
3
5
4
8
6
7
9
7
The value in the right-most bottom row, now moves into this free node
*
Heap Delete Animation
* of 234
0
1
0
7
8
6
5
1
4
3
2
2
3
5
4
8
6
7
9
Actual Heap
Abstract Heap
3
5
4
8
6
7
9
And the right-most bottom node is ‘deleted’
*
Heap Delete Animation
* of 234
0
1
2
7
8
6
5
1
4
3
2
2
3
5
4
8
6
7
9
Actual Heap
Abstract Heap
3
5
4
8
6
7
9
The top value goes onto the next space in the array
*
Heap Delete Animation
* of 234
0
1
2
7
8
6
5
1
4
3
3
3
3
5
4
8
6
7
9
Actual Heap
Abstract Heap
3
5
4
8
6
7
9
The smallest value below then moves upwards
*
Heap Delete Animation
* of 234
0
1
2
7
8
6
5
1
4
3
3
3
4
5
4
8
6
7
9
Actual Heap
Abstract Heap
4
5
4
8
6
7
9
And again
*
Heap Delete Animation
* of 234
0
1
2
7
8
6
5
1
4
3
3
3
4
5
9
8
6
7
9
Actual Heap
Abstract Heap
4
5
9
8
6
7
9
And again
*
Heap Delete Animation
* of 234
0
1
2
7
8
6
5
1
4
3
3
3
4
5
9
8
6
7
Actual Heap
Abstract Heap
4
5
9
8
6
7
As we just moved the value in the right-most bottom node upwards, we simply ‘delete’ that node
*
Heap Delete Animation
* of 234
0
1
2
3
8
6
5
1
4
3
3
3
4
5
9
8
6
7
Actual Heap
Abstract Heap
4
5
9
8
6
7
The top value goes onto the next space in the array
*
Heap Delete Animation
* of 234
0
1
2
3
8
6
5
1
4
3
4
4
4
5
9
8
6
7
Actual Heap
Abstract Heap
4
5
9
8
6
7
The smallest value below then moves upwards
*
Heap Delete Animation
* of 234
0
1
2
3
8
6
5
1
4
3
4
4
8
5
9
8
6
7
Actual Heap
Abstract Heap
8
5
9
8
6
7
And again
*
Heap Delete Animation
* of 234
0
1
2
3
8
6
5
1
4
3
4
4
8
5
9
7
6
7
Actual Heap
Abstract Heap
8
5
9
7
6
7
The value in the right-most bottom row, now moves into this free node
*
Heap Delete Animation
* of 234
0
1
2
3
8
6
5
1
4
3
4
4
7
5
9
8
6
7
Actual Heap
Abstract Heap
7
5
9
8
6
7
And ‘percolates’ upwards
*
Heap Delete Animation
* of 234
0
1
2
3
8
6
5
1
4
3
4
4
7
5
9
8
6
Actual Heap
Abstract Heap
7
5
9
8
6
And the right-most bottom node is deleted
*
Heap Delete Animation
* of 234
0
1
2
3
4
6
5
1
4
3
4
4
7
5
9
8
6
Actual Heap
Abstract Heap
7
5
9
8
6
*
Heap Delete Animation
* of 234
0
1
2
3
4
6
5
1
4
3
5
5
7
5
9
8
6
Actual Heap
Abstract Heap
7
5
9
8
6
*
Heap Delete Animation
* of 234
0
1
2
3
4
6
5
1
4
3
5
5
7
6
9
8
6
Actual Heap
Abstract Heap
7
6
9
8
6
*
Heap Delete Animation
* of 234
0
1
2
3
4
6
5
1
4
3
5
5
7
6
9
8
Actual Heap
Abstract Heap
7
6
9
8
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
5
1
4
3
5
5
7
6
9
8
Actual Heap
Abstract Heap
7
6
9
8
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
5
1
4
3
6
6
7
6
9
8
Actual Heap
Abstract Heap
7
6
9
8
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
5
1
4
3
6
6
7
8
9
8
Actual Heap
Abstract Heap
7
8
9
8
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
5
1
4
3
6
6
7
8
9
Actual Heap
Abstract Heap
7
8
9
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
1
4
3
6
6
7
8
9
Actual Heap
Abstract Heap
7
8
9
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
1
4
3
7
7
7
8
9
Actual Heap
Abstract Heap
7
8
9
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
1
4
3
7
7
9
8
9
Actual Heap
Abstract Heap
9
8
9
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
1
4
3
7
7
9
8
Actual Heap
Abstract Heap
9
8
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
7
4
3
7
7
9
8
Actual Heap
Abstract Heap
9
8
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
7
4
3
8
8
9
8
Actual Heap
Abstract Heap
9
8
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
7
4
3
8
8
9
Actual Heap
Abstract Heap
9
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
7
8
3
8
8
9
Actual Heap
Abstract Heap
9
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
7
8
3
9
9
9
Actual Heap
Abstract Heap
9
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
7
8
9
9
9
Actual Heap
Abstract Heap
*
Heap Delete Animation
* of 234
0
1
2
3
4
5
6
7
8
9
Actual Heap
Abstract Heap
Done!!
*
Quicksort
Quicksort: the name says it all!
It is the fastest algorithm that uses no extra space.
It can also be optimised to be very, very fast indeed.
It is O(nlog n) on average and O(n2) in the worst case.
But it is difficult to code and difficult to understand unless you actually try it.
* of 234
*
Quicksort Algorithm
QuickSort
Quicksort (0, size, array);
END QuickSort
QuickSort (low, high, array)
IF low < high AND high-low >= 2
integer pivotIndex
Split (low, high, array, pivotIndex) // sort is done here
QuickSort (low, pivotIndex-1, array)
QuickSort (pivotIndex+1, high, array)
ELSEIF high-low == 2
If array[high] < array[low]
Swap them
ENDIF
ENDIF
END QuickSort
* of 234
*
Split (low, high, array, pivotIndex)
pvalue = array[low]
integer index1 = low
integer index2 = high
WHILE (index1 < index2)
WHILE (array[index1] <= pvalue && index1 < index2)
index1++;
ENDWHILE
WHILE (array[index2] > pvalue && index2 > index1)
index2–;
ENDWHILE
IF (index1 < index2)
Swap values at index1 and index2
ENDIF
ENDWHILE
Set pivotIndex to index2-1
Swap values at low and pivotIndex
End Split
* of 234
Look for a value higher than the pivot value
Look for a value lower than the pivot value
If found, swap them
Now put the pivot value between them
*
Quicksort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
Split()
pivotValue
*
Quicksort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
index1
Use index1 to look for a number larger than the pivot value.
Split()
index2
pivotValue
*
Quicksort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
index1
FOUND
Split()
index2
pivotValue
*
Quicksort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
index1
Use index2 to look for a number smaller than the pivot value.
Split()
index2
pivotValue
*
Quicksort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
index1
Use index2 to look for a number smaller than the pivot value.
Split()
index2
pivotValue
*
Quicksort Animation
* of 234
2
9
0
7
8
6
5
1
4
3
index1
FOUND.
Split()
index2
pivotValue
*
Quicksort Animation
* of 234
2
1
0
7
8
6
5
9
4
3
index1
Swap them
Split()
index2
pivotValue
*
Quicksort Animation
* of 234
2
1
0
7
8
6
5
9
4
3
Use index1 to look for a number larger than the pivot value.
Split()
index1
index2
pivotValue
*
Quicksort Animation
* of 234
2
1
0
7
8
6
5
9
4
3
FOUND.
Split()
index1
index2
pivotValue
*
Quicksort Animation
* of 234
2
1
0
7
8
6
5
9
4
3
Split()
Use index2 to look for a number smaller than the pivot value.
index1
index2
pivotValue
*
Quicksort Animation
2
1
0
7
8
6
5
9
4
3
Split()
Use index2 to look for a number smaller than the pivot value.
index1
index2
pivotValue
*
Quicksort Animation
2
1
0
7
8
6
5
9
4
3
Use index2 to look for a number smaller than the pivot value.
Split()
index1
index2
pivotValue
*
Quicksort Animation
2
1
0
7
8
6
5
9
4
3
Split()
index2 reaches index1, so we halt
index1
index2
pivotValue
*
Quicksort Animation
2
1
0
7
8
6
5
9
4
3
Set pivotIndex to index2-1
Split()
index1
index2
pivotIndex
pivotValue
*
Quicksort Animation
0
1
2
7
8
6
5
9
4
3
Swap the pivotValue and the value at the pivotIndex
Split()
index1
index2
pivotIndex
pivotValue
*
Quicksort Animation
0
1
2
7
8
6
5
9
4
3
At the end of Split(), all numbers are sorted into two ‘bins’: those greater than the pivot value and those less than the pivot value
pivotIndex
*
Quicksort Animation
0
2
7
8
6
5
9
4
3
1
Quicksort the section below pivotIndex
pivotIndex
*
Quicksort Animation
0
2
7
8
6
5
9
4
3
1
Less than three elements and already in order
pivotIndex
*
Quicksort Animation
0
2
7
8
6
5
9
4
3
1
Quicksort the section above pivotIndex
pivotIndex
*
Quicksort Animation
0
2
7
8
6
5
9
4
3
1
pivotValue
Split()
*
Quicksort Animation
0
2
7
8
6
5
9
4
3
1
pivotValue
Use index1 to look for a number larger than the pivot value.
Split()
index1
index2
*
Quicksort Animation
0
2
7
8
6
5
9
4
3
1
pivotValue
FOUND
Split()
index1
index2
*
Quicksort Animation
0
2
7
8
6
5
9
4
3
1
pivotValue
Split()
Use index2 to look for a number smaller than the pivot value.
index1
index2
*
Quicksort Animation
0
2
7
8
6
5
9
4
3
1
pivotValue
Split()
FOUND
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
9
4
8
1
pivotValue
Split()
Swap them
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
9
4
8
1
pivotValue
Split()
Use index1 to look for a number larger than the pivotValue
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
9
4
8
1
pivotValue
Split()
Use index1 to look for a number larger than the pivotValue
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
9
4
8
1
pivotValue
Split()
FOUND
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
9
4
8
1
pivotValue
Split()
Use index2 to look for a number smaller than the pivot value
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
9
4
8
1
pivotValue
Split()
FOUND
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
4
9
8
1
pivotValue
Split()
Swap them
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
4
9
8
1
pivotValue
Split()
index1 reaches index2 so we halt
index1
index2
*
Quicksort Animation
0
2
7
3
6
5
4
9
8
1
pivotValue
Split()
Set pivotIndex to index2-1
index1
index2
pivotIndex
*
Quicksort Animation
0
2
4
3
6
5
7
9
8
1
pivotValue
Split()
Swap the pivotValue and the value at the pivotIndex
index1
index2
pivotIndex
*
Quicksort Animation
0
2
4
3
6
5
7
9
8
1
At the end of Split(), all numbers are sorted into two ‘bins’: those greater than the pivot value and those less than the pivot value
pivotIndex (2)
*
Quicksort Animation
0
2
4
3
6
5
7
9
8
1
Quicksort the section below the pivotIndex
pivotIndex (2)
*
Quicksort Animation
0
2
4
3
6
7
5
9
8
1
Split()
pivotValue
*
Quicksort Animation
0
2
4
3
6
7
5
9
8
1
Split()
pivotValue
index1
index2
*
Quicksort Animation
0
2
4
3
6
7
5
9
8
1
Split()
pivotValue
Use index1 to search for a value larger than the pivotValue
index1
index2
*
Quicksort Animation
0
2
4
3
6
7
5
9
8
1
Split()
pivotValue
FOUND
index1
index2
*
Quicksort Animation
0
2
4
3
6
7
5
9
8
1
Split()
pivotValue
Use index2 to look for a number smaller than pivotValue
index1
index2
*
Quicksort Animation
0
2
4
3
6
7
5
9
8
1
Split()
pivotValue
index2 reaches index1, so we halt
index1
index2
*
Quicksort Animation
0
2
4
3
6
7
5
9
8
1
Split()
pivotValue
Set pivotIndex to index2-1
index1
index2
pivotIndex
*
Quicksort Animation
0
2
3
4
6
7
5
9
8
1
Split()
pivotValue
Swap the pivotValue and the value at pivotIndex
index1
index2
pivotIndex
*
Quicksort Animation
0
2
3
4
6
7
5
9
8
1
At the end of Split(), all numbers are sorted into two ‘bins’: those greater than the pivot value and those less than the pivot value
pivotIndex (3)
*
Quicksort Animation
0
2
4
6
7
5
9
8
1
3
Only 1 value below pivotIndex, so do nothing
pivotIndex (3)
*
Quicksort Animation
0
2
4
6
7
5
9
8
1
3
Only two values above pivotIndex, but out of order
pivotIndex (3)
*
Quicksort Animation
0
2
4
5
7
6
9
8
1
3
So swap them
pivotIndex (3)
*
Quicksort Animation
0
2
4
5
7
6
9
8
1
3
Only two values above pivotIndex, but out of order
pivotIndex (2)
*
Quicksort Animation
0
2
4
5
7
6
8
9
1
3
So swap them
pivotIndex (2)
*
Quicksort Animation
0
2
4
5
7
6
8
9
1
pivotIndex
3
Done!!
Phew!!
*
Readings
Textbook Chapter Searching and sorting Algorithms. Diagrams in the textbook also explain step by step.
Reference book, Introduction to Algorithms. For further study, see part of the book called Sorting and Order Statistics. It contains a number of chapters on sorting.