ALGORTHIMS

Bubble sort , Selection sort , Count Sort, Heap sort ,Quick sort

WEEK 4
Prepared by Ali Hussein Hameed & Ali Odeh Khudhair

Supervised Asst . prof . Dr Ali Fahem

2025-2026
 Sorting algorithms

Introduction
Sorting algorithms are fundamental in computer science and data
structures & algorithms (DSA). These play a crucial role in organizing
data efficiently.

Sorting in data structures helps arrange elements in a specific order,

making it easier to search, analyze, and visualize information. Let’s
learn about the various types of sorting algorithms, their workings, and
their importance in solving real-world problems.

Classification of Sort Algorithms

We can classify the various types of sorting in data structure as:

1. Based on Comparison:

• Comparison-based Sorting: These algorithms sort data by

comparing elements. Examples include Bubble Sort, Selection
Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort.
• Non-comparison-based Sorting: These algorithms sort data
without comparing elements directly. Examples include Counting
Sort, Radix Sort, and Bucket Sort.

1
 Figure 1: Classification of sorting algorithms

2. Based on Stability

• Stable Sorting Algorithms: Stable sort algorithms maintain the

relative order of equal elements. Examples include Bubble Sort,
Merge Sort, and Insertion Sort.
• Unstable Sorting Algorithms: Unstable sort algorithms do not
guarantee the relative order of equal elements. Examples include
Quick Sort, Heap Sort, and Selection Sort.

2
1) Bubble Sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is
comparison-based algorithm in which each pair of adjacent elements is
compared and the elements are swapped if they are not in order. This
algorithm is not suitable for large data sets as its average and worst case
complexity are of O(n 2 ) where n is the number of items.

Working of Bubble Sort :

Step 1 − Check if the first element in the input array is greater than the
next element in the array.

Step 2 − If it is greater, swap the two elements; otherwise move the

pointer forward in the array.

Step 3 − Repeat Step 2 until we reach the end of the array.

Step 4 − Check if the elements are sorted; if not, repeat the same process
(Step 1 to Step 3) from the last element of the array to the first.

Step 5 − The final output achieved is the sorted array.

Example 1:

We take an unsorted array for our example. Bubble sort takes Ο(n2) time
so we're keeping it short and precise.

Bubble sort starts with very first two elements, comparing them to
check which one is greater.

3
In this case, value 33 is greater than 14, so it is already in sorted
locations. Next, we compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be

swapped.

Next we compare 33 and 35. We find that both are in already sorted
positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35.

4
Hence they are not sorted. We swap these values. We find that we have
reached the end of the array. After one iteration, the array should look
like this:

we are now showing how an array should look like after each iteration.
After the second iteration, it should look like this:

after each iteration, at least one value moves at the end.

5
And when there's no swap required, bubble sort learns that an array is
completely sorted.

Example 2:

Consider the list [4, 2, 7, 1].

First pass:

• Compare 4 and 2, swap to get [2, 4, 7, 1]

• Compare 4 and 7, no swap

• Compare 7 and 1, swap to get [2, 4, 1, 7]

Second pass:

• Compare 2 and 4, no swap

• Compare 4 and 1, swap to get [2, 1, 4, 7]

Third pass:

• Compare 2 and 1, swap to get [1, 2, 4, 7]

Fourth pass:

• List is already sorted, no swaps needed

Final sorted list: [1, 2, 4, 7].

6
Pseudo-code:

Analysis of the Bubble Sort algorithm:

The time complexity of Bubble Sort is O(n^2) in the worst-case

scenario and the space complexity of Bubble sort is O(1). Bubble Sort
only needs a constant amount of additional space during the sorting
process.

1. Best Case Time Complexity Analysis of Bubble Sort: O(N)

The best case occurs when the array is already sorted.

Example: [1, 2, 3, 4, 5, 6]

• No swaps occur, so the algorithm stops after the first pass → O(n)

7
2. Worst Case Time Complexity Analysis of Bubble Sort: O(N2)
The worst-case condition for bubble sort occurs when elements of the
array are arranged in decreasing order.
Example: [6, 5, 4, 3, 2, 1]
• Many swaps in every pass → O(n²).

3. Average Case Time Complexity Analysis of Bubble Sort: O(N2)

The number of comparisons is constant in Bubble Sort. So in average
case, there are O(N2) comparisons. This is because irrespective of the
arrangement of elements, the number of comparisons C(N) is same.
Example: [3, 6, 1, 5, 2, 4]

• Random arrangement → usually O(n²)

8
4. Space Complexity Analysis of Bubble Sort:
The space complexity of Bubble Sort is O(1). This means that the amount
of extra space (memory) required by the algorithm remains constant
regardless of the size of the input array being sorted.
Advantages of Bubble Sort:
• Simple to Implement: Easy to understand and code.

• Stable: Maintains the relative order of equal elements.

• In-place Sorting: Requires only a constant amount of additional

memory.

• Adaptive: Efficient for nearly sorted lists with a best-case time

complexity of O(n).

Disadvantages of Bubble Sort:

• Inefficient: Poor performance on large lists with an average and

worst-case time complexity of O(n2).

• High Number of Comparisons: Even if the list is partially sorted,

Bubble Sort makes unnecessary comparisons.

• Not Suitable for Large Datasets: Due to its quadratic time

complexity, it's not recommended for large datasets.

9
2) Selection Sort
❖ This method is used for sorting arrays in ascending or in descending
order.
❖ Selection Sort is a comparison-based sorting algorithm.
❖ Selection sort arrange n elements of array by placing the smallest
element in proper position in case of ascending order.
❖ If an array has n elements, n-1 iterations are required to sort the
array.

Working of Selection Sort:

1. Start from the first element and find the smallest element in the
entire array by iterating over it.

2. Swap this smallest element with the first element.

3. Now, move to the second element find the next smallest in the
remaining unsorted portion and swap it with the second position.

4. Repeat this process until the entire array becomes sorted.

Example 1:

Consider the following unsorted list of elements.

Iteration #1

Select the first position element in the list, compare it with all other elements
in the list and whenever we found a smaller element than the element at first
position then swap those two elements.

10
List after 1st iteration

11
Iteration #2

Select the second position element in the list, compare it with all other
elements in the list and whenever we found a smaller element than the
element at first position then swap those two elements.

Iteration #3

Select the third position element in the list, compare it with all other
elements in the list and whenever we found a smaller element than the
element at first position then swap those two elements.

Iteration #4

Select the fourth position element in the list, compare it with all other
elements in the list and whenever we found a smaller element than the
element at first position then swap those two elements.

Iteration #5

Select the fifth position element in the list, compare it with all other elements
in the list and whenever we found a smaller element than the element at first
position then swap those two elements.

12
Iteration #6

Select the sixth position element in the list, compare it with all other
elements in the list and whenever we found a smaller element than the
element at first position then swap those two elements.

Iteration #7

Select the seventh position element in the list, compare it with all other
elements in the list and whenever we found a smaller element than the
element at first position then swap those two elements.

Example 2:

Consider the list [4, 2, 7, 1].

First pass:
• Find the minimum element in [4, 2, 7, 1], which is 1
• Swap 1 with 4 to get [1, 2, 7, 4]
Second pass:
• Find the minimum element in [2, 7, 4], which is 2
• Swap 2 with 2 to get [1, 2, 7, 4] (no change)
Third pass:
• Find the minimum element in [7, 4], which is 4
• Swap 4 with 7 to get [1, 2, 4, 7]
Fourth pass:
• The last element 7 is already in place, no need to swap
• Final sorted list: [1, 2, 4, 7].

13
Pseudo-code:

Analysis of the Selection sort algorithm

The Selection sort algorithm has a time complexity of O(n^2) and a space
complexity of O(1) since it does not require any additional memory
space apart from a temporary variable used for swapping.
1. Time Complexity Analysis of Selection Sort:
• Best-case: O(n2), best case occurs when the array is already
sorted. (where n is the number of integers in an array).
Example: [1, 2, 3, 4, 5, 6].
• Average-case: O(n2), the average case arises when the elements
of the array are in a disordered or random order, without a clear
ascending or descending pattern.
Example: [3, 6, 1, 5, 2, 4].
• Worst-case: O(n2), The worst-case scenario arises when we need
to sort an array in ascending order, but the array is initially in
descending order.
Example: [6, 5, 4, 3, 2, 1].

14
The number of comparisons is the same for any input order.

2. Space Complexity Analysis of Selection Sort:

Space Complexity O(1), as no extra space is required for the Selection

sort algorithm

Advantages of Selection Sort

1. Easy to understand and implement: uses a simple idea—find the

smallest element and place it in its correct position.
2. Memory-efficient: sorts in-place with O(1) extra space.
3. Few swaps (writes): performs at most n − 1 swaps, useful when
writing to memory is costly.
Disadvantages of Selection Sort

1. Poor time complexity: always O(n²) (best/average/worst), so it

gets slow as n grows.
2. Not good for large datasets: O(n log n) sorts (merge/quick) are
much faster for big inputs.
3. Not adaptive: doesn’t speed up on partially sorted data; it does
the same work anyway.
4. Unstable (basic version): may change the relative order of equal
elements unless modified.

15
Selection Sort VS Bubble Sort
S. Selection Sort Bubble Sort
No.

1. Selection sorting is a sorting algorithm Bubble sorting is a sorting

where we select the minimum element algorithm where we check two
from the array and put that at its correct elements and swap them at their
position. correct positions.

2. Its Time complexity in the Best case is Its Time complexity in the Best
O(N^2) case is O(N)

3. performs minimum number of swaps to performs maximum number of

sort the array swaps to sort the array

5. This sorting algorithm uses the selection This sorting algorithm uses
method exchanging method

6. It is an efficient sorting technique. It is not an efficient sorting

technique.

7. It isn’t a stable algorithm It is a stable algorithm

8. This method is faster. This method is slower.

Q: Why are algorithms like Bubble Sort and Selection Sort taught despite being
weak in practice? Explain their value in terms of analytical understanding and time
complexity?
Analytical understanding:
• Bubble Sort: Shows step-by-step progress (largest moves to the end each
pass) and how input order + early-exit can improve best-case performance.
• Selection Sort: Shows a fixed strategy (pick the minimum each step), so it
doesn’t benefit much from sorted input.
Time complexity:
• Bubble Sort: Best O(n), Average O(n2), Worst O(n2) performance depends
strongly on input order.
• Selection Sort: Best/Average/Worst all O(n2) it still scans the remaining
elements to find the minimum each time, regardless of input order.

16
3) Counting Sort
Counting Sort is a non-comparison-based sorting algorithm. It is highly
efficient when the range of input values is small compared to the number
of elements.

The main idea is to count the occurrences of each element and then use
these counts to determine the correct position of each element in the
sorted output.

How Counting sort works:

• Find the Range: First, find the largest number in the list. This tells
us how many different numbers we need to count.

• Count Each Number: Make a list of counters, one for each possible
number up to the largest number. Go through the original list and
increase the counter for each number you see.

• Cumulative Count: Change the counters so that each one now

shows the total count of numbers up to that point. This helps to
place each number in its correct position in the sorted list.

• Build the Sorted List: Make a new list for the sorted numbers. Go
through the original list again. For each number, use the counter to
find where it goes in the sorted list, then decrease the counter for
that number.

For example, if you have a list of numbers like [4, 2, 2, 8, 3, 3, 1], you count
how many times each number appears, and then use these counts to sort
the list into [1, 2, 2, 3, 3, 4, 8].

Count sort is especially useful when you have a lot of numbers in a small
range. It’s simple and fast, making it a great tool for sorting.

17
Count Sort Example:

• Consider a given array that needs to be sorted. First, you’ll have to

find the largest element in the array and set it to the max.

• To store the sorted data, you will now initialize a new count array
with length "max+1" and all elements set to 0.

• Later, as shown in the figure, you will store elements of the given
array with the corresponding index in the count array.

• Now, you will change the count array by adding the previous
counts to produce the cumulative sum of an array, as shown below:

18
 • Because the original array has nine inputs, you will create another
empty array with nine places to store the sorted data, place the
elements in their correct positions, and reduce the count by one.

• As a result, the sorted array is:

19
Pseudo Code of Count Sort Algorithm

Analysis of the Count sort algorithm

Count Sort Time Complexity

n= number of elements in the input array.

k = range size (≈ max_val + 1).

20
1. Best-Case

The executed loops depend only on n and k:

• Finding max: (n−1) iterations

• Initializing count: k iterations

• Counting occurrences: n iterations

• Prefix sums: (k−1) iterations

• Creating output: constant c6

2. Worst-Case

Counting Sort still runs the same loops the same number of times (based
on n and k), regardless of input order:

3. Average-Case For a typical (random) input, the number of iterations

is unchanged because the loops depend only on n and k:

Count Sort Space Complexity

The space complexity of count sort is O(n + k).

21
Advantages of Count Sort

• Linear Time Complexity: O(n + k) makes it very efficient for large

datasets with a small range of values.

• Stable Sorting: Maintains the relative order of elements with

equal keys.

• Simple Implementation: Easy to understand and implement.

• Suitable for Large Datasets: Particularly effective when the

range of input values (k) is not significantly larger than the number
of elements (n).

Disadvantages of Count Sort

• Not Suitable for Large Range: Becomes inefficient when the

range of input values (k) is much larger than the number of
elements (n).

• Extra Space: Requires additional space for the count array,

leading to O(n + k) space complexity.

• Restricted to Non-Negative Integers: Primarily works for

sorting integers and cannot be directly applied to other data types
or negative numbers without modification.

• Fixed Range Requirement: Needs prior knowledge of the

maximum value in the input array to determine the size of the
count array.

22
Heap Data Structure
A Heap is a special Tree-based data structure in which the tree is a complete
binary tree and satisfies the heap property:
Properties of a Binary Heap
1. They are complete binary trees: This means all levels are totally filled
(except maybe the last level), and the nodes in the last level are as left as
possible.

2. Heaps are typically of two types — max heap and min heap: In a max heap,
the value of a node is always greater than or equal to the value of each of its
children. Conversely, in a min heap, the value of a parent is always <= the value
of each of its children.

23
3. In a max heap, the element at the root will always be the maximum. In a min
heap, the element at the root will always be the minimum

4) Heap sort
Heap sort is a comparison-based sorting technique based on Binary Heap data
structure. It is similar to the selection sort where we first find the minimum
element and place the minimum element at the beginning. Repeat the same
process for the remaining elements.
An Array A that presents a heap with two attribute:
• Length [A]: the number of elements in the array.
• heap-size[A]: the number of elements in the heap stored with array A.
• Length [A] ≥ heap-size[A].
To convert the heap tree into a heap array as shown in the figure below, the root
of the tree A[0] and given index i of a node , the indices of its parent , left child
and right child can be computed as :
• A [0] is the root of the tree
• The parent PARENT(i) is at [ (i-1) / 2] if i≠ 0.
• The left child LEFT(i) is at [2i+1]
• The right child RIGHT(i) is at [2i+2]

24
Heap sort algorithm
Steps on How the heap sort algorithm work

Step 1: Build Heap. Build a heap from the input data. Build a max heap to sort
in increasing order, and build a min heap to sort in decreasing order.
Step 2: Swap Root. Swap the root element with the last item of the heap.
Step 3: Reduce Heap Size. Reduce the heap size by 1.
Step 4: Re-Heapify. Heapify the remaining elements into a heap of the new heap
size by calling heapify on the root node.
Step 5: Call Recursively. Repeat steps 2,3,4 as long as the heap size is greater
than 2.

Algorithm(pseudocode)
1) Heap sort(A)

25
2) BuildMaxHeap(A)

3) MaxHeapify(A,i)

26
Phase 1: Creating the Heap
Example [3, 7, 1, 8, 2, 5, 9, 4, 6]

This tree does not yet represent a max heap. The definition of a max heap is that
parents are always greater than or equal to their children.

Invocation No. 1 of the Heapify Method

The heapify() method is called first for the last parent node. Parent nodes are 3,
7, 1, and 8. The last parent node is 8. The heapify() function checks if the
children are smaller than the parent node. 4 and 6 are smaller than 8, so at this
parent node, the heap condition is fulfilled, and the heapify() function is
finished.

27
Invocation No. 2 of the Heapify Method
Second, heapify() is called for the penultimate node: the 1. Its children 5 and 9
are both greater than 1, so the heap condition is violated. To restore the heap
condition, we now swap the larger child with the parent node, i.e., the 9 with
the 1. The heapify() method is now finished again

Invocation No. 3 of the Heapify Method

Now heapify() is called on the 7. Child nodes are 8 and 2; only the 8 is larger
than the parent node. So we exchange the 7 with the 8:

Since the child node we just swapped has two children itself, the heapify()
method must now check if the heap condition for this child node is still valid. In
this case, the 7 is greater than 4 and 6; the heap condition is fulfilled, and the
heapify() function is finished.

28
Invocation No. 4 of the Heapify Method
Now we have arrived at the root node with element 3. Both child nodes, 8 and
9 are larger, while 9 is the largest child and is, therefore, swapped with the
parent node:

Again, the swapped child node has children itself, so we need to check the heap
condition on this child node. The 5 is greater than the 3, i.e., the heap condition
is not fulfilled. It must be restored by swapping the 5 and the 3:

29
The fourth and last call of the heapify() function has finished. A max heap has
been created:

Which brings us to phase two of the heapsort algorithm.

Phase 2: Sorting the Array

In phase 2, we take advantage of the fact that the largest element of the max
heap is always at its root (in the array: on the far left).

Phase 2, Step 1: Swapping the Root and Last Elements

The root element (the 9) is now swapped with the last element (the 6) so that the 9 is at its
final position at the end of the array (marked blue in the array). We also remove this element
from the tree (displayed in grey):

30
After we've placed the 6 at the root of the tree, it is no longer a max heap.
Therefore, in the next step, we will "repair" the heap.
Phase 2, Step 2: Restoring the Heap Condition
To restore the heap condition, we call the heapify() method known from phase
1 on the root node. This means we compare the 6 with its children, 8 and 5; the
8 is bigger, so we swap it with the 6:

The swapped child node has, in turn, two children, the 7 and the 2. The 7 is
larger than the 6, and we swap these two elements as well:

31
The exchanged child node also has a child, the 4. The 6 is greater than the 4, so
the heap condition is fulfilled at this node. The heapify() function is finished,
and we have a max heap again:

Repeating the Steps

The largest number of the remaining array, 8, is now in the first position. We
swap it with the last element of the tree. Since we have shortened the tree by
one element, the last element of the tree is on the second last field of the array:

Now, the last two fields of the array are sorted.

At the root, the heap condition is violated again. We repair the tree by calling
heapify() on the root element (the following picture shows all heapify steps at
once).
32
We repeat the process until there is only one element left in the tree:

This element is the smallest and remains at the beginning of the array. The
algorithm is finished, the array is sorted:

33
Time and space complexity
This table illustrate the time and space complexity of the heap sort , build max
heap , and max heapify

1- MaxHeapify
This operation maintains the heap property by comparing a node with it
children and swapping if necessary, moving down the tree.
Time complexity
Proof
In a heap of size n, the height is log2n in the worst case the element travels form
the root to a leave , the number of comparison and swaps is proportional to the
height h.
T(n)≤T(2n/3) +Θ(1)
By master Theorem T(n) = O(log n).
Space complexity
O(l) for iterative implementation
O(log n) for recursive implementation du to stack frame.

34
2- BuildMaxHeap
This involves calling Max-Heapify on all non-leaf nodes starting from
index n/2 down to 1.
Time complexity
Proof
An n-element heap has at most [n/2h+1] nodes of height h. the time to heapify a
node at height h is O(h).
Total cost

Since the infinite series converges to 2, the complexity is O(n).

Space complexity
O(1) (in-place)
3- Heap sort
Algorithm consists of building a max heap and then repeatedly extracting the
maximum element and heapifying the remaining tree.
Time complexity
Proof
1. Build-Max-Heap takes O(n).
2. There are n−1 calls to Max-Heapify.
3. Each Max-Heapify call on a heap of size i takes O(logi).

Using Stirling's approximation, log(n!) ≈ n log n.

Thus, T(n)=O(n log n).

35
Strengths of Heap Sort

• No quadratic worst-case run time.

• It is an in-place sorting algorithm and performs sorting in O(1) space
complexity.
• Compared to quicksort, it has a better worst-case time complexity
— O(n log n).
• The best-case complexity is the same for both quick sort and heap sort
— O(nlog n).
• Unlike merge sort, it does not require extra space.
• The input data being completely or almost sorted doesn’t make the
complexities suffer.

Weaknesses of Heap Sort

• Heap sort is typically not stable since the operations on the heap can
change the relative order of equal key items. It’s typically an unstable
sorting algorithm.

• If the input array is huge and doesn’t fit into the memory and partitioning
the array is faster than maintaining the heap, heap sort isn’t an option. In
such cases, something like merge sort or bucket sort, where parts of the
array can be processed separately and parallelly, works best.

36
5) Quick sort algorithm
Quick Sort algorithm is a highly efficient, comparison-based sorting algorithm
that follows the divide and conquer approach. It picks an element as a pivot and
partitions the given array around the picked pivot.

How to choose the pivot ?

• Always pick the first element as a pivot. Pivot = A[r]
• Always pick the last element as a pivot. Pivot = A[p]
• Pick a random element as a pivot (randomized quick sort).
i = RANDOM(p,r)
swap A[i] with A[r]
pivot = A[r]
• Pick median as the pivot. Pivot = median(A[p] , A[(p+r)/2] , A[r] )

37
How Does the Quick Sort Algorithm Work?
Example 1: (Left Pivot)
Let the elements of array are –

In the given array, we consider the leftmost element as pivot. So, in this case,
a[left] = 24, a[right] = 27 and a[pivot] = 24
Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards
left, i.e. –

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and
pivot moves to right, as -

38
Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so
algorithm starts from left and moves to right
As a[pivot] > a[left], so algorithm moves one position to right as –

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so
algorithm moves one position to right as –

Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so,
swap a[pivot] and a[left], now pivot is at left, i.e. –

39
Since, pivot is at left, so algorithm starts from right, and move to left. Now,
a[left] = 24, a[right] = 29, and a[pivot] = 24. As a[pivot] < a[right], so
algorithm moves one position to left, as –

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap a[pivot]
and a[right], now pivot is at right, i.e. -

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the
algorithm starts from left and move to right.

40
Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are
pointing the same element. It represents the termination of procedure.
Element 24, which is the pivot element is placed at its exact position.
Elements that are right side of element 24 are greater than it, and the
elements that are left side of element 24 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the left and right
sub-arrays.

In Left sub array now, a[pivot] = 19, a[left] = 19, and a[right] = 14. As, a[pivot]
> a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves to
right.
In Right sub array now, a[pivot] = 29, a[left] = 29, and a[right] = 27. As, a[pivot]
> a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves to
right.

41
now, a[pivot] = 14, a[left] = 14, and a[right] = 9. As, a[pivot] > a[right], so,
algorithm will swap a[pivot] with a[right], and pivot moves to right.

Finally combine the already sorted array. After combine gets done, the array
will be :

9 14 19 24 27 20

Example 2: (Middle pivot)

Let the elements of array a[8] are :

8/2=4  pivot = a [4]  pivot =14

A[left]=32 >a[pivot]=14 stop pointer in a[left] ,and compare the pivot with
right, a[right]= 65 >a[pivot]= 14, move right pointer to left, until find number
less than pivot.
a[right]= 6<a[pivot]= 14 then swap(a[left],a[right]).

Move the pointers one more step and find a number greater than the pivot from
the left, then stop when you find it. After that, find a number smaller than the
pivot from the right, and swap the two numbers.

42
 Swap a[left]=23, a[right]=7

Swap(a[left]=6, a[right]=1) Swap(a[left]=43, a[right]=23)

No swap Swap(a[left]=43, a[right]=32)

No swap

Finally combine the already sorted array. After combine gets done, the array
will be :-

43
Divide-and-Conquer in Quick sort
Three-step divide-and-conquer process for sorting a subarray A[p : r]:
Divide by partitioning (rearranging) the array A[p : r] into two (possibly empty)
subarrays A[p : q – 1] (the low side) and A[q + 1 : r] (the high side) such that
each element in the low side of the partition is less than or equal to the
pivot A[q], which is, in turn, less than or equal to each element in the high side.
Compute the index q of the pivot as part of this partitioning procedure.
Conquer by calling quicksort recursively to sort each of the subarrays A[p : q –
1] and A[q + 1 : r].
Combine by doing nothing: because the two subarrays are already sorted, no
work is needed to combine them. All elements in A[p : q 1] are sorted and less
than or equal to A[q], and all elements in A[q + 1 : r] are sorted and greater than
or equal to the pivot A[q]. The entire subarray A[p : r] cannot help but be sorted!

Quick Sort Pseudo Code

The QUICKSORT procedure implements quicksort. To sort an entire n-element
array A[1 : n], the initial call is QUICKSORT (A, 1, n).

To sort an entire array A, the initial call is QUICKSORT (A, 1, length [A]).

44
Partitioning the array
The key to the algorithm is the PARTITION procedure, which rearranges the
subarray A[p……r] in place.

This partitioning procedure is called within a QUICKSORT procedure so that the

algorithm is executed in regular steps according to the partitioning concept,
pivot selection, and other procedures.
The four regions maintained by the procedure PARTITION on a subarray
A[p : r]. The tan values in A[p : i] are all less than or equal to x, the blue values
in A[i + 1 : j – 1] are all greater than x, the white values in A[j : r – 1] have
unknown relationships to x, and A[r] = x

45
Example Trace
The operation of PARTITION on a sample array. Array entry A[r] becomes the pivot element
x.

(a) The initial array and variable settings. None of the elements have been placed into either
side of the partition.

(b) The value 2 is “swapped with itself” and put into the low side.

(c)–(d) The values 8 and 7 are placed into to high side.

(e) The values 1 and 8 are swapped, and the low side grows.

(f) The values 3 and 7 are swapped, and the low side grows.

(g)–(h) The high side of the partition grows to include 5 and 6, and the loop terminates.

(i) Line 7 swaps the pivot element so that it lies between the two sides of the partition, and
line 8 returns the pivot’s new index.

46
Correctness
We need to show that this loop invariant is true prior to the first iteration, that
each iteration of the loop maintains the invariant, that the loop terminates, and
that correctness follows from the invariant when the loop terminates.
1. All entries in A[p .. i] are ≤ pivot.
2. All entries in A[i+1 .. j −1] are > pivot.
3. A[r] = pivot.

Initialization:
Before the loop starts, condition 3 is satisfied because x is assigned the pivot A[r],
and conditions 1 and 2 are trivially satisfied because the subarrays a[p .. i] and
A[i+1 .. j−1] are empty.
Maintenance:
While the loop is running,
• if A[j] ≤ pivot, then i is incremented, A[j] and A[i] are swapped, and j is
incremented. Because of the swap, A[i] ≤ x for condition 1. The item
swapped into A[j-1] > x by the loop invariant, for condition 2.
• If A[j] > pivot, then j is incremented, sustaining condition 2 (the others
are unchanged), as the element added was larger.
Termination:
The loop terminates when j=r, so all elements in A are partitioned into one of
three cases: A[p .. i] ≤ pivot, A[i+1 .. r-1] > pivot, and A[r] = pivot. The last two
lines fix the placement of A[r] by moving it between the two subarrays.

47
Performance of quicksort (Informal Analysis)
The running time of quicksort depends on how balanced each partitioning is,
which in turn depends on which elements are used as pivots. If the two sides of
a partition are about the same size—the partitioning is balanced—then the
algorithm runs asymptotically as fast as merge sort. If the partitioning is
unbalanced, however, it can run asymptotically as slowly as insertion sort. To
allow you to gain some intuition before diving into a formal analysis, this section
informally investigates how quicksort performs under the assumptions of
balanced versus unbalanced partitioning.

1. Worst Case Time Complexity

The worst case occurs when the subarrays are completely unbalanced after
partitioning, i.e., there are 0 elements in one subarray and n−1 elements in the
other subarray (the single pivot is not processed in recursive calls). Then
PARTITION must be called on n−1 elements. If this happens again, it will be
called on n−2 elements, etc. This gives a familiar recurrence (compare to that
for insertion sort):

48
Recursion tree for worst case

2. Best case partitioning

The best case occurs when the subarrays are completely balanced (the pivot is
the median value): subarrays after pivoting have about n/2 elements. (One
has n/2 and the other has (n/2)−1 due to removal of the pivot, but we'll ignore
this difference for asymptotic analysis.) The recurrence is also familiar
(compare to that for merge sort):

49
3. Effect of Unbalanced Partitioning
It turns out that expected behavior is closer to the best case than the worst
case. Two examples suggest why expected case won't be that bad.
Example: 1-to-9 split
Suppose each call splits the data into 1/10 and 9/10. This is highly
unbalanced: won't it result in horrible performance?

We have log10n full levels and log10/9n levels that are nonempty.
As long as it's constant, the base of the log does not affect asymptotic results.
Any split of constant proportionality will yield a recursion tree of depth
Θ(lg n). In particular (using ≈ to indicate truncation of low order digits),
log10/9n = (log2n) / (log210/9) by formula 3.15
≈ (log2n) / 0.152
= 1/0.152 (log2n)
≈ 6.5788 (log2n)
= Θ(lg n), where c = 6.5788.
So the recurrence and its solution is:

50
4- Intuition for the average case
With random data there will usually be a mix of good and bad splits throughout
the recursion tree.
A mixture of worst case and best case splits is asymptotically the same as best
case:

Both these trees have the same two leaves. The extra level on the left hand side
only increases the height by a factor of 2, even if we iterate the same imbalance
for subsequent levels, and this constant disappears in the Θ analysis.
Both result in O(n lg n), though with a larger constant for the left.

Comparison of Heap Sort and Quick Sort

Both algorithms have an average time complexity of O(n log n), but they differ
significantly in their performance guarantees and practical execution.
1-Theoretical vs Practical Performance:
Heap sort
It provides a strict theoretical guarantee. Its worst-case, average-case, and
best-case time complexities are all Θ(n log n).This makes it highly predictable
for real-time systems where a delay beyond a certain threshold is
unacceptable.
Quick sort
While its average-case is O(n log n) its theoretical worst-case is O(n2) (e.g., when
the pivot is consistently the smallest or largest element). However, in practice,

51
with randomized pivoting, the O(n2) case is statistically negligible.

2-Why Quick sort is often preferred

Despite the worst-case risk, Quick Sort is generally faster than Heap Sort in
most software environments due to the following reasons:
(i) Locality of Reference:
Quick Sort accesses elements sequentially in small ranges, making it very cache-
friendly. Heap Sort, however, jumps across the array to maintain the heap
property (accessing indices ), leading to frequent cache misses.

(ii) Constant Factors:

The hidden constant factors in Quick Sort’s O(n log n) are smaller than those in
Heap Sort. The number of swaps and comparisons in the inner loop of Quick
Sort is typically lower.
3- Performance

52
4-Operating Environment Preferences
Standard Libraries: Most public libraries (such as std::sort in C++) use a
hybrid algorithm called Introsort. This algorithm starts with Quick Sort for its
speed and then switches to Heap Sort if the call depth exceeds a certain limit,
combining the practical speed of Quick Sort with the theoretical safety of Heap
Sort.
Embedded/Real-Time Systems: Heap Sort is preferred here because the O(n
log n) guarantee is absolute, and memory is often too constrained for the
recursive stack of Quick Sort.

53
References

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 4th ed.
Cambridge, MA, USA: MIT Press, 2022.

[2] GeeksforGeeks, "Bubble Sort Algorithm," 2024. [Online]. Available:

[Link] [Accessed: Feb. 12, 2026].

[3] GeeksforGeeks, "Selection Sort Algorithm," 2024. [Online]. Available:

[Link] [Accessed: Feb. 12, 2026].

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed.
Cambridge, MA, USA: MIT Press, 2022.

[5] Programiz, "Bubble Sort," 2024. [Online]. Available:

[Link] [Accessed: Feb. 12, 2026].

[6] Dr. A.P.J. Abdul Kalam Technical University, "Heap sort (Data Structures lecture notes),"
2023.

[7] “Selection Sort,” WSCubeTech, 2026. [Online]. Available:

[Link] [Accessed: Feb. 14, 2026]

[8] “Count Sort,” WSCubeTech, 2026. [Online]. Available:

[Link] [Accessed: Feb. 14, 2026].

54