Advanced Sorting
and Searching
Algorithms
Chapter 6
Advanced Sorting Algorithms
• Quick Sort
• Quick sort is the fastest known algorithm.
• It uses divide and conquer strategy and in the worst case its
complexity is O (n2).
• But its expected complexity is O(nlogn).
2
Contd.
Partition
Choose a pivot
Find the position for the pivot so that
all elements to the left are less
all elements to the right are greater
< pivot pivot > pivot
Conquer
Apply the same algorithm to each half
< pivot > pivot
< p’ p’ > p’ pivot < p” p” > p”
3
… Quick sort
• Algorithm:
• Choose a pivot value (mostly the first element is taken as the pivot
value)
• Position the pivot element and partition the list so that:
• the left part has items less than or equal to the pivot value
• the right part has items greater than or equal to the pivot value
• Recursively sort the left part
• Recursively sort the right part
4
… Quick sort
• Example: Sort the following list using quick sort algorithm.
• [7, 2, 1, 6, 3, 5, 4, 8]
• initial Call (low=0, high=7):
• Pivot: arr[0] = 7
• Partitioning:
• Initialize two pointers, i (starting at low + 1) and j (starting at high).
• Move i forward until arr[i] > pivot (or i crosses j).
• Move j backward until arr[j] <= pivot (or j crosses i).
• If i < j, swap arr[i] and arr[j].
• After the loop, swap arr[low] (pivot) with arr[j].
• Result after partitioning: [4, 2, 1, 6, 3, 5, 7, 8] (Pivot 7 is now at index 6)
5
… Quick sort
1. Consider the first element of the list as pivot
2. Define two variables I, j. Set i and j the first and last elements
respectively
3. Increment i until list[i] > pivot then stop.
4. Decrement j until list[j] < pivot then stop
5. If i < j, then exchange list[i] and list[j]
6. Repeat steps 3, 4 and 5 until i>j.
7. Exchange the pivot element with list[j]
5 3 8 1 4 6 2 7
p l h
6
Quick Sort Example
Recursive implementation with the left most array
entry selected as the pivot element.
7
Exercise
• Sort the following list using quick sort. Show by hand trace
5 8 2 4 1 3 9 7 6 0
p i j
8
Heap Sort
• Heap sort operates by first converting the list in to a heap tree.
• Heap tree is a binary tree in which each node has a value greater than
both its children (if any).
• It uses a process called "adjust to accomplish its task (building a heap
tree) whenever a value is larger than its parent.
• The time complexity of heap sort is O(nlogn).
9
The Heap Data Structure
A heap is a complete binary tree with the following two
properties:
Structural property: all levels are full, except possibly the last
one, which is filled from left to right
Order (heap) property: 8 for any node x, Parent(x) ≥ x
From the heap
7 4 property, it follows
5 2
that:
“The root is the
Heap
maximum
A heap is a binary tree that is
element of the
filled in order heap!”
10
Array Representation of Heaps
A heap can be stored
as an array A.
Root of tree is A[1]
Left child of A[i] = A[2i]
Right child of A[i] =
A[2i + 1]
Parent of A[i] = A[ i/2 ]
Heapsize[A] ≤
length[A]
The elements in the
sub array
11
Heap Types
Max-heaps (largest element at root), have the max-heap
property:
for all nodes i, excluding the root:
A[PARENT(i)] ≥ A[i]
Min-heaps (smallest element at root), have the min-heap
property:
for all nodes i, excluding the root:
A[PARENT(i)] ≤ A[i]
12
Max Heap – Example
26 24 20 18 17 19 13 12 14 11 Max-heap as an
1 2 3 4 5 6 7 array.
8 9 10
Max-heap as a
binary tree.
26
24 20
18 17 19 13
12 14 11 Last row filled from left to right.
13
Adding/Deleting Nodes
New nodes are always inserted at the
bottom level (left to right)
Nodes are removed from the bottom level
(right to left)
14
Operations on Heaps
Maintain/Restore the max-heap property
MAX-HEAPIFY
Create a max-heap from an unordered
array
BUILD-MAX-HEAP
Sort an array in place
HEAPSORT
15
Maintaining the Heap Property
Suppose a node is smaller
than a child
Left and Right subtrees of i
are max-heaps
To eliminate the violation:
Exchange with larger child
Move down the tree
Continue until node is not
smaller than children
16
Example
MAX-HEAPIFY(A, 2, 10)
A[2] A[4]
A[4] violates the heap property
A[2] violates the heap property
A[4] A[9]
Heap property restored
17
Maintaining the Heap Property
Assumptions:
Left and Right
subtrees of i are max-
heaps
A[i] may be smaller
than its children
18
Building a Heap
Convert an array A[1 … n] into a max-heap
(n = length[A])
The elements in the subarray A[(n/2+1) ..
n] are leaves
Apply MAX-HEAPIFY on elements between 1
1
and
Alg: BUILD-MAX-HEAP(A)
n/2 4
1. n = length[A] 2 3
1 3
2. for i ← n/2 downto 1 4 5 6 7
8
2 9 10
16 9 10
3. do MAX-HEAPIFY(A, i, n) 14 8 7
A: 4 1 3 2 16 9 10 14 8 7
Example: A 4 1 3 2 16 9 10 14 8 7
i=5 i=4 i=3
1 1 1
4 4 4
2 3 2 3 2 3
1 3 1 3 1 3
4 5 6 7 4 5 6 7 4 5 6 7
8
2 9 10
16 9 10 8 2 9 10
16 9 10 8 14 9 10
16 9 10
14 8 7 14 8 7 2 8 7
i=2 i=1
1 1 1
4 4 16
2 3 2 3 2 3
1 10 16 10 14 10
4 5 6 7 4 5 6 7 4 5 6 7
8
14 9 10
16 9 3 8
14 9 10
7 9 3 8
8 9 10
7 9 3
2 8 7 2 8 1 2 4 1
20
Heapsort
Goal:
Sort an array using heap representations
Idea:
Build a max-heap from the array
Swap the root (the maximum element) with
the last element in the array
“Discard” this last node by decreasing the
heap size
Call MAX-HEAPIFY on the new root
Repeat this process until only one node
remains 21
Example: A=[7, 4, 3, 1, 2]
MAX-HEAPIFY(A, 1, 4) MAX-HEAPIFY(A, 1, 3) MAX-HEAPIFY(A, 1, 2)
MAX-HEAPIFY(A, 1, 1)
22
Alg: HEAPSORT(A)
1. BUILD-MAX-HEAP(A)
2. for i ← length[A] downto 2
3. do exchange A[1] ↔ A[i]
4. MAX-HEAPIFY(A, 1, i -
Heap
1)
sort: Analysis
Running time
worst case is (N log N)
Average case is also O(N log N)
23
Exercise
Sort the following list using heap sort algorithm
5 8 2 4 1 3 9 7 6 0
Construct the initial binary tree
Construct the heap tree
Sort using heapsort
24
Merge Sort
Sorting Problem: Sort a sequence of n elements into non-decreasing order.
Divide: Divide the n-element sequence to be sorted into two subsequences of n/2
elements each
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.
25
Example
26
Merge Sort – Example2
Original Sequence Sorted Sequence
18 26 32 6 43 15 9 1 1 6 9 15 18 26 32 43
18 26 32 6 43 15 9 1 6 18 26 32 1 9 15 43
43
18 26 32 6 43 15 9 1 18 26 6 32 15 43 1 9
18 26 32 6 43 15 9 1 18 26 32 6 43 15 9 1
18 26 32 6 43 15 9 1
28
