Q7) Write a C++ program using types of Sorting.

Aim: To implement the C++ program using Sorting.

Description:
 A Sorting Algorithm is used to rearrange a given array or list of elements
according to a comparison operator on the elements.
 The comparison operator is used to decide the new order of elements in the
respective data structure.
 This order can be from lowest to highest or highest to lowest.
 Sorting an unsorted array helps to solve many problems such as searching for
the minimum or maximum element, etc.
 There are six types of sorting techniques; they are as follows:

1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Radix Sort
5. Merge Sort
6. Quick Sort
 1. Bubble Sort:

Description:

Bubble sort is one of the most straightforward sorting algorithms. In this sorting technique,
we begin by comparing the first two elements of the array and checking if the first element is
greater than the second element; if it is, we will swap those elements and move forward to the
next element.

If the first element is not greater than the second, then we don’t need to swap it. And this
process will keep on repeating till the end of the array.

Program Code:

#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bubbleSort(int *array, int size) {
for(int i = 0; i<size; i++) {
int swaps = 0; //flag to detect any swap is there or not
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) { //when the current item is bigger than next
swapping(array[j], array[j+1]);
swaps = 1; //set swap flag
}
}
if(!swaps)
break; // No swap in this pass, so array is sorted
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
bubbleSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
Output:
 2. Insertion Sort

Description:

In this sorting technique, the elements are sorted by comparing the elements with their
previous elements. It starts by comparing the second element with the first element. If the
second element is smaller than the first, then we will swap it.

After that, we will compare the third element with all the elements that are before it.
Similarly, it goes for the fourth element and so on. Once all the comparisons are made, the
elements become sorted.

Program Code:

#include<iostream>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void insertionSort(int *array, int size) {
int key, j;
for(int i = 1; i<size; i++) {
key = array[i];//take value
j = i;
while(j > 0 && array[j-1]>key) {
array[j] = array[j-1];
j--;
}
array[j] = key; //insert in right place
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
insertionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
Output:
 3. Selection Sort

Description:

In selection sorting technique, the smallest element is fetched by comparing itself with the
rest of the elements and sorted at the array's first position. The complete array is divided into
two halves, the sorted subarray on the left and the unsorted subarray on the right. Once the
first element is sorted, the search for the second minimum element begins from the rest of the
array and is positioned at second place.

Similarly, all the elements are positioned on the sorted side of the subarray one after the
other, and the complete array becomes a sorted array.

Program Code:

#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
 temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void selectionSort(int *array, int size) {
int i, j, imin;
for(i = 0; i<size-1; i++) {
imin = i; //get index of minimum data
for(j = i+1; j<size; j++)
if(array[j] < array[imin])
imin = j;
//placing in correct position
swap(array[i], array[imin]);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
selectionSort(arr, n);
cout << "Array after Sorting: ";
 display(arr, n);
}

Output:
 4. Radix Sort
Description:

Radix sort is a sorting algorithm that sorts the elements by first grouping the individual digits
of the same place value. Then, sort the elements according to their increasing/decreasing
order.

Suppose, we have an array of 8 elements. First, we will sort elements based on the value of
the unit place. Then, we will sort elements based on the value of the tenth place. This process
goes on until the last significant place.

Let the initial array be [121, 432, 564, 23, 1, 45, 788]. It is sorted according to radix sort as
shown in the figure below.

Program Code:
#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void radixSort(int *arr, int n, int max) {
int i, j, m, p = 1, index, temp, count = 0;
list<int> pocket[10]; //radix of decimal number is 10
for(i = 0; i< max; i++) {
m = pow(10, i+1);
p = pow(10, i);
for(j = 0; j<n; j++) {
temp = arr[j]%m;
index = temp/p; //find index for pocket array
pocket[index].push_back(arr[j]);
}
count = 0;
for(j = 0; j<10; j++) {
//delete from linked lists and store to array
while(!pocket[j].empty()) {
arr[count] = *(pocket[j].begin());
pocket[j].erase(pocket[j].begin());
count++;
}
}
}
}
int main() {
int n, max;
cout << "Enter the number of elements: ";
cin >> n;
 cout << "Enter the maximum digit of elements: ";
cin >> max;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Data before Sorting: ";
display(arr, n);
radixSort(arr, n, max);
cout << "Data after Sorting: ";
display(arr, n);
}

Output:

5. Merge Sort
Description:

Merge Sort is one of the most popular sorting algorithms that is based on the principle of
Divide and Conquer Algorithm.

Here, a problem is divided into multiple sub-problems. Each sub-problem is solved

Program Code:
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
//size of left and right sub-arrays
nl = m-l+1; nr = r-m;
int larr[nl], rarr[nr];
//fill left and right sub-arrays
for(i = 0; i<nl; i++)
larr[i] = array[l+i];
for(j = 0; j<nr; j++)
rarr[j] = array[m+1+j];
i = 0; j = 0; k = l;
//marge temp arrays to real array
while(i < nl && j<nr) {
 if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
}else{
array[k] = rarr[j];
j++;
}
k++;
}
while(i<nl) { //extra element in left array
array[k] = larr[i];
i++; k++;
}
while(j<nr) { //extra element in right array
array[k] = rarr[j];
j++; k++;
}
}
void mergeSort(int *array, int l, int r) {
int m;
if(l < r) {
int m = l+(r-l)/2;
// Sort first and second arrays
mergeSort(array, l, m);
mergeSort(array, m+1, r);
merge(array, l, m, r);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
 cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
mergeSort(arr, 0, n-1); //(n-1) for last index
cout << "Array after Sorting: ";
display(arr, n);
}

Output:

6. Quick Sort
Description:

The quicksort algorithm is the most widely used algorithm and the most efficient sorting
algorithm. It works on the divide and conquer approach, i.e., the array is divided into
subarrays, and when these subarrays are sorted, they are combined to form a complete sorted
array.

In this approach, a pivot element is selected, and the array is partitioned into two halves based
on the pivot element. The elements that are smaller than the pivot element are shifted to the
left side of it, and the elements greater than the pivot element are moved to the right side.

Program Code:
#include<iostream>
using namespace std;
int partition(int arr[], int start, int end)
{
int pivot = arr[start];
int count = 0;
for (int i = start + 1; i <= end; i++) {
if (arr[i] <= pivot)
count++;
}
// Giving pivot element its correct position
 int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]);
// Sorting left and right parts of the pivot element
int i = start, j = end;
while (i < pivotIndex && j > pivotIndex) {
while (arr[i] <= pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i < pivotIndex && j > pivotIndex) {
swap(arr[i++], arr[j--]);
}
}
return pivotIndex;
}
void quickSort(int arr[], int start, int end)
{
// base case
if (start >= end)
return;
// partitioning the array
int p = partition(arr, start, end);
// Sorting the left part
quickSort(arr, start, p - 1);
// Sorting the right part
quickSort(arr, p + 1, end);
}
int main()
{
int arr[] = { 9, 3, 4, 2, 1, 8 };
int n = 6;
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}

Output: