Data Structures & Algorithms
Table of content:
- What Is Data Structure?
- Key Features Of Data Structures
- Basic Terminologies Related To Data Structures
- Types Of Data Structures
- What Are Linear Data Structures & Its Types?
- What Are Non-Linear Data Structures & Its Types?
- Importance Of Data Structure In Programming
- Basic Operations On Data Structures
- Applications Of Data Structures
- Real-Life Applications Of Data Structures
- Linear Vs. Non-linear Data Structures
- What Are Algorithms? The Difference Between Data Structures & Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Asymptotic Notation?
- How Asymptotic Notation Helps In Analyzing Performance
- Types Of Asymptotic Notation
- Big-O Notation (O)
- Omega Notation (Ω)
- Theta Notation (Θ)
- Little-O Notation (o)
- Little-Omega Notation (ω)
- Summary Of Asymptotic Notations
- Real-World Applications Of Asymptotic Notation
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Big O Notation
- Types Of Time Complexity
- Space Complexity In Big O Notation
- How To Determine Big O Complexity
- Best, Worst, And Average Case Complexity
- Applications Of Big O Notation
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Time Complexity?
- Why Do You Need To Calculate Time Complexity?
- The Time Complexity Algorithm Cases
- Time Complexity: Different Types Of Asymptotic Notations
- How To Calculate Time Complexity?
- Time Complexity Of Sorting Algorithms
- Time Complexity Of Searching Algorithms
- Writing And optimizing An algorithm
- What Is Space Complexity And Its Significance?
- Relation Between Time And Space Complexity
- Conclusion
Table of content:
- What Is Linear Data Structure?
- Key Characteristics Of Linear Data Structures
- What Are The Types Of Linear Data Structures?
- What Is An Array Linear Data Structure?
- What Are Linked Lists Linear Data Structure?
- What Is A Stack Linear Data Structure?
- What Is A Queue Linear Data Structure?
- Most Common Operations Performed in Linear Data Structures
- Advantages Of Linear Data Structures
- What Is Nonlinear Data Structure?
- Difference Between Linear & Non-Linear Data Structures
- Who Uses Linear Data Structures?
- Conclusion
- Frequently Asked Questions
Table of content:
- What is a linear data structure?
- What is a non-linear data structure?
- Difference between linear data structure and non-linear data structure
- FAQs about linear and non-linear data structures
Table of content:
- What Is Sorting In Data Structures?
- What Is Bubble Sort?
- What Is Selection Sort?
- What Is Insertion Sort?
- What Is Merge Sort?
- What Is Quick Sort?
- What Is Heap Sort?
- What Is Radix Sort?
- What Is Bucket Sort?
- What Is Counting Sort?
- What Is Shell Sort?
- Choosing The Right Sorting Algorithm
- Applications Of Sorting
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Bubble Sort Algorithm
- Bubble Sort Algorithm
- Implementation Of Bubble Sort In C++
- Time And Space Complexity Analysis Of Bubble Sort Algorithm
- Advantages Of Bubble Sort Algorithm
- Disadvantages Of Bubble Sort Algorithm
- Applications of Bubble Sort Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Merge Sort Algorithm
- Algorithm For Merge Sort
- Implementation Of Merge Sort In C++
- Time And Space Complexity Analysis Of Merge Sort
- Advantages And Disadvantages Of Merge Sort
- Applications Of Merge Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Selection Sort Algorithm
- Algorithmic Approach To Selection Sort
- Implementation Of Selection Sort Algorithm
- Complexity Analysis Of Selection Sort
- Comparison Of Selection Sort With Other Sorting Algorithms
- Advantages And Disadvantages Of Selection Sort
- Application Of Selection Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Insertion Sort Algorithm?
- How Does Insertion Sort Work? (Step-by-Step Explanation)
- Implementation of Insertion Sort in C++
- Time And Space Complexity Of Insertion Sort
- Applications Of Insertion Sort Algorithm
- Comparison With Other Sorting Algorithms
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Quick Sort Algorithm
- Step-By-Step Working Of Quick Sort
- Implementation Of Quick Sort Algorithm
- Time Complexity Analysis Of Quick Sort
- Advantages Of Quick Sort Algorithm
- Disadvantages Of Quick Sort Algorithm
- Applications Of Quick Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Heap Data Structure
- Working Of Heap Sort Algorithm
- Implementation Of Heap Sort Algorithm
- Advantages Of Heap Sort
- Disadvantages Of Heap Sort
- Real-World Applications Of Heap Sort
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Counting Sort Algorithm
- Conditions For Using Counting Sort Algorithm
- How Counting Sort Algorithm Works?
- Implementation Of Counting Sort Algorithm
- Time And Space Complexity Analysis Of Counting Sort
- Comparison Of Counting Sort With Other Sorting Algorithms
- Advantages Of Counting Sort Algorithm
- Disadvantages Of Counting Sort Algorithm
- Applications Of Counting Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding Shell Sort Algorithm
- Working Of Shell Sort Algorithm
- Implementation Of Shell Sort Algorithm
- Time Complexity Analysis Of Shell Sort Algorithm
- Advantages Of Shell Sort Algorithm
- Disadvantages Of Shell Sort Algorithm
- Applications Of Shell Sort Algorithm
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is The Binary Search Algorithm?
- Conditions For Using Binary Search
- Steps For Implementing Binary Search
- Iterative Method For Binary Search With Implementation Examples
- Recursive Method For Binary Search
- Complexity Analysis Of Binary Search Algorithm
- Iterative Vs. Recursive Implementation Of Binary Search
- Advantages & Disadvantages Of Binary Search
- Practical Applications & Real-World Examples Of Binary Search
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Linked List In Data Structures?
- Types Of Linked Lists In Data Structures
- Linked List Operations In Data Structures
- Advantages And Disadvantages Of Linked Lists In Data Structures
- Comparison Of Linked Lists And Arrays
- Applications Of Linked Lists
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is A Singly Linked List In Data Structure?
- Insertion Operations On Singly Linked Lists
- Deletion Operation On Singly Linked List
- Searching For Elements In Single Linked List
- Calculating Length Of Single Linked List
- Practical Applications Of Singly Linked Lists In Data Structure
- Common Problems With Singly Linked Lists
- Conclusion
- Frequently Asked Questions (FAQ)
Table of content:
- What Is A Linked List?
- Reverse A Linked List
- How To Reverse A Linked List? (Approaches)
- Recursive Approach To Reverse A Linked List
- Iterative Approach To Reverse A Linked List
- Using Stack To Reverse A Linked List
- Complexity Analysis Of Different Approaches To Reverse A Linked List
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is A Graph Data Structure?
- Importance Of Graph Data Structures
- Types Of Graphs In Data Structure
- Types Of Graph Algorithms
- Application Of Graphs In Data Structures
- Challenges And Complexities In Graphs
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Tree Data Structure?
- Terminologies Of Tree Data Structure:
- Different Types Of Tree Data Structures
- Basic Operations On Tree Data Structure
- Applications Of Tree Data Structures
- Comparison Of Trees, Graphs, And Linear Data Structures
- Advantages Of Tree Data Structure
- Disadvantages Of Tree Data Structure
- Conclusion
- Frequently Asked Questions
Table of content:
- What Is Dynamic Programming?
- Real-Life Example: The Jigsaw Puzzle Analogy
- How To Solve A Problem Using Dynamic Programming?
- Dynamic Programming Algorithm Techniques
- Advantages Of Dynamic Programming
- Disadvantages Of Dynamic Programming
- Applications Of Dynamic Programming
- Conclusion
- Frequently Asked Questions
Table of content:
- Understanding The Sliding Window Algorithm
- How Does The Sliding Window Algorithm Works?
- How To Identify Sliding Window Problems?
- Fixed-Size Sliding Window Example: Maximum Sum Subarray Of Size k
- Variable-Size Sliding Window Example: Smallest Subarray With A Given Sum
- Advantages Of Sliding Window Technique
- Disadvantages Of Sliding Window Technique
- Conclusion
- Frequently Asked Questions
Table of content:
- Introduction To Data Structures
- Data Structures Interview Questions: Basics
- Data Structures Interview Questions: Intermediate
- Data Structures Interview Questions: Advanced
- Conclusion
Sorting In Data Structures - All Techniques Explained (+Examples)

Sorting is a fundamental concept in data structures and algorithms, where the elements of a collection are arranged in a specific order, such as ascending or descending. This process improves data organization, making it easier to search, analyze, and process. From simple methods like Bubble Sort to more advanced techniques like Quick Sort and Merge Sort, sorting algorithms play a vital role in optimizing performance in various applications. In this article, we’ll explore key sorting techniques, their working mechanisms, and use cases to help you understand their importance and implementation.
What Is Sorting In Data Structures?
Sorting in data structures is the process of arranging data elements in a specific order—ascending or descending—based on a particular criterion. Sorting is a fundamental operation because it makes searching, organizing, and analyzing data more efficient. For instance, sorting a list of names alphabetically or numbers in increasing order simplifies the retrieval process.
Types Of Sorting Techniques
Here’s a table that provides the types of sorting techniques in data structures:
Type of Sorting |
Definition |
Time Complexity (Best / Average / Worst) |
Space Complexity |
Bubble Sort |
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. |
O(n) / O(n²) / O(n²) |
O(1) |
Selection Sort |
Divides the list into sorted and unsorted parts, repeatedly selecting the smallest (or largest) element and moving it to the sorted part. |
O(n²) / O(n²) / O(n²) |
O(1) |
Insertion Sort |
Builds the final sorted array one element at a time by comparing each new element to those already sorted and inserting it in its correct position. |
O(n) / O(n²) / O(n²) |
O(1) |
Merge Sort |
A divide-and-conquer algorithm that splits the array into halves, recursively sorts each half, and merges the sorted halves into one. |
O(n log n) / O(n log n) / O(n log n) |
O(n) |
Quick Sort |
Picks a pivot, partitions the array around it, and recursively sorts the partitions. |
O(n log n) / O(n log n) / O(n²) |
O(log n) (due to recursion) |
Heap Sort |
Based on a binary heap structure; repeatedly extracts the largest (or smallest) element to build the sorted array. |
O(n log n) / O(n log n) / O(n log n) |
O(1) |
Radix Sort |
A non-comparison algorithm that processes digits of numbers from least to most significant. |
O(nk) / O(nk) / O(nk) (n = no. of elements, k = digits) |
O(n + k) |
Bucket Sort |
Divides the array into buckets, sorts each bucket, and combines them. |
O(n + k) / O(n + k) / O(n²) |
O(n + k) |
Counting Sort |
Counts occurrences of elements to determine their sorted order. |
O(n + k) / O(n + k) / O(n + k) (k = range of numbers) |
O(k) |
Shell Sort |
An optimized version of insertion sort that sorts elements far apart to reduce comparisons, progressively narrowing the gap. |
O(n log n) / O(n log² n) / O(n²) |
O(1) |
What Is Bubble Sort?
Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. The name "Bubble Sort" comes from the way smaller elements "bubble" to the top (beginning of the list) with each pass.
How It Works:
- Compare the first and second elements of the list.
- If the first element is greater than the second, swap them.
- Move to the next pair of elements and repeat the process.
- After each pass, the largest unsorted element is "bubbled" to the end of the list.
- Repeat the process for the remaining unsorted part of the list.
Bubble Sort Syntax (In C++):
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// Swap the elements if they are in the wrong order
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
Code Example:
#include <iostream>
using namespace std;
// Function to implement Bubble Sort
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap the elements if they are in the wrong order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
bubbleSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90
Explanation:
In the above code example-
- bubbleSort Function: This function sorts the array using Bubble Sort. It has two nested loops:
- The outer loop runs n-1 times (where n is the number of elements).
- The inner loop compares adjacent elements and swaps them if necessary.
- printArray Function: This function prints the elements of the array.
- main() Function: The array is defined, and then both the unsorted and sorted arrays are printed before and after calling the bubbleSort function.
What Is Selection Sort?
Selection Sort is a simple sorting algorithm that divides the list into two parts: the sorted part and the unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.
How It Works:
- Find the smallest (or largest) element in the unsorted part of the array.
- Swap it with the first element of the unsorted part.
- Repeat the process for the remaining unsorted part until the entire array is sorted.
Selection Sort Syntax (In C++)
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIdx = i; // Index of the minimum element
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j; // Update index of the smallest element
}
}
// Swap the found minimum element with the first element of the unsorted part
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
Code Example:
#include <iostream>
using namespace std;
// Function to implement Selection Sort
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i; // Index of the minimum element
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j; // Update index of the smallest element
}
}
// Swap the found minimum element with the first element of the unsorted part
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
selectionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 64 25 12 22 11
Sorted array: 11 12 22 25 64
Explanation:
In the above code example-
- In the selectionSort Function:
- The outer loop runs n-1 times (where n is the number of elements).
- For each iteration, the smallest element in the unsorted part is found using the inner loop.
- The smallest element is then swapped with the first element of the unsorted part.
- printArray Function: This function prints the elements of the array.
- main() Function: The array is defined, and both the unsorted and sorted arrays are printed before and after calling the selectionSort function.
What Is Insertion Sort?
Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how we sort playing cards in our hands:
- Start with the second element, compare it with elements before it, and insert it in the correct position.
- Repeat for all elements, ensuring that the array is sorted after each insertion.
How It Works:
- Divide the array into a sorted part and an unsorted part.
- Take the first element of the unsorted part and compare it with the elements of the sorted part.
- Shift elements of the sorted part that are larger than the current element to make space for it.
- Insert the current element in its correct position.
Insertion Sort Syntax (In C++)
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements of the sorted part to make space for the key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // Insert the key in the correct position
}
}
Code Example:
#include <iostream>
using namespace std;
// Function to implement Insertion Sort
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // Current element to be inserted
int j = i - 1;
// Shift elements of the sorted part to make space for the key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // Insert the key in the correct position
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
insertionSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 12 11 13 5 6
Sorted array: 5 6 11 12 13
Explanation:
In the above code example-
- In the insertionSort Function:
- The loop starts with the second element (i = 1) because a single element is already sorted.
- For each element, it finds its correct position in the sorted part of the array.
- Elements larger than the current key are shifted to the right to make space.
- The key is then inserted into its correct position.
- printArray Function: This function prints the elements of the array.
- main() Function: The array is defined, and the unsorted and sorted arrays are printed before and after calling the insertionSort function.
What Is Merge Sort?
Merge Sort is a divide-and-conquer sorting algorithm that recursively divides the array into two halves until each subarray contains only one element, then merges those subarrays to produce a sorted array. It is one of the most efficient sorting algorithms for large datasets.
How It Works:
- Divide: Split the array into two halves recursively until each subarray has only one element.
- Conquer: Merge the subarrays back together in sorted order.
- Combine: Repeat merging until the entire array is sorted.
Merge Sort involves two main functions:
- A recursive function to divide the array.
- A helper function to merge two sorted subarrays.
Code Example:
#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 the first subarray
int n2 = right - mid; // Size of the second subarray
int L[n1], R[n2]; // Temporary arrays for left and right subarrays
// 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];
int i = 0, j = 0, k = left;
// Merge the temporary arrays back into the original array
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);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
mergeSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13
Explanation:
In the above code example-
- merge Function:
- Merges two sorted subarrays L and R into a single sorted array.
- Uses temporary arrays to hold data during merging.
- mergeSort Function:
- Recursively splits the array into two halves.
- Calls the merge function to combine the sorted halves.
- printArray Function: Prints the elements of the array.
- main() Function: Initializes the array, calls the mergeSort function, and prints the array before and after sorting.
What Is Quick Sort?
Quick Sort is a highly efficient and widely used divide-and-conquer sorting algorithm. It selects a "pivot" element, partitions the array around the pivot, and recursively sorts the partitions.
How It Works:
- Choose a Pivot: Select an element as the pivot. Common choices include the first element, the last element, the middle element, or a random element.
- Partitioning: Reorder the array so that:
- Elements less than the pivot are moved to its left.
- Elements greater than the pivot are moved to its right.
- Recursion: Recursively apply the above steps to the left and right partitions.
Quick Sort involves two main functions:
- A partition function that rearranges elements around the pivot.
- A quickSort function that recursively applies the algorithm to subarrays.
Code Example:
#include <iostream>
using namespace std;
// Function to partition the array
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Pivot element
int i = low - 1; // Index of smaller element
// Rearrange elements based on pivot
for (int j = low; j < high; j++) {
if (arr[j] < 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) {
// Partition the array and get the pivot index
int pi = partition(arr, low, high);
// Recursively sort the partitions
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 10 7 8 9 1 5
Sorted array: 1 5 7 8 9 10
Explanation:
In the above code example-
- partition Function:
- Chooses the pivot as the last element.
- Rearranges the array so elements smaller than the pivot are on the left and greater ones are on the right.
- Returns the index of the pivot.
- quickSort Function: Recursively applies Quick Sort to the left and right subarrays around the pivot.
- printArray Function: Prints the elements of the array.
- main() Function: Initializes the array, calls quickSort, and prints the results.
What Is Heap Sort?
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It is an in-place and non-recursive sorting technique that efficiently organizes and retrieves elements.
How It Works:
- Build a Max Heap: Construct a binary heap from the input array, ensuring the largest element is at the root.
- Extract Elements: Repeatedly remove the root (maximum element) of the heap, place it at the end of the array, and reduce the heap size.
- Heapify: Restore the heap property after each extraction to maintain the max heap structure.
Heap Sort involves two key operations:
- Heapify: Maintains the max heap property.
- Heap Sort Function: Builds the heap and sorts the array.
Code Example:
#include <iostream>
using namespace std;
// Function to maintain the heap property
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize the largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// Check if left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// Check if right child is larger than the largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// If the largest is not root, swap and continue heapifying
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// Function to perform Heap Sort
void heapSort(int arr[], int n) {
// Build the max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from the heap one by one
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]); // Move the current root to the end
heapify(arr, i, 0); // Reheapify the reduced heap
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
heapSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13
Explanation:
In the above code example-
- heapify Function:
- Ensures the max heap property (parent is larger than its children).
- Recursively adjusts the heap if the largest element is not at the root.
- heapSort Function:
- Builds the initial max heap from the array.
- Extracts the largest element (root) and places it at the end of the array.
- Reduces the heap size and re-applies heapify.
- printArray Function: Prints the elements of the array.
What Is Radix Sort?
Radix Sort is a non-comparative, stable sorting algorithm that sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD) or vice versa. It uses counting sort as a subroutine to sort digits.
How It Works:
- Identify the Maximum Element: Determine the maximum number in the array to find the number of digits.
- Sort by Each Digit: Starting from the least significant digit (unit place), sort the numbers using counting sort.
- Repeat for Each Place Value: Move to the next significant digit and repeat until all place values are processed.
Syntax For Radix Sort (In C++)
Radix Sort relies on counting sort to sort numbers at each digit position.
void radixSort(int arr[], int n) {
// Find the maximum number to determine the number of digits
int max = *max_element(arr, arr + n);
// Apply counting sort for each digit
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}
Code Example:
#include <iostream>
#include <algorithm>
using namespace std;
// Function for counting sort
void countingSort(int arr[], int n, int exp) {
int output[n];
int count[10] = {0};
// Count occurrences of digits
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Update count array to hold positions
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// Copy the sorted elements back to the original array
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
// Function for radix sort
void radixSort(int arr[], int n) {
int max = *max_element(arr, arr + n);
// Perform counting sort for each digit
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
radixSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 170 45 75 90 802 24 2 66
Sorted array: 2 24 45 66 75 90 170 802
Explanation:
In the above code example-
- countingSort Function:
- Sorts the array based on the current digit (unit, tens, hundreds, etc.).
- Uses a counting array to track occurrences of digits.
- radixSort Function:
- Determines the number of digits in the largest number.
- Iteratively sorts the array for each digit using countingSort.
- printArray Function: Prints the elements of the array before and after sorting.
What Is Bucket Sort?
Bucket Sort is a distribution-based sorting algorithm that divides the input into several "buckets," sorts each bucket individually, and then combines them to produce a sorted array. It works well when the input data is uniformly distributed over a range.
How It Works:
- Divide the Input into Buckets: The input array is divided into several buckets based on a pre-defined range.
- Sort Each Bucket: Each bucket is sorted individually using another sorting algorithm (commonly Insertion Sort).
- Concatenate the Sorted Buckets: After sorting each bucket, the contents of all buckets are combined to form the final sorted array.
Code Example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to perform insertion sort on each bucket
void insertionSort(vector<int>& bucket) {
int n = bucket.size();
for (int i = 1; i < n; i++) {
int key = bucket[i];
int j = i - 1;
// Shift elements to make space for the key
while (j >= 0 && bucket[j] > key) {
bucket[j + 1] = bucket[j];
j--;
}
bucket[j + 1] = key;
}
}
// Bucket sort function
void bucketSort(int arr[], int n) {
vector<int> buckets[n];
// Step 1: Insert elements into corresponding buckets
for (int i = 0; i < n; i++) {
int index = arr[i] * n; // Index is scaled by the number of buckets
buckets[index].push_back(arr[i]);
}
// Step 2: Sort each bucket and concatenate them
for (int i = 0; i < n; i++) {
insertionSort(buckets[i]);
}
// Step 3: Combine the sorted buckets into the original array
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {0.42, 0.32, 0.23, 0.52, 0.67, 0.31};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
bucketSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 0.42 0.32 0.23 0.52 0.67 0.31
Sorted array: 0.23 0.31 0.32 0.42 0.52 0.67
Explanation:
In the above code example-
- insertionSort Function: Sorts each bucket using Insertion Sort, which is efficient for small datasets.
- bucketSort Function:
- Divides the array into buckets and places elements into the appropriate bucket based on their value.
- Sorts each bucket and combines them back into the original array.
- printArray Function: Prints the elements of the array before and after sorting.
What Is Counting Sort?
Counting Sort is a non-comparative sorting algorithm that counts the number of occurrences of each element in the array and uses that information to place elements in their correct sorted position. It is best suited for sorting integers or objects that can be mapped to non-negative integer values.
How It Works:
- Count Occurrences: Count the frequency of each distinct element in the input array.
- Compute Cumulative Count: Use the frequency counts to compute the cumulative sum, which will indicate the position of each element in the sorted output.
- Place Elements: Place each element from the input array into the correct position in the output array, using the cumulative count.
- Rebuild Sorted Array: After placing all elements in their correct position, the output array is the sorted array.
Counting Sort requires:
- A counting array to store the frequency of each element.
- A cumulative array to determine the position of elements.
Code Example:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Counting sort function
void countingSort(int arr[], int n) {
int max = *max_element(arr, arr + n);
// Create a count array
vector<int> count(max + 1, 0);
// Count the occurrences of each element
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// Update the count array
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Place elements in the sorted order in the output array
int output[n];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the sorted array to the original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
countingSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 4 2 2 8 3 3 1
Sorted array: 1 2 2 3 3 4 8
Explanation:
In the above code example-
- countingSort Function:
- First, it determines the maximum element in the array to define the size of the counting array.
- It counts the occurrences of each element in the arr[].
- The count[] array is then updated by adding the previous counts to make it cumulative.
- The elements are placed into their correct position in the output[] array based on the cumulative count.
- Finally, the sorted elements are copied back into the original array.
- printArray Function: Prints the elements of the array before and after sorting.
What Is Shell Sort?
Shell Sort is an optimization of Insertion Sort that allows the exchange of items that are far apart. The basic idea is to arrange the list of elements so that, starting anywhere, taking every kthk^{th}kth element produces a sorted list. By progressively reducing the gap between elements, Shell Sort efficiently reduces the number of inversions (out-of-order pairs), which leads to improved sorting performance compared to regular Insertion Sort.
How It Works:
- Gap Sequence: Instead of comparing adjacent elements (like Insertion Sort), Shell Sort compares elements that are far apart. It starts by sorting pairs of elements far apart, then progressively reduces the gap between elements being compared.
- Insertion Sort: After comparing and potentially swapping far-apart elements, it sorts the sublists using Insertion Sort.
- Reducing the Gap: The gap between elements is reduced at each step, and this process is repeated until the gap is 1, at which point the algorithm behaves like Insertion Sort.
Code Example:
#include <iostream>
#include <vector>
using namespace std;
// Function to perform Shell Sort
void shellSort(int arr[], int n) {
// Start with a large gap and reduce it
for (int gap = n / 2; gap > 0; gap /= 2) {
// Perform a gapped Insertion Sort
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
// Shift earlier gap-sorted elements up until the correct location is found
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: ";
printArray(arr, n);
shellSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Output:
Unsorted array: 5 2 9 1 5 6
Sorted array: 1 2 5 5 6 9
Explanation:
In the above code example-
- shellSort Function:
- Starts with a gap of n/2, where n is the number of elements in the array.
- In each iteration, the gap is halved until it becomes 1.
- For each gap, the array is sorted using a variation of Insertion Sort, where instead of comparing adjacent elements, it compares elements that are gap positions apart.
- printArray Function: Prints the elements of the array before and after sorting.
Choosing The Right Sorting Algorithm
When selecting a sorting algorithm for a particular problem, several factors should be taken into account to ensure the best performance. The decision depends on the input data characteristics (like size, order, and range) and the specific requirements such as time and space efficiency. Here's a guide to help you choose the right sorting algorithm based on these factors.
Key Factors To Consider:
- Size of the Input Data:
- Small Data: For small arrays (under 1000 elements), simpler algorithms like Insertion Sort or Selection Sort may perform well despite their higher time complexities, as they have low overhead.
- Large Data: For larger datasets, algorithms with better time complexities, such as Merge Sort, Quick Sort, or Heap Sort, are preferred because of their faster performance for large inputs.
- Time Complexity:
- Best Time Complexity: Algorithms with O(n log n) average or worst-case time complexity, like Quick Sort, Merge Sort, and Heap Sort, are efficient for large datasets.
- Worst Time Complexity: For sorting where performance guarantees are critical, Merge Sort is a better choice, as its worst-case time complexity is consistently O(n log n), unlike Quick Sort which can degrade to O(n^2) in the worst case (with bad pivot choices).
- Space Complexity:
- In-place Sorting: If memory usage is a concern (e.g., for large datasets), in-place sorting algorithms like Quick Sort, Heap Sort, and Insertion Sort are preferred, as they use O(1) extra space.
- Extra Space Required: Algorithms like Merge Sort require O(n) extra space, which can be a disadvantage when dealing with large datasets in memory-constrained environments.
- Stability:
- Stable Sorting Algorithms maintain the relative order of records with equal keys. Merge Sort and Bubble Sort are stable, whereas Quick Sort and Heap Sort are not.
- If stability is important (e.g., sorting objects based on one attribute while maintaining the relative order of objects with the same attribute), then Bubble Sort, Merge Sort, or Insertion Sort are good choices.
- Range of Input Elements:
- Counting Sort, Radix Sort, and Bucket Sort can perform much faster than O(n log n) algorithms when the range of input elements is small and can be mapped to integers.
- If the input range is large and non-integer, you may need to use comparison-based algorithms like Quick Sort or Merge Sort.
- Input Order:
- Partially Sorted Data: Algorithms like Insertion Sort are particularly efficient when the data is already partially sorted. In fact, Insertion Sort can run in O(n) time if the input is already sorted or nearly sorted.
- Randomized or Unsorted Data: Quick Sort, Merge Sort, and Heap Sort generally perform well on random or unsorted data.
Applications Of Sorting
Sorting plays a crucial role in various fields of computer science and real-world applications. It is a fundamental operation that optimizes the performance of other algorithms and systems. Here are some key applications of sorting:
1. Searching Algorithms
- Binary Search: Sorting is essential for efficient searching algorithms like Binary Search. Binary Search can only work on sorted arrays or lists, allowing it to find elements in O(log n) time, much faster than linear search, which has a time complexity of O(n).
2. Data Visualization
- Graphing and Charts: Sorting helps in organizing data for easier visualization, such as arranging data points in ascending or descending order before plotting graphs or creating charts. This makes patterns, trends, and outliers more noticeable.
3. Database Management
- Indexing: Many database management systems use sorting to maintain indexes. Sorted data enables faster retrieval, as the search algorithms can take advantage of the sorted structure to locate records quickly.
- Query Optimization: Sorting improves query performance by optimizing the execution of range queries and join operations.
4. File Systems
- Efficient Storage: In file systems, sorting is used to organize files in directories, ensuring that file listings (e.g., names or sizes) are displayed in a sorted order, allowing for quick access.
- Data Compression: Sorting is used in compression algorithms like Huffman coding, where symbols are arranged in a frequency order to minimize the storage space required.
5. Social Media and Online Platforms
- Ranking Algorithms: Sorting plays a key role in ranking systems on social media platforms, e-commerce websites, and news feeds. It helps in organizing content based on relevance, popularity, or user preferences, ensuring that users see the most important or trending content first.
6. Scheduling Algorithms
- Task Scheduling: In operating systems, sorting helps in scheduling tasks. For example, Shortest Job Next (SJN) scheduling algorithm sorts processes based on their burst time to optimize CPU utilization.
- Deadline-based Scheduling: Sorting helps to order tasks by their deadlines, allowing the system to prioritize tasks efficiently.
7. Data Mining
- Clustering and Classification: Sorting can help with data clustering algorithms by grouping similar data points together. It is also used in decision tree algorithms and other classification techniques to organize and rank data.
8. Merchandise Inventory Management
- Stock Sorting: Sorting algorithms are used in inventory management systems to sort stock items based on factors such as price, quantity, or item number, allowing efficient tracking and reporting.
9. Networking Protocols
- Packet Routing: In networking, sorting helps in routing packets based on priority. For example, Quality of Service (QoS) algorithms prioritize network traffic by sorting packets, ensuring that high-priority packets are transmitted first.
10. E-commerce Systems
- Product Listings: E-commerce platforms like Amazon, eBay, and others use sorting to arrange products based on user preferences, such as sorting by price, rating, or newest arrival, to enhance the shopping experience.
11. Genomic Data Analysis
- Sorting DNA Sequences: Sorting plays a crucial role in bioinformatics, especially in sorting DNA sequences or genomic data. It is used in algorithms for sequence alignment, where sequences need to be sorted based on certain criteria, such as length or nucleotide composition.
Conclusion
In conclusion, sorting is a critical operation in data structures that enables efficient data management and retrieval. Whether you're organizing data for search operations, improving performance in algorithms, or optimizing resource usage in large-scale systems, understanding and choosing the right sorting technique is essential. From simple algorithms like Bubble Sort to advanced methods like Quick Sort and Merge Sort, each sorting technique offers distinct advantages depending on the problem at hand.
By considering factors such as dataset size, memory constraints, and time complexity, we can make informed decisions about which algorithm to implement. Sorting remains a foundational concept in computer science, with applications spanning across various domains, making it an indispensable skill for anyone working with data.
Frequently Asked Questions
Q. What is the best sorting algorithm for large datasets?
For large datasets, algorithms like Quick Sort, Merge Sort, and Heap Sort are typically the best choices due to their O(n log n) average time complexity. Merge Sort is particularly useful when stability is important, while Quick Sort is often faster in practice for general use.
Q. Is there a sorting algorithm that works in linear time?
Yes, sorting algorithms like Counting Sort, Radix Sort, and Bucket Sort can achieve linear time complexity O(n) under certain conditions, such as when the range of input values is small or the data is uniformly distributed.
Q. What is the difference between stable and unstable sorting algorithms?
A stable sorting algorithm preserves the relative order of equal elements, meaning that if two elements are equal, their order in the sorted array will remain the same as in the original array. Examples of stable algorithms include Bubble Sort, Merge Sort, and Insertion Sort. Unstable algorithms like Quick Sort and Heap Sort do not guarantee this.
Q. When should I use Insertion Sort over other algorithms?
Insertion Sort is ideal for small or nearly sorted datasets. Its simplicity and low overhead make it an efficient choice for small arrays. It also performs exceptionally well when the data is almost sorted, running in linear time O(n) in the best case.
Q. What is the time complexity of Quick Sort, and why is it so popular?
The average time complexity of Quick Sort is O(n log n), but in the worst case (with poor pivot selection), it can degrade to O(n^2). Despite this, Quick Sort is popular because it often outperforms other algorithms in practice due to its low constant factors and efficient in-place sorting.
Q. Why is Quick Sort often faster than Merge Sort despite having a similar time complexity?
Quick Sort is often faster than Merge Sort in practical use because it has smaller constant factors and performs in-place sorting, which reduces memory usage and overhead. Additionally, Quick Sort is more cache-efficient, making it faster for many real-world datasets. However, Merge Sort guarantees O(n log n) performance in the worst case, while Quick Sort can degrade to O(n^2) if the pivot selection is poor, which is why Quick Sort's performance may vary based on the data.
You may also like to read:
- Dynamic Programming - From Basics To Advanced (+Code Examples)
- Convert String To Date In Java | 3 Different Ways With Examples
- Super Keyword In Java | Definition, Applications & More (+Examples)
- How To Find LCM Of Two Numbers In Java? Simplified With Examples
- How To Find GCD Of Two Numbers In Java? All Methods With Examples
- Volatile Keyword In Java | Syntax, Working, Uses & More (+Examples)
- Throws Keyword In Java | Syntax, Working, Uses & More (+Examples)
I’m a Computer Science graduate with a knack for creative ventures. Through content at Unstop, I am trying to simplify complex tech concepts and make them fun. When I’m not decoding tech jargon, you’ll find me indulging in great food and then burning it out at the gym.
Comments
Add commentLogin to continue reading
And access exclusive content, personalized recommendations, and career-boosting opportunities.

Subscribe
to our newsletter
Indira Mehta 3 days ago
UTKARSH SINGH 6 days ago
Divyansh Shrivastava 1 week ago
Paritosh Sharma 1 week ago
Archana Ba Parmar 1 week ago
Archana Ba Parmar 1 week ago