Create a 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

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; } };