Chapter 16 – Sorting Algorithms

Chapter 16: Sorting Algorithms

Sorting algorithms are fundamental in computer science and are used in nearly every application that involves data. Sorting helps in arranging data in a specific order, usually ascending or descending, making data retrieval and manipulation easier.

In this chapter, we will explore various sorting algorithms, their logic, code implementations, and analyze their efficiency. Let’s get started with one of the simplest sorting algorithms — Bubble Sort.

---

16.1 Bubble Sort

Definition:

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.

How It Works:

1. Compare the first two elements. If the first element is larger, swap them.
2. Move to the next pair of elements and repeat the comparison and swapping process.
3. Continue doing this for the entire list. At the end of the first pass, the largest element will "bubble up" to its correct position at the end of the list.
4. Repeat the process for the rest of the list, ignoring the last sorted elements.
5. Continue until no more swaps are needed.

Time Complexity:

• Worst case: O(n²) — This happens when the list is in reverse order.
• Best case: O(n) — This occurs when the list is already sorted.

Bubble Sort Implementation in C:

#include <stdio.h>

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

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Explanation:

• The bubbleSort() function performs repeated passes through the array, comparing adjacent elements and swapping them if necessary.
• The largest element "bubbles" up to the correct position after each pass.
• The printArray() function is used to print the sorted array after the algorithm finishes.

Pros and Cons of Bubble Sort:

• Pros:

  • Easy to understand and implement.
  • Good for small datasets or nearly sorted data.

• Cons:

  • Not efficient for large datasets due to its O(n²) time complexity.
  • Performs unnecessary comparisons even when the array is already sorted.

---

16.2 Selection Sort

Definition:

Selection Sort is another simple sorting algorithm. It divides the input list into two parts: a sorted part and an unsorted part. Initially, the sorted part is empty, and the unsorted part contains the entire list. The algorithm proceeds by repeatedly selecting the smallest element from the unsorted part and swapping it with the leftmost unsorted element.

How It Works:

1. Start with the first element and assume it’s the minimum.
2. Compare it with every other element in the array.
3. If a smaller element is found, mark that as the new minimum.
4. At the end of the first pass, swap the minimum element with the first element.
5. Move to the next element and repeat the process.
6. Continue until the entire list is sorted.

Time Complexity:

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

Selection Sort Implementation in C++:

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // Swap the found minimum element with the first element
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Explanation:

• The selectionSort() function selects the smallest element from the unsorted portion of the array and swaps it with the leftmost unsorted element.
• The printArray() function prints the sorted array.

Pros and Cons of Selection Sort:

• Pros:

  • Simple and easy to understand.
  • Reduces the number of swaps compared to bubble sort.

• Cons:

  • Like Bubble Sort, it’s inefficient for large datasets.
  • Time complexity remains O(n²) even if the array is partially sorted.

---

16.3 Insertion Sort

Definition:

Insertion Sort works by dividing the array into a sorted and an unsorted section. The sorted section starts with the first element. The algorithm picks elements from the unsorted section and places them into the correct position in the sorted section.

How It Works:

1. Start with the second element as the key.
2. Compare the key with the elements in the sorted section.
3. Shift larger elements one position to the right to make space for the key.
4. Insert the key into its correct position.
5. Repeat this process for each element in the unsorted section.

Time Complexity:

• Worst and Average case: O(n²)
• Best case: O(n) (when the array is already sorted)

Insertion Sort Implementation in C++:

#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 that are greater than key to one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Explanation:

• The insertionSort() function inserts each element into its correct position by shifting larger elements one step to the right.
• The printArray() function displays the sorted array.

Pros and Cons of Insertion Sort:

• Pros:

  • Efficient for small or nearly sorted datasets.
  • In-place and stable sort.

• Cons:

  • Like bubble and selection sort, it is inefficient for large datasets due to its O(n²) time complexity.

---

Conclusion of Part 1: Simple Sorting Algorithms

Bubble Sort, Selection Sort, and Insertion Sort are great for understanding how sorting works, but their O(n²) time complexity makes them unsuitable for large datasets. They are generally used for educational purposes or small, nearly sorted datasets.

---

Next Chapter: Advanced Sorting Algorithms

In the next part of this chapter, we’ll cover Quick Sort, Merge Sort, and Heap Sort — algorithms that are more efficient for large datasets. These algorithms bring the time complexity down to O(n log n) and are used in many real-world applications.

Feel free to visit digilearn.cloud for additional learning resources provided by Emancipation Edutech Private Limited, where this book is available for free!

Let me know when you’re ready to continue with Quick Sort or the next part of the chapter.