Sorting Algorithms

Sorting Algorithms

Sorting algorithms are fundamental techniques used to rearrange a sequence of elements (numbers, strings, etc.) in a particular order, typically in ascending or descending order. Sorting is crucial in many applications, including searching, data processing, and algorithm optimization. Let's explore several key sorting algorithms in detail, focusing on their approaches and complexity.

1. Selection Sort

Selection sort is a simple, inefficient sorting algorithm that works by repeatedly finding the minimum (or maximum) element and placing it at the beginning (or end) of the unsorted portion of the array.

Steps:

1. Find the smallest element in the array and swap it with the first element.
2. Repeat the process for the remaining unsorted portion of the array.

Example:

For an array [64, 25, 12, 22, 11]:

1. Find the minimum (11) and swap with 64.
2. Repeat the process for the remaining elements.

Code in C++:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        swap(arr[i], arr[min_idx]);
    }
}

Time Complexity:

• Best, Worst, and Average Case: O(n²)
• Space Complexity: O(1)

2. Insertion Sort

Insertion sort builds the sorted array one element at a time. It works similarly to sorting playing cards in your hand. It repeatedly picks the next element and places it in its correct position in the already sorted portion.

Steps:

1. Start with the second element.
2. Compare it with the elements before it, and insert it into the correct position.

Code in C++:

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];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Time Complexity:

• Best Case: O(n) (already sorted array)
• Worst and Average Case: O(n²)
• Space Complexity: O(1)

3. Merge Sort

Merge sort is a stable, efficient sorting algorithm that uses the divide and conquer technique. It divides the array into two halves, recursively sorts each half, and then merges the sorted halves.

Steps:

1. Divide the array into two halves.
2. Recursively sort the two halves.
3. Merge the two sorted halves.

Code in C++:

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(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);
    }
}

Time Complexity:

• Best, Worst, and Average Case: O(n log n)
• Space Complexity: O(n) (for auxiliary arrays)

4. Quick Sort

Quick sort is another divide and conquer algorithm that selects a "pivot" element and partitions the array such that all elements smaller than the pivot are on the left, and all larger elements are on the right. It then recursively sorts the partitions.

Steps:

1. Choose a pivot element.
2. Partition the array such that elements smaller than the pivot go to the left, and larger ones go to the right.
3. Recursively sort the left and right partitions.

Code in C++:

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; 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);
    }
}

Time Complexity:

• Best and Average Case: O(n log n)
• Worst Case: O(n²) (when pivot is the smallest or largest element)
• Space Complexity: O(log n) (for recursion)

5. Bubble Sort

Bubble sort repeatedly swaps adjacent elements if they are in the wrong order, "bubbling" the largest elements to the end of the array.

Steps:

1. Compare adjacent elements.
2. Swap them if they are in the wrong order.
3. Repeat until the array is sorted.

Code 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(arr[j], arr[j+1]);
            }
        }
    }
}

Time Complexity:

• Best Case: O(n) (already sorted array)
• Worst and Average Case: O(n²)
• Space Complexity: O(1)

6. Heap Sort

Heap sort uses a binary heap data structure to sort an array. It builds a max heap (where the largest element is the root), extracts the root, and repeats the process.

Steps:

1. Build a max heap from the array.
2. Extract the maximum element (root), and swap it with the last element.
3. Heapify the remaining array and repeat.

Code in C++:

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

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--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Time Complexity:

• Best, Worst, and Average Case: O(n log n)
• Space Complexity: O(1)

7. Shell Sort

Shell sort is an optimization of insertion sort that allows the exchange of far-apart elements. It starts by comparing elements far apart and gradually reduces the gap between elements to be compared.

Steps:

1. Initialize a gap value.
2. Compare and swap elements that are gap distance apart.
3. Reduce the gap and repeat until gap = 1.

Code in C++:

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

Time Complexity:

• Best Case: O(n log n)
• Worst Case: O(n²)
• Space Complexity: O(1)

8. Radix Sort

Radix sort is a non-comparative sorting algorithm that processes the digits of numbers in a specific order (usually least significant digit first) and uses another stable sorting algorithm (like counting sort) as a subroutine.

Steps:

1. Sort the elements based on the least significant digit.
2. Move

to the next significant digit and repeat.

Code in C++:

int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

void countSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int m = getMax(arr, n);
    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

Time Complexity:

• Best, Worst, and Average Case: O(d * (n + k)), where d is the number of digits and k is the range of digits.
• Space Complexity: O(n + k)

9. Bucket Sort

Bucket sort works by distributing elements into different buckets (usually based on ranges) and then sorting the individual buckets using another sorting algorithm.

Steps:

1. Distribute elements into buckets.
2. Sort each bucket.
3. Concatenate the sorted buckets.

Code in C++:

void bucketSort(float arr[], int n) {
    vector<float> buckets[n];

    for (int i = 0; i < n; i++) {
        int bucket_idx = n * arr[i];
        buckets[bucket_idx].push_back(arr[i]);
    }

    for (int i = 0; i < n; i++)
        sort(buckets[i].begin(), buckets[i].end());

    int index = 0;
    for (int i = 0; i < n; i++) {
        for (auto num : buckets[i])
            arr[index++] = num;
    }
}

Time Complexity:

• Best and Average Case: O(n + k)
• Worst Case: O(n²)
• Space Complexity: O(n)

Conclusion

Each sorting algorithm has its strengths and weaknesses, with varying levels of efficiency depending on the data's structure and size. Algorithms like quicksort and merge sort are often preferred due to their average-case efficiency, while selection and bubble sorts are mainly useful for educational purposes due to their simplicity. Radix and bucket sorts are more suited for specialized cases involving specific types of input (like integers or uniformly distributed data).