Visualizing Efficient Sorting Algorithms

In the previous post, we discussed basic sorting algorithms namely, Bubble Sort, Insertion Sort, and Selection Sort. Next, we will move on to more efficient ones that handle larger datasets effectively.

Let’s visualize three efficient sorting algorithms — Heap Sort, Merge Sort, and Quick Sort — to understand their sorting process.

Efficient Sorting Algorithms

These sorting algorithms handle large datasets efficiently and provide optimal performance in applications like data analysis, search optimization, database indexing etc.

Brief Overview of Efficient Sorting Algorithms

• Heap Sort: Utilizes a binary heap data structure to repeatedly extract the maximum element and build the sorted array from largest to smallest.
• Merge Sort: Employs a divide-and-conquer strategy to recursively split the array into halves, sort them, and merge them back together.
• Quick Sort: Uses a pivot element to partition the array into two parts and recursively sorts each part. The pivot is placed in its correct position after each partitioning.

Why Are Efficient Sorting Algorithms Better?

Efficient sorting algorithms are generally preferred because of their better time complexity compared to basic sorting methods. The traditional algorithms have an average and worst-case time complexity of O(n²), which makes them inefficient for large datasets. In contrast, Heap Sort, Merge Sort, and Quick Sort all achieve an average time complexity of O(n logn), allowing them to handle significantly larger arrays more efficiently.

These algorithms not only optimize the time required to sort data but are also performant. For instance, Merge Sort ensures stability, whereas Quick Sort often performs exceptionally well in practice due to its partitioning mechanism.

Heap Sort

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

Heap Sort works by first building a max heap from the input array and then repeatedly extracting the maximum element from the heap and placing it at the end of the array. Each extraction reduces the size of the heap, while the sorted portion of the array grows from right to left.

The visualization of Heap Sort shows how the maximum element is selected and moved to its correct position at each step, followed by the heap being restructured to maintain its properties.

Explanation

• The algorithm builds a max heap from the input array.
• At each iteration, the maximum element is extracted and swapped with the last element of the heap; and the heap size is reduced by 1.
• The heapify process is applied to restore the max-heap property.
• The visual representation shows how the unsorted portion decreases and the sorted portion grows from right to left with each iteration.

Merge Sort

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> leftArr(n1), rightArr(n2);
     
    for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
    for (int i = 0; i < n2; i++) rightArr[i] = arr[mid + 1 + i];
     
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) arr[k++] = (leftArr[i] <= rightArr[j]) ? leftArr[i++] : rightArr[j++];
     
    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
}
 
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);
    }
}

Merge Sort follows a divide-and-conquer approach. The array is recursively split into smaller subarrays until each subarray contains only one element. These subarrays are then merged back together in sorted order. The visualization of Merge Sort shows how individual elements are merged to create sorted subarrays, which are eventually combined to form the sorted array.

Explanation

• The algorithm recursively divides the array into halves until single-element subarrays are obtained.
• Each pair of subarrays is merged in a sorted manner.
• The visualization shows the merging process, with smaller sorted subarrays combining to form larger sorted segments.
• The recursive nature of the algorithm can be observed from the step-by-step merging and how the sorted portions expand to cover the entire array.

Quick Sort

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // Store the pivot value
    int i = low - 1;

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

    swap(arr[++i], arr[high]); // Place pivot in its correct position

    return i;
}
 
 
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

Quick Sort partitions the array around a pivot element. After each iteration, the pivot element is placed in its correct position, such that all elements to its left are smaller than it and all elements to its right are larger than it. The array is then recursively sorted on either side of the pivot. The visualization of Quick Sort shows how the pivot is chosen and placed, and how the array is divided into smaller partitions around the pivot.

Explanation

• A pivot element is selected, and the array is partitioned so that elements smaller than the pivot are on the left and the larger elements are on the right. (In the provided implementation, arr[high] is used as the pivot. However, in practice, the pivot is often chosen randomly or through other strategies, such as the median-of-three method, to reduce the likelihood of worst-case performance.)
• The pivot is then placed in its correct position.
• The process is repeated recursively for the left and right partitions.
• The visualization shows how each partitioning step reduces the problem size, and how the pivot elements gradually sort themselves into their correct positions.

Key Takeaways:

• Heap Sort visualization shows how the max-heap property is maintained and how the sorted portion grows from right to left, as the largest elements are moved into place.
• Merge Sort works by recursively dividing the array and then merging the sorted subarrays. The sorted segments are gradually combined to create the final sorted array.
• Quick Sort works by recursively selecting a pivot and placing the pivot element in its correct position, such that elements less than the pivot are before it, and elements greater than the pivot are after it.

These algorithms are significantly more suitable for large datasets compared to basic sorting methods. While each algorithm has its unique advantages, the selection of the right algorithm depends on the specific use case.

Visualizing these efficient sorting algorithms improves our understanding of their working. It helps appreciate their efficiency and optimizations.