Sorting in Data Structures - Complete Notes
Definition
Sorting is the process of arranging data in a particular order (ascending or descending) to make it more meaningful,
searchable, and easier to use.
Uses of Sorting
- Searching: Faster search (Binary Search)
- Data Representation: Clean display
- Duplicate Detection
- Helps in Algorithms like Merge, Binary Search
- Data Management
Types of Sorting
1. Comparison-based: Bubble, Selection, Insertion, Merge, Quick, Heap
2. Non-comparison-based: Counting
Bubble Sort
Definition: Compares and swaps adjacent elements.
Time: O(n²), Best: O(n)
Stable: Yes, In-place: Yes
Code:
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]) {
int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
}
}
Selection Sort
Definition: Finds minimum and places it at the start.
Time: O(n²), Stable: No, In-place: Yes
Code:
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min = i;
for (int j = i+1; j < n; j++)
Sorting in Data Structures - Complete Notes
if (arr[j] < arr[min]) min = j;
int temp = arr[min]; arr[min] = arr[i]; arr[i] = temp;
}
}
Insertion Sort
Definition: Inserts each element in the correct place.
Time: Best O(n), Avg/Worst O(n²), Stable: Yes
Code:
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; int j = i - 1;
while (j >= 0 && arr[j] > key)
arr[j + 1] = arr[j--];
arr[j + 1] = key;
}
}
Merge Sort
Definition: Divide and conquer algorithm.
Time: O(n log n), Stable: Yes, In-place: No
Code:
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = (l + r)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
Quick Sort
Definition: Picks pivot, partitions, and sorts recursively.
Time: Avg O(n log n), Worst O(n²), In-place: Yes
Code:
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
Sorting in Data Structures - Complete Notes
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Heap Sort
Definition: Builds max heap, extracts max.
Time: O(n log n), Stable: No, In-place: Yes
Code:
void heapSort(int arr[], int n) {
for (int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;
heapify(arr, i, 0);
}
}
Counting Sort
Definition: Count frequency and place values.
Time: O(n + k), Stable: Yes, In-place: No
Code:
void countingSort(int arr[], int n) {
int count[MAX] = {0}, output[n];
for (int i = 0; i < n; i++) count[arr[i]]++;
for (int i = 1; i < MAX; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--)
output[--count[arr[i]]] = arr[i];
for (int i = 0; i < n; i++) arr[i] = output[i];
}
Summary Table
Bubble: O(n²), Stable, In-place
Selection: O(n²), Not Stable, In-place
Insertion: O(n²), Stable, In-place
Merge: O(n log n), Stable, Not In-place
Quick: O(n log n), Not Stable, In-place
Heap: O(n log n), Not Stable, In-place
Sorting in Data Structures - Complete Notes
Counting: O(n + k), Stable, Not In-place
