Programming Paradigms

Assignment 1: Sorting Techniques

Name: Kanwaldeep Singh Saluja

Enrollment Number: 2023CSB088

1. Develop subroutines for various shoring techniques as mentioned
below.

a) Insertion sort –

i. Default algorithm and

ii. Avoiding swap

b) Bubble sort –

i. Default algorithm

ii. Avoiding swap

iii. Flagged bubble sort

iv. Range limiting bubble sort

c) Merge sort – Default algorithm

d) Quicksort – Default algorithm. Here use “median of three” pivot

selection

algorithm.

Now consider the following three lists each of having 20 elements:

List-1: 1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95

List-2: 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99

List-3: 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92

Write the main () function to order these lists using the above-
stated subroutines.

Also, programmatically take notes on the number of exchanges (or

exchange
like segment) for each sorting technique and try to understand the
result for

various sorting techniques.

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

void printArray(int *arr, int size)

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

cout << arr[i] << ",";

cout << endl;

void printCommand()

cout << "Enter the sorting algorithm: " << endl

<< "Press 1 for Insertion Sort" << endl

<< "Press 2 for Insertion Sort avoiding swap" << endl

<< "Press 3 for Bubble Sort" << endl

<< "Press 4 for Bubble Sort avoiding swap" << endl

<< "Press 5 for Flagged Bubble Sort" << endl

<< "Press 6 for Range limiting Bubble Sort" << endl

 << "Press 7 for Merge Sort" << endl

<< "Press 8 for Sorting Algorithm" << endl;

// Insertion Sort

void insertionSort(int *arr, int count)

int comparisonCount = 0;

int swapCount = 0;

for (int i = 1; i <= count - 1; i++)

int key = arr[i];

int j = i - 1;

while (j >= 0)

comparisonCount++;

if (arr[j] > key)

arr[j + 1] = arr[j];

j--;

swapCount++;

else

{
 break;

arr[j + 1] = key;

cout << "Total comparisons: " << comparisonCount << endl;

cout << "Total swaps: " << swapCount << endl;

// Insertion avoiding swap

void insertionWithouSwap(int *arr, int n)

int comparisonCount = 0;

int swapCount = 0;

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

int temp = arr[i];

bool swapped = false;

for (int j = i; j > 0; j--)

comparisonCount++;

if (arr[j - 1] > temp)

{
 arr[j] = arr[j - 1];

swapCount++;

else

arr[j] = temp;

swapped = true;

break;

if (!swapped && arr[0] > temp)

arr[0] = temp;

swapCount++;

cout << "Total comparisons: " << comparisonCount << endl;

cout << "Total swaps: " << swapCount << endl;

// Bubble Sort

void bubblesort(int *a, int n)

int comparisonCount = 0;

int swapCount = 0;

int bubbleIteration = 0;
 int temp;

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

bubbleIteration++;

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

comparisonCount++;

if (a[j] > a[j + 1])

temp = a[j];

a[j] = a[j + 1];

a[j + 1] = temp;

swapCount++;

cout << "Total comparisons: " << comparisonCount << endl;

cout << "Total swaps: " << swapCount << endl;

// Bubble Sort avoiding swap

void bubbleSortAvoidingSwap(int *arr, int n)

int comparisonCount = 0;

int swapCount = 0;
 int iteration = 0;

for (int i = n - 1; i > 0; i--)

iteration++;

int max = arr[0];

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

comparisonCount++;

if (arr[j] < max)

arr[j - 1] = arr[j];

swapCount++;

else

arr[j - 1] = max;

max = arr[j];

swapCount++;

arr[i] = max;

cout << "Total comparisons: " << comparisonCount << endl;

cout << "Total swaps: " << swapCount << endl;

}
// Flagged Bubble Sort

void flaggedBubbleSort(int *arr, int n)

int comparisonCount = 0;

int swapCount = 0;

int iterationCount = 0;

for (int i = n - 1; i > 0; i--)

iterationCount++;

int max = arr[0];

bool sorted = true;

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

comparisonCount++;

if (arr[j] < max)

arr[j - 1] = arr[j];

sorted = false;

swapCount++;

else

arr[j - 1] = max;
 max = arr[j];

swapCount++;

arr[i] = max;

if (sorted)

break;

cout << "Total comparisons: " << comparisonCount << endl;

cout << "Total swaps: " << swapCount << endl;

// Range limiting Bubble Sort

void rangeLimitingBubbleSort(int *arr, int n)

int comparisonCount = 0;

int swapCount = 0;

for (int i = n - 1; i > 0;)

int lastSwap = 0;

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

{
 comparisonCount++;

if (arr[j] > arr[j + 1])

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

swapCount++;

lastSwap = j;

i = lastSwap;

cout << "Total comparisons: " << comparisonCount << endl;

cout << "Total swaps: " << swapCount << endl;

// Merge Sort

int mergeCompareCount = 0;

int mergeSwapCount = 0;

void merge(int A[], int mid, int low, int high)

int B[2000];

int i, j, k;

i = low;
j = mid + 1;

k = low;

while (i <= mid && j <= high)

mergeCompareCount++;

if (A[i] < A[j])

B[k] = A[i];

i++;

else

B[k] = A[j];

j++;

k++;

while (i <= mid)

B[k] = A[i];

k++;

i++;

while (j <= high)

 {

B[k] = A[j];

k++;

j++;

for (i = low; i <= high; i++)

A[i] = B[i];

void mergeSort(int A[], int low, int high)

if (low < high)

int mid = (low + high) / 2;

mergeSort(A, low, mid);

mergeSort(A, mid + 1, high);

merge(A, mid, low, high);

// Quick Sort

int quickComparisonCount = 0;

int quickSwapCount = 0;
int medianOfThree(int *array, int low, int high)

int mid = low + (high - low) / 2;

quickComparisonCount++;

if (array[low] > array[mid])

int temp = array[low];

array[low] = array[mid];

array[mid] = temp;

quickSwapCount++;

quickComparisonCount++;

if (array[low] > array[high])

int temp = array[low];

array[low] = array[high];

array[high] = temp;

quickSwapCount++;

quickComparisonCount++;

if (array[mid] > array[high])

int temp = array[mid];

array[mid] = array[high];

array[high] = temp;

quickSwapCount++;
 }

return array[mid];

int partition(int *array, int low, int high)

int pivot = medianOfThree(array, low, high);

int i = low - 1;

int j = high + 1;

while (true)

do

i++;

quickComparisonCount++;

} while (array[i] < pivot);

do

j--;

quickComparisonCount++;

} while (array[j] > pivot);

if (i >= j)

return j;
 int temp = array[i];

array[i] = array[j];

array[j] = temp;

quickSwapCount++;

void quickSort(int *array, int low, int high)

if (low < high)

int partitionIndex = partition(array, low, high);

quickSort(array, low, partitionIndex);

quickSort(array, partitionIndex + 1, high);

int main()

clock_t start = clock();

int list1[] = {1, 16, 12, 26, 25, 35, 33, 58, 45, 42, 56, 67, 83, 75, 74, 86,
81, 88, 99, 95};

int list2[] = {1, 17, 21, 42, 24, 27, 32, 35, 45, 47, 57, 23, 66, 69, 70, 76,
87, 85, 95, 99};

int list3[] = {22, 20, 81, 38, 95, 84, 99, 12, 79, 44, 26, 87, 96, 10, 48, 80,
1, 31, 16, 92};

int n = 20;
int listNo;

int algo;

cout << "Enter the list you want to sort: " << endl

<< "Press 1 for list 1" << endl

<< "Press 2 for list 2" << endl

<< "Press 3 for list 3" << endl;

cin >> listNo;

switch (listNo)

case 1:

printCommand();

cin >> algo;

switch (algo)

case 1:

insertionSort(list1, n);

printArray(list1, n);

break;

case 2:

insertionWithouSwap(list1, n);

printArray(list1, n);

break;

case 3:

bubblesort(list1, n);

printArray(list1, n);
 break;

case 4:

bubbleSortAvoidingSwap(list1, n);

printArray(list1, n);

break;

case 5:

flaggedBubbleSort(list1, n);

printArray(list1, n);

break;

case 6:

rangeLimitingBubbleSort(list1, n);

printArray(list1, n);

break;

case 7:

mergeSort(list1, 0, n - 1);

printArray(list1, n);

cout << "Merge Comparison:" << mergeCompareCount << endl;

cout << "Merge Swap:" << mergeSwapCount << endl;

break;

case 8:

quickSort(list1, 0, n - 1);

printArray(list1, n);

cout << "Quick Sort Comparison:" << quickComparisonCount <<

endl;

cout << "Quick Sort Swap:" << quickSwapCount << endl;

break;
 default:

break;

break;

case 2:

printCommand();

cin >> algo;

switch (algo)

case 1:

insertionSort(list2, n);

printArray(list2, n);

break;

case 2:

insertionWithouSwap(list2, n);

printArray(list2, n);

break;

case 3:

bubblesort(list2, n);

printArray(list2, n);

break;

case 4:

bubbleSortAvoidingSwap(list2, n);

printArray(list2, n);

break;

case 5:

flaggedBubbleSort(list2, n);
 printArray(list2, n);

break;

case 6:

rangeLimitingBubbleSort(list2, n);

printArray(list2, n);

break;

case 7:

mergeSort(list2, 0, n - 1);

printArray(list2, n);

break;

case 8:

quickSort(list2, 0, n - 1);

printArray(list2, n);

break;

default:

break;

break;

case 3:

printCommand();

cin >> algo;

switch (algo)

case 1:

insertionSort(list3, n);

printArray(list3, n);
 break;

case 2:

insertionWithouSwap(list3, n);

printArray(list3, n);

break;

case 3:

bubblesort(list3, n);

printArray(list3, n);

break;

case 4:

bubbleSortAvoidingSwap(list3, n);

printArray(list3, n);

break;

case 5:

flaggedBubbleSort(list3, n);

printArray(list3, n);

break;

case 6:

rangeLimitingBubbleSort(list3, n);

printArray(list3, n);

break;

case 7:

mergeSort(list3, 0, n - 1);

printArray(list3, n);

break;

case 8:

quickSort(list3, 0, n - 1);
 printArray(list3, n);

break;

default:

break;

default:

break;

clock_t end = clock();

double time_taken = static_cast<double>(end - start) / CLOCKS_PER_SEC;

cout << "\nThe program took " << time_taken << " seconds to execute."
<< endl;

return 0;

Analysis:
1. Insertion Sort

 Time Complexity: O(n^2) in the worst case, O(n) in the best case.

 Number of Comparisons: In the worst case, this will be O(n^2). The

number of comparisons increases as the array becomes more
unsorted.
  Number of Swaps: The worst-case swap count is also O(n^2) when
elements need to be moved multiple times.

 Efficiency: Insertion Sort is efficient for small or nearly sorted arrays.

It performs well when the array is already partially sorted because it
has a best-case time complexity of O(n).

2. Insertion Sort (Avoiding Swap)

 Time Complexity: Just like the default insertion sort, O(n^2) in the
worst case and O(n) in the best case.

 Number of Comparisons: Just like the default insertion sort, the

worst-case comparisons will be O(n^2).

 Number of Swaps: This version of insertion sort reduces the swap

count, it does shifting of elements instead of swapping.

 Efficiency: Slightly more efficient in terms of swaps, but still O(n^2) in

the worst case for both comparisons and time complexity.

3. Bubble Sort

 Time Complexity: O(n^2)in the worst case time complexity of this

algorithm.

 Number of Comparisons: In the worst case, bubble sort performs

O(n^2)comparisons.

 Number of Swaps: In the worst case, bubble sort performs O(n^2)

swaps.

 Efficiency: Bubble Sort is not efficient for large data of elements due
to its O(n^2)complexity.

 4. Bubble Sort (Avoiding Swap)

 Time Complexity: Similar to Bubble Sort, O(n^2) in the worst case.

 Number of Comparisons: Similar to Bubble Sort, the number of

comparisons will be O(n^2) in the worst case.

 Number of Swaps: This version avoids swaps by shifting elements,

decreases the number of swap operations.

 Efficiency: It is better than the default Bubble Sort when it comes to

swap operations but still not efficient with comparisons due to O(n^2)
comparisons.
5. Flagged Bubble Sort

 Time Complexity: O(n^2) in the worst case, but if the array becomes
sorted earlier before completion of full iteration than it will terminate.

 Number of Comparisons: In the worst case, it will still perform

O(n^2)comparisons, but in best-case scenarios (when the array is
already sorted), it will perform fewer comparisons.

 Number of Swaps: Similar to Bubble Sort, the worst-case swap count

is O(n^2), but the algorithm might perform fewer swaps in some
cases.

 Efficiency: This algorithm can be more efficient than the regular

Bubble Sort in practice due to the early termination if the array is
sorted early, but it still suffers from O(n^2)complexity in the worst
case.

6. Range Limiting Bubble Sort

 Time Complexity: O(n^2) in the worst case.

 Number of Comparisons: The worst-case comparisons are O(n^2).

 Number of Swaps: Similar to Bubble Sort, the number of swaps will

be O(n^2) in the worst case.

 Efficiency: It improves the performance slightly by reducing the range

of comparisons after each pass (by limiting the range of the inner
loop), but it still has O(n^2) complexity.

7. Merge Sort

 Time Complexity: O(n log n) in both the worst and best cases.

 Number of Comparisons: Merge Sort performs approximately O(n

log n) comparisons, as it divides the array and merges the sorted
halves.

 Number of Swaps: Merge Sort does not perform swaps.

 Efficiency: Merge Sort is much more efficient than the algorithms with
O(n^2) complexity, mostly for large datasets.

 8. Quick Sort

 Time Complexity: O (n log n) on average, but O(n^2) in the worst

case (when the pivot selection is poor).
 Number of Comparisons: Quick Sort performs approximately O (n
log n) comparisons on average, but in the worst case, it can perform
O(n^2) comparisons.

 Number of Swaps: Quick Sort performs O(n log n) swaps on average,

but this can increase to O(n^2) in the worst case.

 Efficiency: Quick Sort is generally more efficient than algorithms with

O(n^2) complexity, especially when a good pivot selection strategy
(like median-of-three) is used, but its worst-case performance is still
O(n^2).

Conclusion:

Insertion and Bubble Sort are not most used algorithms mostly
for large data sets, these are generally used for smaller data sets
of elements.

Quick Sort Algorithm and Merge Sort Algorithm are used for large
data sets of elements. Quick Sort is highly efficient but in worst
case it can be costly. A better pivot selection is needed in Quick
Sort.
2. Create a list of 10K integer elements stored in an array. Then,
perform sorting

on that array using all four techniques (Improved Insertion sort,

Improved

Bubble Sort, Merge Sort and Quick Sort) mentioned above.

Please run at least five times using the same sorting technique and
take an

average of to note the time taken to complete the sorting.

Finally, compare and analyze the time taken for the respective
sorting

techniques.
#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

void printArray(int *arr, int count)

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

cout << arr[i] << ", ";

cout << endl;

// Insertion avoiding swap

void insertionWithouSwap(int *arr, int n)

int comparisonCount = 0;

int swapCount = 0;

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

int temp = arr[i];

bool swapped = false;

 for (int j = i; j > 0; j--)

comparisonCount++;

if (arr[j - 1] > temp)

arr[j] = arr[j - 1];

swapCount++;

else

arr[j] = temp;

swapped = true;

break;

if (!swapped && arr[0] > temp)

arr[0] = temp;

swapCount++;

cout << "Total comparisons: " << comparisonCount << endl;

cout << "Total swaps: " << swapCount << endl;

// Range limiting Bubble Sort

void rangeLimitingBubbleSort(int *arr, int n)

int comparisonCount = 0;

int shiftCount = 0;

for (int i = n - 1; i > 0;)

int lastSwap = 0;

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

comparisonCount++;

if (arr[j] > arr[j + 1])

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

shiftCount++;

lastSwap = j;

i = lastSwap;

cout << "Total comparisons: " << comparisonCount << endl;

cout << "Total shifts: " << shiftCount << endl;

}
// Merge Sort

int mergeCompareCount = 0;

int mergeSwapCount = 0;

void merge(int A[], int mid, int low, int high)

int B[10001];

int i, j, k;

i = low;

j = mid + 1;

k = low;

while (i <= mid && j <= high)

mergeCompareCount++;

if (A[i] < A[j])

B[k] = A[i];

i++;

else

B[k] = A[j];

j++;

k++;
 }

while (i <= mid)

B[k] = A[i];

k++;

i++;

while (j <= high)

B[k] = A[j];

k++;

j++;

for (i = low; i <= high; i++)

A[i] = B[i];

void mergeSort(int A[], int low, int high)

if (low < high)

int mid = (low + high) / 2;

 mergeSort(A, low, mid);

mergeSort(A, mid + 1, high);

merge(A, mid, low, high);

// Quick Sort

int quickComparisonCount = 0;

int quickSwapCount = 0;

int medianOfThree(int *array, int low, int high)

int mid = low + (high - low) / 2;

quickComparisonCount++;

if (array[low] > array[mid])

int temp = array[low];

array[low] = array[mid];

array[mid] = temp;

quickSwapCount++;

quickComparisonCount++;

if (array[low] > array[high])

int temp = array[low];

array[low] = array[high];
 array[high] = temp;

quickSwapCount++;

quickComparisonCount++;

if (array[mid] > array[high])

int temp = array[mid];

array[mid] = array[high];

array[high] = temp;

quickSwapCount++;

return array[mid];

int partition(int *array, int low, int high)

int pivot = medianOfThree(array, low, high);

int i = low - 1;

int j = high + 1;

while (true)

do

i++;

quickComparisonCount++;
 } while (array[i] < pivot);

do

j--;

quickComparisonCount++;

} while (array[j] > pivot);

if (i >= j)

return j;

int temp = array[i];

array[i] = array[j];

array[j] = temp;

quickSwapCount++;

void quickSort(int *array, int low, int high)

if (low < high)

int partitionIndex = partition(array, low, high);

quickSort(array, low, partitionIndex);

quickSort(array, partitionIndex + 1, high);

}
// Random Number Generator

void randomNumberGenerator(int min, int max, int count, int arr[])

srand(time(0));

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

arr[i] = rand() % (max - min + 1) + min;

int main()

clock_t start = clock();

int min = 1;

int max = 10000;

int count;

cout << "Enter the size of the array of random numbers: ";

cin >> count;

int arr[count];

randomNumberGenerator(min, max, count, arr);

cout << "Random numbers: " << endl;

printArray(arr, count);
int num;

cout << "Choose the sorting method:" << endl

<< "Press 1 for Insertion Sort" << endl

<< "Press 2 for Bubble Sort" << endl

<< "Press 3 for Merge Sort" << endl

<< "Press 4 for Quick Sort" << endl;

cin >> num;

switch (num)

case 1:

insertionWithouSwap(arr, count);

cout << "Sorting using Insertion Sort: " << endl;

printArray(arr, count);

break;

case 2:

rangeLimitingBubbleSort(arr, count);

cout << "Sorting using Bubble Sort: " << endl;

printArray(arr, count);

break;

case 3:

mergeSort(arr, 0,count-1);

cout << "Sorting using merge Sort: " << endl;

cout << "Number of comparisons: " << mergeCompareCount << endl;

 cout << "Number of swaps: " << mergeSwapCount << endl;

printArray(arr, count);

break;

case 4:

quickSort(arr, 0, count - 1);

cout << "Sorting using Quick Sort: " << endl;

cout << "Number of comparisons: " << quickComparisonCount <<

endl;

cout << "Number of swaps: " << quickSwapCount << endl;

printArray(arr, count);

break;

default:

cout << "Enter a valid number (Between 1-4)" << endl;

break;

clock_t end = clock();

double time_taken = static_cast<double>(end - start) / CLOCKS_PER_SEC;

cout << "\nThe program took " << time_taken << " seconds to execute."
<< endl;

return 0;

}
Analysis:
Insertion Sorting execution time for 10k random integers:
1. 7.644 seconds
2. 6.252 seconds
3. 9.975 seconds
4. 8.499 seconds
5. 6.542 seconds
Average: 7.7824 seconds
Bubble Sort execution time for 10k random integers:
1. 5.709 seconds
2. 6.026 seconds
3. 5.305 seconds
4. 5.257 seconds
5. 5.48 seconds
Average: 5.5554 seconds
Merge Sort execution time for 10k random integers:
1. 5.443 seconds
2. 5.286 seconds
3. 5.349 seconds
4. 5.611 seconds
5. 5.239 seconds
Average: 5.3856 seconds
Quick Sort execution time for 10k random integers:
1. 6.845 seconds
2. 5.22 seconds
3. 6.631 seconds
4. 5.57 seconds
5. 5.132 seconds
Average: 5.8796 seconds

Conclusion: Hence, Merge Sort, Quick Sort and Bubble Sort are
less time taken algorithms, Insertion Sort is not efficient for large
data sets like 10k elements.