Program to Create 6 Sorting Algorithms in C++ Assignment Solution.

Instructions

Objective

Write a C++ assignment program to create 6 sorting algorithms.

Requirements and Specifications

program to create 6 sorting algorithms in C++

program to create 6 sorting algorithms in C++ 1

Source Code

BUBBLE SORT

class bubblesort
{
 /*
 This class implements the Bubble Sort algorithm for an array of integers
 */
 public:
 void sort(int arr[], int n)
 {
 for(int i = 0; i < n-1; i++) // iterate through the array
 {
 for(int j = 0; j < n-i-1; j++) // iterate from the beginning of the array to element n-i
 {
 if(arr[j] > arr[j+1]) // if the 2 consecutive elements are not sorted, then swap them
 swap(&arr[j], &arr[j+1]);
 }
 }
 }
 void swap(int *x, int *y)
 {
 //This function swaps the values in two pointer variables a and b
 int temp = *x;
 *x = *y;
 *y = temp;
 }
};

HEAP SORT

class heapsort
{
 /*
 This class implements the Heap Sort algorithm for an array of integers
 */
 public:
 void swap(int *x, int *y)
 {
 //This function swaps the values in two pointer variables a and b
 int temp = *x;
 *x = *y;
 *y = temp;
 }
 void heapify_array(int arr[], int n, int i)
 {
 int largest = i;
 int l = 2*i+1; // left index
 int r = 2*i+2; // right index
 if(l  arr[largest])
 largest = l;
 if(r < n && arr[r] > arr[largest])
 largest = r;
 if(largest != i)// if alrgest is not equal to the given index i, then swap
 {
 swap(&arr[i], &arr[largest]);
 heapify_array(arr, n, largest);
 }
 }
 void sort(int arr[], int n)
 {
 for(int i = n/2-1; i >= 0; i--)
 heapify_array(arr, n, i);
 for(int i = n-1; i >= 0; i--)
 {
 swap(&arr[0], &arr[i]);
 heapify_array(arr, i, 0);
 }
 }
};

INSERTION SORT

class insertionsort
{
 /*
 This class implements the Insertion Sort algorithm for an array of integers
 */
 public:
 void sort(int arr[], int n)
 {
 int x;
 for(int i = 0; i < n; i++) // iterate through the array
 {
 x = arr[i]; // element at index i
 int j = i-1; // set the value of j to the previous element before i
 while(j>= 0 && arr[j] > x) // if element j is higher than x, then move j to the right
 {
 arr[j+1] = arr[j];
 j = j - 1;
 }
 arr[j+1] = x; // insert x to the right of the last value of j
 }
 }
};

MERGE SORT

class mergesort
{
 /*
 This class implements the merge Sort algorithm for an array of integers
 */
 public:
 void merge(int arr[], int l, int m, int r)
 {
 int size_left = m-l+1;
 int size_right = r-m;
 int left[size_left];
 int right[size_right];
 // get the elements at the left and insert them into 'left'
 for(int i = 0; i < size_left; i++)
 left[i] = arr[l+i];
 // get the elements at the right and insert them into 'right'
 for(int i = 0; i < size_right; i++)
 right[i] = arr[m+i+1];
 int i = 0;
 int j = 0;
 int k = l;
 while(i < size_left && j < size_right)
 {
 if(left[i] <= right[j])
 {
 arr[k] = left[i];
 i += 1;
 }
 else
 {
 arr[k] = right[j];
 j+=1;
 }
 k+=1;
 }
 while(i
{
 arr[k] = left[i];
 i+=1;
 k+=1;
 }
 while(j < size_right)
 {
 arr[k] = right[j];
 j+=1;
 k+=1;
 }
 }
 void sort(int arr[], int l, int r)
 {
 if(l< r)
 {
 int m = l + (r-l)/2; // get the middle index
 sort(arr, l, m); // sort left
 sort(arr, m+1, r); // sort right
 merge(arr, l, m, r); // merge
 }
 }
};

QUICK SORT

class quicksort
{
 /*
 This class implements the Quick Sort algorithm for an array of integers
 */
 public:
 void sort(int arr[], int low, int high)
 {
 // This is the main funtion for the Quick Sort method
 if(low < high)
 {
 int part_i = partition(arr, low, high);
 // Sort elements at the left
 sort(arr, low, part_i-1);
 // Sort elements at the right
 sort(arr, part_i+1, high);
 }
 }
 void swap(int *x, int *y)
 {
 //This function swaps the values in two pointer variables a and b
 int temp = *x;
 *x = *y;
 *y = temp;
 }
 int partition(int arr[], int low, int high)
 {
 // This function takes last element in the arr as a pivot, and swaps it
 // to its correct position. Then, the smaller values (smaller than the pivot) are
 // placed at the left of the pivot, and greater elements are placed at the right
 int pivot = arr[high]; // last element in array
 int i = low -1;
 for(int j = low; j <= high - 1; j++)
 {
 if(arr[j] < pivot) // element is smaller than pivot but at the right of the pivot, so it must me moved to the left
 {
 i+= 1;
 swap(&arr[i], &arr[j]);
 }
 }
 swap(&arr[i+1], &arr[high]);
 return i+1;
 }
};

SELECTION SORT

class selectionsort
{
 /*
 This class implements the Selection Sort algorithm for an array of integers
 */
 public:
 void sort(int arr[], int n)
 {
 int index;
 for(int i = 0; i < n-1; i++) // iterate through array
 {
 index = i; // save the current index into a variable
 for(int j = i+1; j < n; j++) // iterate from element i+1 to the end of the array
 {
 if(arr[j] < arr[index]) // if the element to the right of element i is smaller than the elemnt i, then it must me swaped to the left
 index = j;
 }
 swap(&arr[index], &arr[i]); // swap elements between index and i
 }
 }
 void swap(int *x, int *y)
 {
 //This function swaps the values in two pointer variables a and b
 int temp = *x;
 *x = *y;
 *y = temp;
 }
};

Create a Program to Create 6 Sorting Algorithms in C++ Assignment Solution.

Instructions

Requirements and Specifications