Fundamental Sorting Methods (Bubble, Selection, Quick, and Insertion Sort) || eBook - C++ Lab Programs Collection

 Pgm Description: To implement and compare fundamental sorting techniques—Bubble Sort, Selection Sort, Quick Sort, and Insertion Sort—to arrange a list of integers in ascending order.

Pgm Details: Bubble Sort uses repetitive exchange of adjacent elements. Selection Sort finds the smallest element and swaps it into position. Quick Sort utilizes a "divide and conquer" strategy with a pivot element. Insertion Sort builds a sorted list one element at a time by inserting items into their correct positions.

Pgm Logic:

1. Bubble Sort: For $i=0$ to $n-2$, compare adjacent elements $arr[j]$ and $arr[j+1]$. Swap if $arr[j] > arr[j+1]$.

2. Selection Sort: For each position $i$, find the minimum element in the remaining unsorted array and swap it with the element at $i$.

3. Quick Sort: Pick a pivot; partition the array so elements less than pivot are on the left and greater are on the right; recursively sort sub-arrays.

4. Insertion Sort: Iterate through the array; for each element, shift larger elements in the sorted sub-list to the right and insert the current element in its correct place.

Program Code:

// C++ program to implement Bubble, Selection, Quick, and Insertion Sort

#include<iostream>

using namespace std;

void bubble_sort(int list[], int n) {

    for(int i = 0; i < n; i++)

        for(int j = 0; j < n-1; j++)

            if(list[j] > list[j+1]) swap(list[j], list[j+1]);

}

void selection_sort(int list[], int n) {

    for(int i = 0; i < n; i++) {

        int min = i;

        for(int j = i+1; j < n; j++)

            if(list[j] < list[min]) min = j;

        swap(list[i], list[min]);

    }

}

void quicksort(int x[], int Lb, int Ub) {

    if(Lb < Ub) {

        int down = Lb, up = Ub, pivot = Lb;

        while(down < up) {

            while(x[down] <= x[pivot] && down < Ub) down++;

            while(x[up] > x[pivot]) up--;

            if(down < up) swap(x[down], x[up]);

        }

        swap(x[pivot], x[up]);

        quicksort(x, Lb, up - 1);

        quicksort(x, up + 1, Ub);

    }

}

void insertion_sort(int a[], int n) {

    for(int i = 0; i < n; i++) {

        int t = a[i], pos = i;

        while(pos > 0 && a[pos-1] > t) {

            a[pos] = a[pos-1];

            pos--;

        }

        a[pos] = t;

    }

}

int main() {

    int n, choice, list;

    cout << "Enter no of elements: "; cin >> n;

    cout << "Enter " << n << " numbers: ";

    for(int i = 0; i < n; i++) cin >> list[i];

    cout << "Choose Sort: 1.Bubble 2.Selection 3.Quick 4.Insertion: "; cin >> choice;

    if(choice == 1) bubble_sort(list, n);

    else if(choice == 2) selection_sort(list, n);

    else if(choice == 3) quicksort(list, 0, n-1);

    else insertion_sort(list, n);

    cout << "After sorting:\n";

    for(int i = 0; i < n; i++) cout << list[i] << " ";

    return 0;

}

Output:

Enter no of elements: 5

Enter 5 numbers: 25 11 7 33 2

Choose Sort: 1.Bubble 2.Selection 3.Quick 4.Insertion: 3

After sorting:

2 7 11 25 33

RESULT: Thus the program has been executed and the output was verified.

Remarks: These algorithms vary in time complexity; Quick Sort is generally the fastest for large datasets, while Bubble and Selection sorts are inefficient for large $N$.

Program Explanation: The code provides a menu to select the sorting algorithm. Each function implements the specific logic: swapping neighbors (Bubble), finding the minimum (Selection), partitioning around a pivot (Quick), or shifting to insert (Insertion).

eBook ‘C++ Lab Programs Collection’ purchase Link: Google Play Store  || Google Books

...till the next post, bye-bye & take care