Sorting Algorithms

Algorithms Sorting & Search

Sorting is a fundamental algorithmic problem where we arrange elements in a specific order. Understanding various sorting algorithms helps you choose the right approach for different scenarios and builds foundation for more complex algorithms.

Why Sorting Matters

Sorting is one of the most fundamental operations in computer science. It arranges data in a specific order, making it easier to search, analyze, and process. Many algorithms depend on sorted data to work efficiently.

Benefits of Sorted Data:

Faster searching with binary search (O(log n) vs O(n))
Easier to find duplicates or missing elements
Better data visualization and analysis
Required for many advanced algorithms

Simple Sorting Algorithms

Let's start with basic sorting algorithms that are easy to understand and implement:

Bubble Sort

Repeatedly compares adjacent elements and swaps them if they're in the wrong order.


void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Selection Sort

Finds the minimum element and places it at the beginning, then repeats for the rest.


void selectionSort(vector<int>& arr) {
    int n = arr.size();
    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(arr[i], arr[minIndex]);
    }
}

Efficient Sorting Algorithms

These algorithms are much faster for larger datasets:

Merge Sort

Divides the array into halves, sorts them recursively, then merges the sorted halves.


void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    for (i = left; i <= right; i++) {
        arr[i] = temp[i - left];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Using STL Sort

C++ provides highly optimized sorting functions in the Standard Template Library:


#include <algorithm>
#include <vector>

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    
    // Sort in ascending order
    sort(arr.begin(), arr.end());
    
    // Sort in descending order
    sort(arr.begin(), arr.end(), greater<int>());
    
    // Custom comparator for sorting pairs by second element
    vector<pair<int, int>> pairs = {{1, 5}, {2, 3}, {3, 8}};
    sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
        return a.second < b.second;
    });
    
    return 0;
}

Binary Search

Once data is sorted, we can use binary search to find elements efficiently:


int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;  // Found target
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;  // Target not found
}

// Using STL binary search
bool found = binary_search(arr.begin(), arr.end(), target);

Time Complexity Comparison

Algorithm Performance:

Bubble Sort: O(n²) - Very slow for large data
Selection Sort: O(n²) - Slightly better than bubble sort
Insertion Sort: O(n²) - Good for small or nearly sorted data
Merge Sort: O(n log n) - Consistent performance
Quick Sort: O(n log n) average, O(n²) worst case
STL sort: O(n log n) - Highly optimized

When to Use Each Algorithm

Choosing the Right Sort

Small arrays (< 10 elements): Insertion sort is often fastest
Nearly sorted data: Insertion sort performs well
General purpose: Use STL sort() - it's highly optimized
Stable sorting needed: Use stable_sort() to preserve equal elements' order
Custom sorting criteria: Use sort() with custom comparator

owlingcode