Understanding Sorting Algorithms: Simplified Time Complexities

Searching Algorithms and Their Time Complexities

Understanding sorting algorithms is crucial for any programmer. Let’s dive into some common sorting algorithms, their mechanics, and their time complexities.

1. Bubble Sort

Bubble Sort is a simple algorithm that repeatedly swaps adjacent elements to push larger elements to the end of the array.

• Time Complexity:

  • Best Case: O(N) — When the array is already sorted.

  • Worst Case: O(N²) — When the array is sorted in reverse order.

Bubble Sort Algorithm:

void bubbleSort(int *arr, int n) {
    for (int i = 1; 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]);
            }
        }
    }
}

2. Insertion Sort

Insertion Sort builds a sorted array one element at a time by inserting each new element into its correct position in the already sorted part.

• Time Complexity:

  • Best Case: O(N) — When the array is sorted.

  • Worst Case: O(N²) — When the array is in reverse order.

Insertion Sort Algorithm:

void insertionSort(int *arr, int n) {
    for (int i = 1; i <= n - 1; i++) {
        int current = arr[i];
        int prev = i - 1;
        while (prev >= 0 && arr[prev] > current) {
            arr[prev + 1] = arr[prev];
            prev -= 1;
        }
        arr[prev + 1] = current;
    }
}

3. Selection Sort

Selection Sort repeatedly finds the minimum element from the unsorted section and moves it to the front.

• Time Complexity:

  • Best Case: O(N²)

  • Worst Case: O(N²)

Selection Sort Algorithm:

void selectionSort(int *arr, int n) {
    for (int position = 0; position <= n - 2; position++) {
        int currentElement = arr[position];
        int minPosition = position;
        for (int j = position; j < n; j++) {
            if (arr[j] < arr[minPosition]) {
                minPosition = j;
            }
        }
        swap(arr[minPosition], arr[position]);
    }
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
}

4. Quick Sort

Quick Sort is one of the fastest sorting algorithms. It follows the divide-and-conquer paradigm and is efficient in terms of space since it’s an in-place sorting algorithm.

• Time Complexity:

  • Best Case: O(N log N) — When the pivot is the median.

  • Worst Case: O(N²) — When the pivot is the smallest or largest element.

Quick Sort Algorithm:

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

5. Counting Sort

Counting Sort is a non-comparison based sorting algorithm suitable for sorting integers when the range of numbers is known.

• Time Complexity:

  • Best Case: O(N) — When all elements are the same.

  • Worst Case: O(N + K) — When K is the range of the input.

Counting Sort Algorithm:

vector<int> countingSort(vector<int> arr) {
    int n = arr.size();
    int largest = *max_element(arr.begin(), arr.end());
    vector<int> freq(largest + 1, 0);

    for (int x : arr) {
        freq[x]++;
    }

    int j = 0;
    for (int i = 0; i <= largest; i++) {
        while (freq[i] > 0) {
            arr[j] = i;
            freq[i]--;
            j++;
        }
    }
    return arr;
}

6. Merge Sort

Merge Sort is a divide-and-conquer algorithm that uses both recursive and iterative approaches. It's stable and requires additional memory.

• Time Complexity:

  • Best Case: O(N log N) — Always performs the same number of operations.

  • Worst Case: O(N log N)

Merge Sort Algorithm:

void mergeSort(int A[], int size_a, int B[], int size_b, int C[]) {
    int token_a = 0, token_b = 0, token_c = 0;
    while (token_a < size_a && token_b < size_b) {
        if (A[token_a] <= B[token_b]) {
            C[token_c++] = A[token_a++];
        } else {
            C[token_c++] = B[token_b++];
        }
    }

    while (token_a < size_a) {
        C[token_c++] = A[token_a++];
    }
    while (token_b < size_b) {
        C[token_c++] = B[token_b++];
    }
}

---

That wraps up our exploration of sorting algorithms. Each algorithm has its strengths and weaknesses, so understanding when to use them is key to efficient programming.

Until next time, happy coding! ❤️ Be sure to check out my other blogs - I am sure you’ll enjoy them! 🦄