Unraveling the Mysteries of Sorting Algorithms

1. Bubble Sort

Detailed Algorithmic Steps

1. Initialization:

   • Start with the array you want to sort. Let’s denote the array as arr and its size as n.

2. Outer Loop:

   • Run a loop from i = 0 to n-1 (or n-2 if you prefer to avoid one iteration since the last element will naturally be in place). This loop will keep track of how many passes through the array you have completed.

3. Swapping Flag:

   • Initialize a boolean flag swapped to false at the beginning of each outer loop iteration. This flag will help detect if any swapping happened during the inner loop.

4. Inner Loop:

   • Run a nested loop from j = 0 to n-i-2. The reason we stop at n-i-2 is that the last i elements are already sorted in each pass.

   • Inside this inner loop, compare the current element arr[j] with the next element arr[j + 1].

5. Comparison:

   • If arr[j] is greater than arr[j + 1], swap them.

   • Set the swapped flag to true to indicate that a swap has occurred.

6. Check for Early Exit:

   • After the inner loop completes, check the swapped flag:

     • If swapped is still false, it means the array is already sorted, and you can exit the outer loop early to save unnecessary passes.

7. Completion:

   • Once all outer loop iterations are complete, the array is sorted.

8. Return or Print:

   • Return the sorted array or print it.

Complexity:

• Time Complexity:

  • Worst-case: O(n2)O(n^2)O(n2) (when the array is in reverse order)

  • Best-case: O(n)O(n)O(n) (when the array is already sorted)

• Space Complexity: O(1)O(1)O(1) (in-place sorting)

C/C++ Implementation

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // Flag to track if a swap occurred
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]); // Swap if elements are in the wrong order
                swapped = true; // Set the flag
            }
        }
        // If no elements were swapped, the array is sorted
        if (!swapped) {
            break;
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java Implementation

public class BubbleSort {
    void bubbleSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false; // Flag to track if a swap occurred
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true; // Set the flag
                }
            }
            // If no elements were swapped, the array is sorted
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        BubbleSort ob = new BubbleSort();
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        ob.bubbleSort(arr);

        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Python Implementation

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False  # Flag to track if a swap occurred
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Swap if elements are in the wrong order
                swapped = True  # Set the flag
        # If no elements were swapped, the array is sorted
        if not swapped:
            break

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

2.Selection Sort

Overview

Selection Sort is a simple sorting algorithm that divides the input list into two parts: a sorted part and an unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the end of the sorted part.

Algorithm Steps

1. Start with the first element as the minimum.

2. Iterate through the unsorted part of the array to find the smallest element.

3. Swap the smallest element with the first unsorted element.

4. Move the boundary between the sorted and unsorted parts.

5. Repeat steps 1-4 until the entire array is sorted.

Time Complexity

• Best Case: O(n²)

• Average Case: O(n²)

• Worst Case: O(n²)

• Space Complexity: O(1) (in-place sort)

C/C++ Implementation

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // Assume the first element is the minimum
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // Update minimum index
            }
        }
        swap(arr[i], arr[minIndex]); // Swap the found minimum with the first element
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java Implementation

javaCopy codepublic class SelectionSort {
    void selectionSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // Assume the first element is the minimum
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // Update minimum index
                }
            }
            // Swap the found minimum with the first element
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        SelectionSort ob = new SelectionSort();
        int arr[] = {64, 25, 12, 22, 11};
        ob.selectionSort(arr);

        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Python Implementation

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i  # Assume the first element is the minimum
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j  # Update minimum index
        arr[i], arr[min_index] = arr[min_index], arr[i]  # Swap

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

---

2. Insertion Sort

Overview

Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It is much less efficient on large lists than more advanced algorithms but is quite efficient for small data sets.

Algorithm Steps

1. Start from the second element (the first element is considered sorted).

2. Compare the current element with the elements in the sorted part of the array.

3. Shift all elements larger than the current element to the right.

4. Insert the current element in its correct position.

5. Repeat for all elements until the array is sorted.

Time Complexity

• Best Case: O(n) (when the array is already sorted)

• Average Case: O(n²)

• Worst Case: O(n²)

• Space Complexity: O(1) (in-place sort)

C/C++ Implementation

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // Shift elements greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // Insert the current element at the right position
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java Implementation

public class InsertionSort {
    void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // Shift elements greater than key to the right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key; // Insert the current element at the right position
        }
    }

    public static void main(String[] args) {
        InsertionSort ob = new InsertionSort();
        int arr[] = {64, 25, 12, 22, 11};
        ob.insertionSort(arr);

        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Python Implementation

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # Shift elements greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Insert the current element at the right position

arr = [64, 25, 12, 22, 11]
insertion_sort(arr)
print("Sorted array:", arr)

4. Merge Sort

Detailed Algorithmic Steps

1. Divide:

   • If the array has one or zero elements, it is already sorted. Return it.

   • Otherwise, find the middle index mid of the array:

     • mid = (low + high) / 2 where low is the starting index and high is the ending index of the current array segment.

2. Recursively Sort:

   • Recursively apply the Merge Sort algorithm to the left half of the array (arr[low...mid]).

   • Recursively apply the Merge Sort algorithm to the right half of the array (arr[mid+1...high]).

3. Merge:

   • After sorting both halves, merge the two sorted halves:

     • Create temporary arrays to hold the left (L) and right (R) halves.

     • Initialize three pointers: i for iterating through L, j for R, and k for the main array.

     • Compare elements of L and R:

       • If L[i] <= R[j], place L[i] in arr[k] and increment i and k.

       • Otherwise, place R[j] in arr[k] and increment j and k.

     • After one of the arrays is exhausted, copy the remaining elements of the other array into arr.

4. Completion:

   • Once all elements are merged, the array will be sorted.

Complexity:

• Time Complexity:

  • Worst-case: O(nlog⁡n)O(n \log n)O(nlogn)

  • Best-case: O(nlog⁡n)O(n \log n)O(nlogn)

• Space Complexity: O(n)O(n)O(n) (due to the temporary arrays used for merging)

C/C++ Implementation

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // Size of left sub-array
    int n2 = right - mid; // Size of right sub-array

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temporary arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temporary arrays back into arr[left..right]
    int i = 0; // Initial index of first sub-array
    int j = 0; // Initial index of second sub-array
    int k = left; // Initial index of merged sub-array
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // Avoid overflow
        mergeSort(arr, left, mid); // Sort first half
        mergeSort(arr, mid + 1, right); // Sort second half
        merge(arr, left, mid, right); // Merge the sorted halves
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java Implementation

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

        int L[] = new int[n1];
        int R[] = new int[n2];

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

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

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    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);
        }
    }

    public static void main(String[] args) {
        MergeSort ob = new MergeSort();
        int arr[] = {12, 11, 13, 5, 6, 7};
        ob.mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Python Implementation

def merge(arr, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid

    L = arr[left:left + n1]  # Left sub-array
    R = arr[mid + 1:mid + 1 + n2]  # Right sub-array

    i = 0  # Initial index of first sub-array
    j = 0  # Initial index of second sub-array
    k = left  # Initial index of merged sub-array

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def merge_sort(arr, left, right):
    if left < right:
        mid = left + (right - left) // 2
        merge_sort(arr, left, mid)
        merge_sort(arr, mid + 1, right)
        merge(arr, left, mid, right)

arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

3. Quick Sort

Detailed Algorithmic Steps

1. Choose a Pivot:

   • Select a pivot element from the array. Common strategies include choosing the first element, the last element, or a random element.

2. Partitioning:

   • Rearrange the array so that elements less than the pivot come before it and elements greater than the pivot come after it.

   • Create two pointers:

     • i starts before the first element (i.e., -1), and j iterates through the array.

   • For each element arr[j]:

     • If arr[j] is less than or equal to the pivot, increment i and swap arr[i] with arr[j].

   • After the loop, swap the pivot element with arr[i + 1]. This places the pivot in its correct position.

3. Recursively Apply:

   • Apply the Quick Sort algorithm to the sub-arrays:

     • arr[low...i] for elements less than the pivot.

     • arr[i+2...high] for elements greater than the pivot.

4. Completion:

   • Once the base case (sub-array size <= 1) is reached, the recursion unwinds, and the array is sorted.

Complexity:

• Time Complexity:

  • Worst-case: O(n2)O(n^2)O(n2) (when the pivot is the smallest or largest element repeatedly)

  • Average-case: O(nlog⁡n)O(n \log n)O(nlogn)

• Space Complexity: O(log⁡n)O(\log n)O(logn) (for the recursive call stack)

C/C++ Implementation

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choosing the last element as pivot
    int i = low - 1; // Pointer for the smaller element

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++; // Increment index of smaller element
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1; // Return the partitioning index
}

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

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java Implementation

public class QuickSort {
    int partition(int arr[], int low, int high) {
        int pivot = arr[high]; // Choosing the last element as pivot
        int i = (low - 1); // Pointer for the smaller element

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++; // Increment index of smaller element
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1; // Return the partitioning index
    }

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

    public static void main(String[] args) {
        QuickSort ob = new QuickSort();
        int arr[] = {10, 7, 8, 9, 1, 5};
        ob.quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Python Implementation

def partition(arr, low, high):
    pivot = arr[high]  # Choosing the last element as pivot
    i = low - 1  # Pointer for the smaller element

    for j in range(low, high):
        if arr[j] < pivot:
            i += 1  # Increment index of smaller element
            arr[i], arr[j] = arr[j], arr[i]  # Swap

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Swap pivot
    return i + 1  # Return the partitioning index

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)  # Partitioning index
        quick_sort(arr, low, pi - 1)  # Before pi
        quick_sort(arr, pi + 1, high)  # After pi

arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

6. Heap Sort

Heap Sort is a comparison-based sorting algorithm that utilizes a binary heap data structure. It consists of two main phases:

1. Building a max heap from the input array.

2. Extracting elements from the heap one by one to produce a sorted array.

Key Concepts

• Binary Heap: A complete binary tree where each node is greater than or equal to its children (in a max heap) or less than or equal to its children (in a min heap).

• Heap Property: The value of each node is greater than or equal to the values of its children, ensuring that the maximum element is always at the root.

Algorithm Steps

Step 1: Build a Max Heap

• Input: An unsorted array of n elements.

• Process:

  • Start from the last non-leaf node (at index n/2 - 1) and move towards the root (index 0).

  • For each node, call the heapify function to maintain the max heap property.

Step 2: Sort the Array

• Input: The max heap created from the previous step.

• Process:

  • Swap the root (maximum element) with the last element of the heap.

  • Reduce the size of the heap by one (ignore the last element, which is now sorted).

  • Call heapify on the root of the heap to restore the max heap property.

  • Repeat the process until the heap is empty.

Detailed Algorithm Steps

1. Heapify Function:

   • Define a function heapify(arr, n, i) that adjusts the heap to maintain the max heap property.

   • Parameters:

     • arr[]: The array representing the heap.

     • n: The size of the heap.

     • i: The index of the current node (subtree) being checked.

   • Operations:

     • Set largest as i (current node).

     • Calculate indices for the left (2*i + 1) and right (2*i + 2) children.

     • Compare the value of the current node with its children. If any child is greater than the current node, update largest.

     • If largest is not equal to i, swap the values of arr[i] and arr[largest], and recursively call heapify on the affected subtree.

2. Heap Sort Function:

   • Define a function heapSort(arr[]).

   • Operations:

     • Build a max heap by calling heapify for each non-leaf node (starting from n/2 - 1 down to 0).

     • Extract elements one by one:

       • Swap the root of the heap (maximum element) with the last element of the heap.

       • Call heapify on the root to maintain the max heap property.

       • Decrease the heap size by one.

Example

Let’s consider an example array: [4, 10, 3, 5, 1].

Building the Max Heap

1. Start heapifying from the last non-leaf node (index 1).

   • Compare arr[1] (10) with its children arr[3] (5) and arr[4] (1). No change needed.

2. Move to index 0 (4).

   • Compare arr[0] (4) with its children arr[1] (10) and arr[2] (3).

   • 10 is the largest, so swap arr[0] with arr[1]: [10, 4, 3, 5, 1].

   • Heapify at index 1:

     • Compare arr[1] (4) with its children (no children in this case). No change needed.

Final max heap: [10, 4, 3, 5, 1].

Sorting the Array

1. Swap the root with the last element: [1, 4, 3, 5, 10].

2. Heapify the root:

   • Compare 1 with its children (4 and 3).

   • Swap with 4: [4, 1, 3, 5, 10].

   • Heapify at index 1: No changes needed (only one child).

3. Repeat:

   • Swap [4, 1, 3, 5] with 1: [3, 1, 4, 5, 10].

   • Heapify: Swap 3 and 1: [3, 1, 4].

   • Swap [3, 1] with 1: [1, 3, 4, 5, 10].

   • The final sorted array is [1, 3, 4, 5, 10].

C/C++ Implementation

#include <iostream>
using namespace std;

// Function to maintain the max heap property
void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left child index
    int right = 2 * i + 2; // right child index

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]); // Swap
        heapify(arr, n, largest); // Recursively heapify the affected subtree
    }
}

// Function to perform heap sort
void heapSort(int arr[], int n) {
    // Build a max heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract elements from heap
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]); // Move current root to end
        heapify(arr, i, 0); // Call max heapify on the reduced heap
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java Implementation

public class HeapSort {
    // Function to maintain the max heap property
    void heapify(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // left child index
        int right = 2 * i + 2; // right child index

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // If largest is not root
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest); // Recursively heapify the affected subtree
        }
    }

    // Function to perform heap sort
    void heapSort(int arr[]) {
        int n = arr.length;

        // Build a max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // One by one extract elements from heap
        for (int i = n - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0); // Call max heapify on the reduced heap
        }
    }

    public static void main(String[] args) {
        HeapSort ob = new HeapSort();
        int arr[] = {64, 25, 12, 22, 11};
        ob.heapSort(arr);

        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Python Implementation

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index

    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left

    #

4o mini