Understanding All Sorting Algorithms with Pseudocodes and Code Examples

 Let's go through the code explanations for each sorting algorithm along with their pseudocode.

---

1. Bubble Sort

Explanation

• Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.
• Each pass of the list ensures that the largest unsorted element "bubbles" to its correct position.

C++ Code

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

Pseudocode for Bubble Sort

function bubbleSort(arr, n):
    for i from 0 to n-2:
        for j from 0 to n-i-2:
            if arr[j] > arr[j+1]:
                swap(arr[j], arr[j+1])

---

2. Selection Sort

Explanation

• Selection Sort selects the smallest element from the unsorted portion of the array and places it at the beginning. This process is repeated for the remaining unsorted elements.
• The algorithm works by finding the smallest element and swapping it with the first unsorted element.

C++ Code

void selectionSort(int arr[], int n) {
    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]);
    }
}

Pseudocode for Selection Sort

function selectionSort(arr, n):
    for i from 0 to n-2:
        minIndex = i
        for j from i+1 to n-1:
            if arr[j] < arr[minIndex]:
                minIndex = j
        swap(arr[i], arr[minIndex])

---

3. Insertion Sort

Explanation

• Insertion Sort builds the sorted array one element at a time.
• It takes the next unsorted element and places it in the correct position within the sorted part.

C++ Code

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

Pseudocode for Insertion Sort

function insertionSort(arr, n):
    for i from 1 to n-1:
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = key

---

4. Merge Sort

Explanation

• Merge Sort divides the array into halves recursively until each half contains one element, then merges these halves back together in a sorted manner.
• This is a divide-and-conquer algorithm that uses a combination of sorting and merging steps.

C++ Code

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];

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

    int i = 0, j = 0, k = l;
    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++];
}

Pseudocode for Merge Sort

function merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = arr[l...m]
    R = arr[m+1...r]
    
    i = 0, j = 0, k = l
    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++]

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

---

These explanations should provide a better understanding of each sorting algorithm and their respective pseudocodes.

Let's break down the Time Complexity and Space Complexity for the sorting algorithms discussed earlier.

---

1. Bubble Sort

• Time Complexity:

  • Best case: O(n) (already sorted array)
  • Worst case: O(n²) (completely unsorted array)
  • Average case: O(n²)

• Space Complexity:

  • O(1) (in-place sorting, requires minimal extra space)

---

2. Selection Sort

• Time Complexity:

  • Best case: O(n²)
  • Worst case: O(n²)
  • Average case: O(n²)

• Space Complexity:

  • O(1) (in-place sorting)

---

3. Insertion Sort

• Time Complexity:

  • Best case: O(n) (already sorted array)
  • Worst case: O(n²) (completely unsorted array)
  • Average case: O(n²)

• Space Complexity:

  • O(1) (in-place sorting)

---

4. Merge Sort

• Time Complexity:

  • Best case: O(n log n) (balanced recursive splitting and merging)
  • Worst case: O(n log n)
  • Average case: O(n log n)

• Space Complexity:

  • O(n) (extra space used for the temporary merge arrays)

---

Summary of Complexity

Algorithm	Time Complexity	Space Complexity
Bubble Sort	O(n²)	O(1)
Selection Sort	O(n²)	O(1)
Insertion Sort	O(n²)	O(1)
Merge Sort	O(n log n)	O(n)

These complexities give insights into how efficient each sorting algorithm is based on input size.