Introduction to Sorting
Sorting refers to rearrangement of a given array or list of elements according to a
comparison operator on the elements. The comparison operator is used to decide the new
order of elements in the respective data structure.
Applications of Sorting Algorithms:
● Quickly Finding k-th Smallest or K-th Largest : Once we sort the array, we can
find k-th smallest and k-th largest elements in O(1) time for different values of k.
● Searching Algorithms: Sorting is often a crucial step in search algorithms like
binary search, Ternary Search, where the data needs to be sorted before
searching for a specific element.
● Data management: Sorting data makes it easier to search, retrieve, and analyze.
● Database optimization: Sorting data in databases improves query performance.
We typically keep the data sorted by primary index so that we can do quick
queries.
● Machine learning: Sorting is used to prepare data for training machine learning
models.
● Data Analysis: Sorting helps in identifying patterns, trends, and outliers in
datasets. It plays a vital role in statistical analysis, financial modeling, and other
data-driven fields.
● Operating Systems: Sorting algorithms are used in operating systems for tasks
like task scheduling, memory management, and file system organization.
Advantages of Sorting Algorithms:
● Efficiency: Sorting algorithms help in arranging data in a specific order, making it
easier and faster to search, retrieve, and analyze information.
● Improved Performance: By organizing data in a sorted manner, algorithms can
perform operations more efficiently, leading to improved performance in various
applications.
● Simplified data analysis: Sorting makes it easier to identify patterns and trends in
data.
● Reduced memory consumption: Sorting can help reduce memory usage by
eliminating duplicate elements.
● Improved data visualization: Sorted data can be visualized more effectively in
charts and graphs.
Disadvantages of Sorting Algorithms:
● Insertion: If we wish to keep data sorted, then insertion operation becomes costly
as we have to maintain sorted order. If we do not have to maintain sorted order,
we can simply insert at the end.
● Algorithm selection: Choosing the most appropriate sorting algorithm for a given
dataset can be challenging.
● For a lot of problems hashing works better than sorting, for example, finding
distinct elements, finding a pair with given sum.
Types of Sorting Techniques
There are various sorting algorithms used in data structures. The following two types of
sorting algorithms can be broadly classified:
1. Comparison-based: We compare the elements in a comparison-based sorting
algorithm)
2. Non-comparison-based: We do not compare the elements in a
non-comparison-based sorting algorithm)
1. Bubble Sort
Bubble Sort is an algorithm that sorts an array from the lowest value to the highest value.
The word 'Bubble' comes from how this algorithm works, it makes the highest values 'bubble
up'.
How it works:
1. Go through the array, one value at a time.
2. For each value, compare the value with the next value.
3. If the value is higher than the next one, swap the values so that the highest value
comes last.
4. Go through the array as many times as there are values in the array.
Complexity Analysis of Bubble Sort:
Time Complexity: O(n2)
Auxiliary Space: O(1)
Advantages
● 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
● 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
Applications of Bubble Sort
● Educational Purposes: Ideal for teaching and learning basic sorting algorithms.
● Small Datasets: Suitable for sorting small lists where simplicity is more important
than efficiency.
● Partially Sorted Data: Performs well on nearly sorted data, making it useful in
scenarios where data is mostly ordered.
● Computer Graphics: Sometimes used in simple graphics applications where small
arrays need sorting.
Algorithm
In the algorithm given below, suppose arr is an array of n elements. The assumed swap
function in the algorithm will swap the values of given array elements.
1. begin BubbleSort(arr)
2. for all array elements
3. if arr[i] > arr[i+1]
4. swap(arr[i], arr[i+1])
5. end if
6. end for
7. return arr
8. end BubbleSort
Program to sort an array of integers in ascending order using bubble sort.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
int arr[n];
cout << "Enter " << n << " integers: ";
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
// Bubble Sort
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n-i-1; j++) {
if(arr[j] > arr[j+1]) {
// Swap elements
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
cout << "Array sorted in ascending order: ";
for(int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Output
Enter number of elements: 5
Enter 5 integers: 45 12 67 23 9
Array sorted in ascending order: 9 12 23 45 67
Applications of Bubble Sort
● Educational Purposes: Ideal for teaching and learning basic sorting algorithms.
● Small Datasets: Suitable for sorting small lists where simplicity is more important
than efficiency.
● Partially Sorted Data: Performs well on nearly sorted data, making it useful in
scenarios where data is mostly ordered.
● Computer Graphics: Sometimes used in simple graphics applications where small
arrays need sorting.
2. Insertion sort
Insertion sort is a simple sorting algorithm that works by iteratively inserting each element
of an unsorted list into its correct position in a sorted portion of the list. It is like sorting
playing cards in your hands. You split the cards into two groups: the sorted cards and the
unsorted cards. Then, you pick a card from the unsorted group and put it in the right place in
the sorted group.
● We start with the second element of the array as the first element is assumed to
be sorted.
● Compare the second element with the first element if the second element is
smaller then swap them.
● Move to the third element, compare it with the first two elements, and put it in its
correct position
● Repeat until the entire array is sorted.
How it works:
1. Take the first value from the unsorted part of the array.
2. Move the value into the correct place in the sorted part of the array.
3. Go through the unsorted part of the array again as many times as there are values.
Complexity Analysis of Insertion Sort
Time Complexity
● Best case: O(n), If the list is already sorted, where n is the number of elements in
the list.
● Average case: O(n2), If the list is randomly ordered
● Worst case: O(n2), If the list is in reverse order
Space Complexity
● Auxiliary Space: O(1), Insertion sort requires O(1) additional space, making it a
space-efficient sorting algorithm.
Algorithm
1. insertionSort(array):
2. for i from 1 to length(array) - 1:
3. key = array[i]
4. j=i-1
5. while j >= 0 and array[j] > key:
6. array[j + 1] = array[j]
7. j=j-1
8. array[j + 1] = key
Program to sort an array of integers in ascending order using insertion sort.
#include <iostream>
using namespace std;
// Function to perform insertion sort
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // Current element to be placed
int j = i - 1;
// Move elements greater than key one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // Place key in correct position
}
}
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
int arr[n];
cout << "Enter " << n << " integers: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
insertionSort(arr, n);
cout << "Sorted array in ascending order: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Output
Enter number of elements: 5
Enter 5 integers: 64 25 12 22 11
Sorted array in ascending order: 11 12 22 25 6
Insertion Sort Advantages
● Easy to understand and implement compared to other complex sorting algorithms.
● Performs well for small arrays or lists due to low overhead.
● Efficient for data that is already substantially sorted. In the best case (when the array
is already sorted), the time complexity is O(n).
● Maintains the relative order of records with equal keys (i.e., it does not change the
order of equal elements).
● Requires only a constant amount (O(1)) of additional memory space, as it sorts the
array in place.
● Can sort a list as it receives it. This means it can sort data dynamically as new data
comes in.
Insertion Sort Disadvantages
● The time complexity of O(n^2) makes it inefficient for large lists or arrays compared
to more advanced algorithms like Quick Sort, Merge Sort, or Heap Sort.
● Requires more comparisons and shifts in the worst case (when the array is sorted in
reverse order), which can be time-consuming.
● For large datasets or when performance is critical, other sorting algorithms are
generally more suitable.
● Due to the frequent shifting of elements, it may not perform well with cache memory
in comparison to algorithms like Quick Sort.
Applications of Insertion Sorting Algorithm
● Small Data Sets: Efficient for sorting small lists or arrays due to its low overhead.
● Partially Sorted Data: Ideal for arrays that are already partially sorted, as it can
quickly finish the sorting.
● Real-Time Systems: Useful in systems where the data is continuously received and
needs to be sorted in real-time.
● Adaptive Sorting: Employed in situations where the data is nearly sorted or when new
elements are frequently added to a sorted array.
● Educational Purposes: Often used in teaching fundamental sorting concepts and
algorithms due to its simplicity.
● Hybrid Sorting Algorithms: Used as a part of more complex algorithms like Timsort,
which combines insertion sort with merge sort for improved performance on
real-world data.
3. Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly
selecting the smallest (or largest) element from the unsorted portion and swapping it with
the first unsorted element. This process continues until the entire array is sorted.
1. First we find the smallest element and swap it with the first element. This way we
get the smallest element at its correct position.
2. Then we find the smallest among remaining elements (or second smallest) and
swap it with the second element.
3. We keep doing this until we get all elements moved to the correct position.
How it works:
1. Go through the array to find the lowest value.
2. Move the lowest value to the front of the unsorted part of the array.
3. Go through the array again as many times as there are values in the array.
Complexity Analysis of Selection Sort
Time Complexity: O(n2) ,as there are two nested loops:
● One loop to select an element of Array one by one = O(n)
● Another loop to compare that element with every other Array element = O(n)
● Therefore overall complexity = O(n) * O(n) = O(n*n) = O(n2)
Auxiliary Space: O(1) as the only extra memory used is for temporary variables.
Algorithm
Let’s understand the algorithm of selection sort in data structure:
1. SelectionSort(array)
2. for i from 0 to length(array) - 1 do
3. min_index = i
4. for j from i + 1 to length(array) do
5. if array[j] < array[min_index] then
6. min_index = j
7. swap(array[i], array[min_index])
Program to sort an array of integers in ascending order using selection sort.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n];
cout << "Enter " << n << " integers:" << endl;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// Selection Sort
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
cout << "Sorted array in ascending order:" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Output:
Enter the number of elements: 6
Enter 6 integers:
29 10 14 37 13 5
Sorted array in ascending order:
5 10 13 14 29 37
Advantages of Selection Sort
Simple Implementation: Easy to understand and implement.
In-Place Sorting: Requires only a constant amount of additional memory (O(1) space
complexity).
Performance on Small Arrays: Works efficiently for small arrays or lists.
Predictable Performance: Always performs the same number of comparisons regardless of
the initial order of the elements.
Works Well on Lists with Few Unique Elements: Performs relatively well when sorting lists
with a small number of unique elements.
Disadvantages of Selection Sort
Inefficient for Large Data Sets: Time complexity of O(n^2) makes it impractical for large
arrays or lists.
Not Stable: Does not preserve the relative order of equal elements.
High Number of Comparisons: Always makes n*(n-1)/2 comparisons, even if the array is
already sorted.
Poor Performance on Nearly Sorted Data: Unlike insertion sort, it does not take advantage of
the fact that the array might be partially sorted.
Applications of Selection Sort
Educational Purposes: Used to teach basic concepts of sorting algorithms due to its
simplicity.
Small Data Sets: Suitable for sorting small arrays or lists where the overhead of more
complex algorithms is not justified.
Memory-Constrained Environments: Works well in environments with limited memory due to
its O(1) space complexity.
Sorting Arrays with Few Unique Elements: Efficient when dealing with arrays that contain a
small number of unique elements.
Initial Steps in More Complex Algorithms: Sometimes used as a preliminary step in more
complex sorting algorithms or hybrid algorithms for small data sets.
4. Quick Sort
QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a
pivot and partitions the given array around the picked pivot by placing the pivot in its correct
position in the sorted array.
It works on the principle of divide and conquer, breaking down the problem into smaller
sub-problems.
There are mainly three steps in the algorithm:
1. Choose a Pivot: Select an element from the array as the pivot. The choice of pivot
can vary (e.g., first element, last element, random element, or median).
2. Partition the Array: Re arrange the array around the pivot. After partitioning, all
elements smaller than the pivot will be on its left, and all elements greater than
the pivot will be on its right. The pivot is then in its correct position, and we obtain
the index of the pivot.
3. Recursively Call: Recursively apply the same process to the two partitioned
sub-arrays (left and right of the pivot).
4. Base Case: The recursion stops when there is only one element left in the
sub-array, as a single element is already sorted.
How it works:
1. Choose a value in the array to be the pivot element.
2. Order the rest of the array so that lower values than the pivot element are on the left,
and higher values are on the right.
3. Swap the pivot element with the first element of the higher values so that the pivot
element lands in between the lower and higher values.
4. Do the same operations (recursively) for the sub-arrays on the left and right side of
the pivot element.
Complexity Analysis of Quick Sort
Time Complexity:
● Best Case: (Ω(n log n)), Occurs when the pivot element divides the array into two
equal halves.
● Average Case (θ(n log n)), On average, the pivot divides the array into two parts,
but not necessarily equal.
● Worst Case: (O(n²)), Occurs when the smallest or largest element is always
chosen as the pivot (e.g., sorted arrays).
Auxiliary Space:
● Worst-case scenario: O(n) due to unbalanced partitioning leading to a skewed
recursion tree requiring a call stack of size O(n).
● Best-case scenario: O(log n) as a result of balanced partitioning leading to a
balanced recursion tree with a call stack of size O(log n).
Quick Sort Algorithm
Let’s understand the algorithm for quick sort:
1. QuickSort(arr, low, high)
2. if low < high then
3. pivot_index = Partition(arr, low, high)
4. QuickSort(arr, low, pivot_index - 1)
5. QuickSort(arr, pivot_index + 1, high)
6.
7. Partition(arr, low, high)
8. pivot = arr[high]
9. i = low - 1
10. for j from low to high - 1 do
11. if arr[j] <= pivot then
12. i=i+1
13. swap arr[i] with arr[j]
14. swap arr[i + 1] with arr[high]
15. return i + 1
Program to sort an array of integers in ascending order using quick sort.
#include <iostream>
using namespace std;
// Function to swap two elements
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // choose last element as pivot
int i = low - 1; // index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) { // if current element < pivot
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]); // place pivot at correct position
return i + 1;
}
// Quick Sort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // partition index
quickSort(arr, low, pi - 1); // sort left subarray
quickSort(arr, pi + 1, high); // sort right subarray
}
}
// Driver code
int main() {
int n;
cout << "Enter number of elements: ";
cin >> n;
int arr[n];
cout << "Enter elements: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Output
Enter number of elements: 6
Enter elements: 10 7 8 9 1 5
Sorted array: 1 5 7 8 9 10
Advantages of Quick Sort
● Efficient Average Case: O(n log n) time complexity on average, making it faster for
most inputs.
● In-Place Sorting: Requires minimal additional memory, typically O(log n) space.
● Widely Used: Commonly used in practice due to its efficiency and simplicity.
● Divide and Conquer: Effectively handles large datasets by breaking them into smaller
subproblems.
Disadvantages of Quick Sort
● Worst-Case Performance: Can degrade to O(n²) time complexity if the pivot choices
are poor (e.g., when the array is already sorted).
● Not Stable: Does not preserve the relative order of equal elements unless modified.
● Recursive Overhead: Recursive nature can lead to stack overflow for large arrays or
deep recursion, especially in the worst case.
● Performance Depends on Pivot Selection: Choosing an optimal pivot is crucial; poor
choices can significantly impact performance.
Applications of Quick Sort
● General-Purpose Sorting: Often used for sorting arrays and lists in various
programming languages due to its efficiency.
● Divide and Conquer Algorithms: Forms the basis for other algorithms that use
divide-and-conquer techniques.
● Database Query Optimization: Used in database systems to optimize query
processing by efficiently sorting large datasets.
● Search Algorithms: Helps in efficient searching by sorting data beforehand.
● Memory-Constrained Environments: Suitable for in-place sorting where memory
usage needs to be minimized.
● Real-Time Systems: Quick execution time makes it useful in systems requiring fast
response times.
● Parallel Algorithms: Can be parallelized effectively, making it suitable for
high-performance computing tasks.
● Algorithm Education: Widely taught in computer science courses as an example of
an efficient, comparison-based sorting algorithm.
5. Merge Sort
Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the
Divide and Conquer approach. It works by recursively dividing the input array into two halves,
recursively sorting the two halves and finally merging them back together to obtain the
sorted array.
Here's a step-by-step explanation of how merge sort works:
1. Divide: Divide the list or array recursively into two halves until it can no more be
divided.
2. Conquer: Each subarray is sorted individually using the merge sort algorithm.
3. Merge: The sorted subarrays are merged back together in sorted order. The
process continues until all elements from both subarrays have been merged.
What is Merge Sort?
Merge sort is a way to sort a list of items, like numbers or names, in order. Imagine you have
a big pile of mixed-up playing cards, and you want to sort them. You can break the pile into
smaller groups, sort each group, and then put the groups back together in order.
For example, if you have two sorted lists, like [3, 8] and [2, 7], you compare the first items in
each list. Since 2 is smaller than 3, you put 2 in the new list first. Then you compare 3 and 7.
Since 3 is smaller, you add 3 next. You keep doing this until all items are merged into one
sorted list.
Complexity Analysis of Merge Sort
Time Complexity:
● Best Case: O(n log n), When the array is already sorted or nearly sorted.
● Average Case: O(n log n), When the array is randomly ordered.
● Worst Case: O(n log n), When the array is sorted in reverse order.
Auxiliary Space: O(n), Additional space is required for the temporary array used during
merging.
Merge Sort Algorithm
1. MergeSort(array)
2. if length(array) > 1 then
3. mid = length(array) // 2
4. leftHalf = array[0:mid]
5. rightHalf = array[mid:length(array)]
6.
7. MergeSort(leftHalf)
8. MergeSort(rightHalf)
9.
10. i=j=k=0
11.
12. while i < length(leftHalf) and j < length(rightHalf) do
13. if leftHalf[i] < rightHalf[j] then
14. array[k] = leftHalf[i]
15. i=i+1
16. else
17. array[k] = rightHalf[j]
18. j=j+1
19. k=k+1
Program to sort an array of integers in ascending order using merge sort.
#include <iostream>
using namespace std;
// Function to merge two subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
int L[n1], R[n2]; // Temporary arrays
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the two subarrays
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Function to implement merge sort
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
int main() {
int arr[100], n;
cout << "Enter number of elements: ";
cin >> n;
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
mergeSort(arr, 0, n - 1);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Output
Enter number of elements: 5
Enter 5 elements: 8 3 5 2 9
Sorted array: 2 3 5 8 9
Advantages of Merge Sort
● Consistent Time Complexity: O(n log n) time complexity in all cases (best, average,
worst).
● Stable Sorting: Maintains the relative order of equal elements.
● Efficient for Large Data Sets: Handles large arrays or lists efficiently.
● Parallelizable: Can be easily parallelized due to its divide-and-conquer nature.
● Predictable Performance: Performance does not degrade based on input data
characteristics.
Disadvantages of Merge Sort
● High Space Complexity: Requires O(n) additional space for merging.
● Complex Implementation: More complex to implement compared to simpler
algorithms like insertion sort or selection sort.
● Not In-Place: Uses extra space for temporary subarrays, which can be a limitation for
memory-constrained environments.
● Overhead for Small Arrays: For small arrays, the overhead of recursive calls and
merging can make it slower than simpler algorithms like insertion sort.
Applications of Merge Sort
● Large Data Sets: Efficiently sorts large arrays or lists due to its O(n log n) time
complexity.
● External Sorting: Suitable for sorting large data sets that do not fit into memory (e.g.,
external merge sort).
● Stable Sort Requirement: Used when maintaining the relative order of equal elements
is important.
● Linked Lists: Efficient for sorting linked lists, as it does not require random access to
elements.
● Parallel Processing: Can be easily parallelized, making it useful in multi-threaded or
distributed environments.
● Inversion Count Problems: Used in counting the number of inversions in an array, a
measure of how far the array is from being sorted.
6. Heap Sort
Heap sort is a comparison-based sorting technique based on Binary Heap Data Structure. It
can be seen as an optimization over selection sort where we first find the max (or min)
element and swap it with the last (or first). We repeat the same process for the remaining
elements. In Heap Sort, we use Binary Heap so that we can quickly find and move the max
element in O(Log n) instead of O(n) and hence achieve the O(n Log n) time complexity.
Heap Sort Algorithm
First convert the array into a max heap using heapify, Please note that this happens in-place.
The array elements are re-arranged to follow heap properties. Then one by one delete the
root node of the Max-heap and replace it with the last node and heapify. Repeat this process
while size of heap is greater than 1.
● Rearrange array elements so that they form a Max Heap.
● Repeat the following steps until the heap contains only one element:
○ Swap the root element of the heap (which is the largest element in
current heap) with the last element of the heap.
○ Remove the last element of the heap (which is now in the correct
position). We mainly reduce heap size and do not remove element
from the actual array.
○ Heapify the remaining elements of the heap.
● Finally we get sorted array.
What is Heap Sort?
Heap sort is a way to sort a list of items, like numbers, in order. It uses a special tree
structure called a heap. A heap is a kind of binary tree where each parent node is greater
than or equal to its child nodes. This helps in easily finding the largest or smallest item.
Here’s how it works:
● Build a Heap: First, we arrange the list of numbers into a heap. This makes sure the
largest number is at the top of the heap.
● Remove the Top: Then, we remove the top (the largest number) and place it at the
end of the list.
● Rebuild the Heap: After removing the top, we rebuild the heap with the remaining
numbers.
● Repeat: We keep repeating the process of removing the top and rebuilding the heap
until all numbers are sorted.
By repeatedly moving the largest number to the end of the list and restructuring the heap, we
end up with a sorted list. Heap sort is efficient and works well for large lists.
Complexity Analysis of Heap Sort
Time Complexity: O(n log n)
Auxiliary Space: O(log n), due to the recursive call stack. However, auxiliary space can be
O(1) for iterative implementation.
Important points about Heap Sort
● An in-place algorithm.
● Its typical implementation is not stable but can be made stable
● Typically 2-3 times slower than well-implemented QuickSort. The reason for
slowness is a lack of locality of reference.
Heap Sort Algorithm
1. HeapSort(array)
2. n = length(array)
3. // Build a max heap
4. for i from n/2 - 1 to 0 do
5. heapify(array, n, i)
6. // One by one extract elements from the heap
7. for i from n-1 to 0 do
8. swap(array[0], array[i])
9. heapify(array, i, 0)
10.heapify(array, n, i)
11. largest = i
12. left = 2 * i + 1
13. right = 2 * i + 2
14. if left < n and array[left] > array[largest] then
15. largest = left
16. if right < n and array[right] > array[largest] then
17. largest = right
18. if largest != i then
19. swap(array[i], array[largest])
20. heapify(array, n, largest)
Advantages of Heap Sort
● Consistent Time Complexity: O(n log n) for best, average, and worst cases.
● In-Place Sorting: Requires only a constant amount of additional memory (O(1) space
complexity).
● Not Recursive: Can be implemented iteratively, avoiding the risk of stack overflow in
recursive algorithms.
● Efficient for Large Data Sets: Handles large arrays efficiently.
Disadvantages of Heap Sort
● Unstable Sorting: Does not maintain the relative order of equal elements.
● More Complex Implementation: More complex to implement compared to simpler
sorting algorithms like insertion sort or selection sort.
● Less Cache-Friendly: Access patterns can lead to less efficient use of the CPU cache
compared to algorithms like quicksort.
● Not Adaptive: Performance does not improve for partially sorted arrays.
Applications of Heap Sort
● Sorting Large Data Sets: Efficiently handles large arrays or lists due to its O(n log n)
time complexity.
● Priority Queues: Used to implement priority queues where elements are processed
based on priority.
● Real-Time Systems: Suitable for real-time systems that require guaranteed time
complexity.
● Heapsort for External Sorting: Useful in external sorting algorithms where data is too
large to fit into memory.
● Graph Algorithms: Applied in algorithms like Dijkstra's shortest path and Prim's
minimum spanning tree, which utilize heap structures.
● Event Simulation Systems: Used in discrete event simulation systems where the next
event needs to be processed in priority order.