CS计算机代考程序代写 data structure algorithm Searching, Sorting and Merging

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.