Advanced Sorting

algorithms
Quick Sort
Shell sort
Heap Sort
merge sort (Covered before)

12/24/2023 Set by Kelemu L. 1

Quick Sort
• Quick sort is based on partition( partition exchange sorting).
• The basic concept of quick sort process is pick one element (Pivot) from an array
and rearranges the remaining elements around it.
• This element divides the main list into two sub lists.
• Once pivot is chosen, then it shifts all the elements less than pivot to left of pivot
and all the elements greater than pivot are shifted to the right side.
• This procedure of choosing pivot and partition the list is applied recursively until
sub-lists consisting of only one element.
• Which paradigm does it really apply?

12/24/2023 Set by Kelemu L. 2

Cont’d…
• It applies a divide and conquer algorithm paradigm.
• It has two basic procedures (Partition, and quickSort)
• The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements which are less than the pivot come before
the pivot and so that all elements greater than the pivot come after it (equal
values can go either way).
After this partitioning, the pivot is in its final position.
This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater
elements.

12/24/2023 Set by Kelemu L. 3

Example
• Ex:- A list of unsorted elements are: 8 3 2 11 5 14 0 2 9 4 20

12/24/2023 Set by Kelemu L. 4

Algorithm
1

12/24/2023 Set by Kelemu L. 5

Simplified version

12/24/2023 Set by Kelemu L. 6

Analysis
• How to select the pivot element ?
• Using a random element as pivot enables Quicksort to provide an average-case
performance that usually outperforms other sorting algorithms.
• In the ideal case, partition divides the original array in half and Quicksort exhibits
O(n log n) performance.
• Quicksort is effective with a randomly selected pivot.

• In the worst case, the largest or smallest item is picked as the pivot.
• Quicksort makes a pass over all elements in the array (in linear time) to sort just a single
item in the array
• If this process is repeated n − 1 times, it will result in O(n2) worst-case behavior

12/24/2023 Set by Kelemu L. 7

Pivot selection
• Selection of Pivot
• Select first or last: A[left] or A[left + n − 1]
• Select random element in A[left, left + n − 1]
• Select median-of-k: the middle value of k elements taken from A[left, left + n −1]
• Selection of algorithms
• If the depth of the recursion is a foreseeable issue, then perhaps Quicksort is not
appropriate for your application.
• On small arrays, Insertion Sort is faster than Quicksort.
• Or use introSort (quicksort variation)
• If the depth of the Quicksort recursion exceeds log (n) levels, then IntroSort switches to Heap Sort
• Using bucket sort and hashing ?
• Researchers suggest that a combination of median-of-three (pivot selection) and using
Insertion Sort for small subarrays offers a speedup of 20%–25% over pure Quicksort.

12/24/2023 Set by Kelemu L. 8

Time Complexity of Quick sort
• Pass 1 will have n comparisons.
• Pass 2 will have 2*(n/ 2) comparisons. In the subsequent passes will have
4*(n/4), 8*(n/8) comparisons and so on.
• The total comparisons involved O(n)+O(n)+O(n)+···+s.
• The value of expression will be O (n logn) time complexity is O(n log n).
• And , only O(n log n) additional space is required.
• Best case : O (n log n)
• Average case : O (n log n)
• Worst case : O (n2)

12/24/2023 Set by Kelemu L. 9

Advantages and disadvantage
• Advantages
• This is faster sorting method among all (even when an array is in random order).
• Its efficiency is also relatively good.
• It requires relatively small amount of memory
• can be used to sort arrays of any size.
• Disadvantages
• It is complex method of sorting so, it is little hard to implement than other
sorting methods.

12/24/2023 Set by Kelemu L. 10

Shell sort
• is very similar to that of the Insertion sort algorithm.
• In case of Insertion sort, we move elements one position ahead to insert an element at its
correct position.
• Whereas, Shell sort starts by sorting pairs of elements far apart from each other, then
progressively reducing the gap between elements to be compared.
• Starting with far apart elements, it can move some out-of-place elements into
the position faster than a simple nearest-neighbor exchange.

12/24/2023 Set by Kelemu L. 11

Example
• A = {17, 3, 9, 1, 8}

12/24/2023 Set by Kelemu L. 12

Algorithm

12/24/2023 Set by Kelemu L. 13

Time complexity
• Best Case Complexity - It occurs when there is no sorting required, i.e., the array
is already sorted.
• The best-case time complexity of Shell sort is O(n*logn).
• Average Case Complexity - It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending.
• The average case time complexity of Shell sort is O(n*logn).
• Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order.
• That means suppose you have to sort the array elements in ascending order, but its
elements are in descending order.
• The worst-case time complexity of Shell sort is O(n2).

12/24/2023 Set by Kelemu L. 14

Heap Sort
• First convert the array into heap data structure using heapify,
• Then one by one delete the root node of the Max-heap and replace it with the last node in
the heap and then heapify the root of the heap.
• Repeat this process until size of heap is greater than 1.
• Specifically
• Build a heap from the given input array.
Repeat the following steps until the heap contains only one element:
• Swap the root element of the heap (which is the largest element) with the last element of
the heap.
• Remove the last element of the heap (which is now in the correct position).
• Heapify the remaining elements of the heap.
• The sorted array is obtained by reversing the order of the elements in the input array.

12/24/2023 Set by Kelemu L. 15

Heap Properties
• Complete Binary Tree: A heap tree is a complete binary tree,
• meaning all levels of the tree are fully filled except possibly the last level, which is filled
from left to right.
• Heap Property: This property ensures that the minimum (or maximum) element
is always at the root of the tree according to the heap type.
• Parent-Child Relationship: The relationship between a parent node at index ‘i’
and its children is given by the formulas:
• left child at index 2i+1 and right child at index 2i+2 for 0-based indexing of node numbers.

12/24/2023 Set by Kelemu L. 16

• Efficient Insertion and Removal: Insertion and removal operations in heap trees
are efficient.
• New elements are inserted at the next available position in the bottom-rightmost level,
and the heap property is restored by comparing the element with its parent and swapping
if necessary.
• Removal of the root element involves replacing it with the last element and heapifying
down.
• Efficient Access to Extremal Elements: The minimum or maximum element is
always at the root of the heap, allowing constant-time access.

12/24/2023 Set by Kelemu L. 17

Operation in heap
• Heapify: It is the process to rearrange the elements to maintain the property of
heap data structure.
• It is done when a certain node creates an imbalance in the heap due to some
operations on that node.
• It takes O(log N) to balance the tree.
• For max-heap, it balances in such a way that the maximum element is the root of that
binary tree and
• For min-heap, it balances in such a way that the minimum element is the root of that
binary tree.

12/24/2023 Set by Kelemu L. 18

• Insertion: If we insert a new element into the heap
• since we are adding a new element into the heap
• so it will distort the properties of the heap
• so we need to perform the heapify operation so that it maintains the property of the
heap.
• This operation also takes O(logN) time.

12/24/2023 Set by Kelemu L. 19

Example

• First, we have to construct a heap from the given array and convert it into max
heap.

12/24/2023 Set by Kelemu L. 20

Delete the root element
• delete the root element (89) from the max heap.
• To delete this node, we have to swap it with the last node, i.e. (11).
• After deleting the root element, we again have to heapify it to convert it into
max heap.

12/24/2023 Set by Kelemu L. 21

12/24/2023 Set by Kelemu L. 22
12/24/2023 Set by Kelemu L. 23
• Then lastly

12/24/2023 Set by Kelemu L. 24

Algorithm
• Build a max heap from the input array:
• Start from the last non-leaf node (index n/2 - 1) and move up to the root.
• For each node, compare it with its children and swap if necessary to maintain the max
heap property.
• Repeat this process until all nodes are in their correct positions.
• Extract elements from the max heap one by one:
• Swap the root element (maximum value) with the last element in the heap.
• Reduce the size of the heap by 1.
• Heapify the root element to maintain the max heap property.
• Repeat these steps until all elements are extracted.
• The extracted elements, in reverse order, form the sorted array.

12/24/2023 Set by Kelemu L. 25

Time Complexity
• Best Case Complexity - It occurs when there is no sorting required, i.e. the array
is already sorted.
• The best-case time complexity of heap sort is O(n logn).
• Average Case Complexity - It occurs when the array elements are in jumbled
order that is not properly ascending and not properly descending.
• The average case time complexity of heap sort is O(n log n).
• Worst Case Complexity - It occurs when the array elements are required to be
sorted in reverse order.
• That means suppose you have to sort the array elements in ascending order, but its
elements are in descending order.
• The worst-case time complexity of heap sort is O(n log n).

12/24/2023 Set by Kelemu L. 26

Advantages
• Like insertion sort algorithm, the heap sort algorithm sorts in place.
• Heap sort algorithm is simple, fast, and stable sorting algorithm which can be
used to sort large sets of data.
• Fast access to maximum/minimum element (O(1)) (how ?)
• Efficient Insertion and Deletion operations (O(log n))
• Flexible size
• Can be efficiently implemented as an array
• Suitable for real-time applications

12/24/2023 Set by Kelemu L. 27

Disadvantages
• Not suitable for searching for an element other than maximum/minimum (O(n)
in worst case)
• Extra memory overhead to maintain heap structure
• Slower than other data structures like arrays and linked lists for non-priority
queue operations.

12/24/2023 Set by Kelemu L. 28

 End of Chapter 2

Questions ?

12/24/2023 Set by Kelemu L. 29

Chapter 2: quiz a 15 min work
• Construct a heap tree and heapify (MaxHeap ) the Tree for the array given
below.
[12, 21, 13, 8, 45, 32, 35, 25, 66] ?
• Illustrate diagrammatically how the above array can be sorted using a heap sort

• Attempt the questions based on your understandings.

• Weight 5%
12/24/2023 Set by Kelemu L. 30
 Individual Assignment (10%)
Prepare a term paper on
improving the performance (both best case, and worst case) of quicksort, merge
sort, and shell sort algorithms.
Justify your answers with examples, theorems or demonstrations if any.

• pages should not be more than 4 (four pages)

• Plagiarism, and AI generated text is prohibited
• Use references (books, research papers)

12/24/2023 Set by Kelemu L. 31