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:
Bubble Sort: For $i=0$ to $n-2$, compare adjacent elements $arr[j]$ and $arr[j+1]$. Swap if $arr[j] > arr[j+1]$.
Selection Sort: For each position $i$, find the minimum element in the remaining unsorted array and swap it with the element at $i$.
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.
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