Sorting Program Note: Make sure you use c++ programming otherwise i will not gra
ID: 2247597 • Letter: S
Question
Sorting Program Note: Make sure you use c++ programming otherwise i will not grade your work
For this assignment, you are to write a comparative algorithm that will
compare the efficiency of three sorting routines. Here is the approach
you should use:
1. Write a Bubble Sort function with a test program.
2. Write a Shell Sort function with a test program.
3. Write a Quick Sort function (using stacks, rather
than recursion) with a test program.
4. Write the main program (that will include the other 3 programs).
Notes:
In the test programs, the logic should be as follows:
Print the random numbers
Sort the numbers keeping track of the costs
Print the sorted numbers
Print the cost
Use __INCLUDE_LEVEL__ in all of the programs, which includes the sorting
routines and a test program. ( Sample program using include level)
The main program should have the following logic.
Generate 20 random numbers.
Print the random numbers.
Move the original random numbers into another array.
Bubble Sort the other array.
Print the sorted numbers AND the cost of sorting the numbers.
Move the original random numbers into another array.
Shell Sort the other array.
Print the sorted numbers AND the cost of sorting the numbers.
Move the original random numbers into another array.
Quick Sort the other array.
Print the sorted numbers AND the cost of sorting the numbers.
To compute the cost, you assign values to every swap and every
compare. A compare costs 1 unit, and a swap costs 6 units.
Explanation / Answer
#include <bits/stdc++.h>
using namespace std;
void BubbleSort(int temp[],int n){
//Create a temporary array
int arr[n];
for(int cnt=0;cnt < n;cnt++){
arr[cnt] = temp[cnt];
}
int i, j,cost=0;
for (i = 0; i < n-1; i++){
for (j = 0; j < n-i-1; j++){
if (arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
cost++;
cost += 6;
}else{
cost++;
}
}
}
cout << "Elements sorted after bubble sort:"<<endl;
for(int cnt=0;cnt < 20;cnt++){
cout << arr[cnt] << " ";
}
cout << endl;
cout << "Cost is " << cost << endl;
return;
}
void ShellSort(int temp[], int n)
{
//Create array copy
int arr[n];
for(int cnt=0;cnt < n;cnt++){
arr[cnt] = temp[cnt];
}
int cost=0;
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2)
{
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is
// gap sorted
for (int i = gap; i < n; i += 1)
{
// add a[i] to the elements that have been gap sorted
// save a[i] in temp and make a hole at position i
int temp = arr[i];
cost += 2;
// shift earlier gap-sorted elements up until the correct
// location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap){
arr[j] = arr[j - gap];
cost += 2;
}
// put temp (the original a[i]) in its correct location
arr[j] = temp;
cost += 2;
}
}
cout << "Elements sorted after shell sort:"<<endl;
for(int cnt=0;cnt < 20;cnt++){
cout << arr[cnt] << " ";
}
cout << endl;
cout << "Cost is " << cost << endl;
}
/* This function takes last element as pivot and
places all elements smaller than pivot
to left of pivot and others to right
of pivot */
pair<int,int> partition (int arr[], int low, int high)
{
int cost=0;
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
cost++;
i++; // increment index of smaller element
swap(arr[i], arr[j]);
cost += 6;
}
}
swap(arr[i + 1], arr[high]);
cost += 6;
pair<int,int> p;
//Partition index
p.first = i+1;
//Cost for partition
p.second = cost;
//Return both partition index and cost
return p;
}
void QuickSort(int arr[],int low,int high){
stack<int> s;
s.push(low);
s.push(high);
int cost=0;
while( !s.empty() ){
//Sort from low to high
high = s.top();
s.pop();
low = s.top();
s.pop();
if (low < high)
{
cost++;
/* pi is partitioning index*/
pair<int,int> p;
p = partition(arr, low, high);
int pi = p.first;
cost += p.second;
//Sort from low to pi-1 and then pi+1 to high
//Since stack follows LIFO pi+1 and high inserted first
//followed by low and pi-1
s.push(pi+1);
s.push(high);
s.push(low);
s.push(pi-1);
}
}
cout << "Elements sorted after quick sort:"<<endl;
for(int cnt=0;cnt < 20;cnt++){
cout << arr[cnt] << " ";
}
cout << endl;
cout << "Cost is " << cost << endl;
return;
}
int main(){
int arr[20];
for(int cnt=0;cnt < 20;cnt++){
//Generate random numbers and store them in an array
arr[cnt] = rand();
cout << arr[cnt] << endl;
}
BubbleSort(arr,20);
ShellSort(arr,20);
QuickSort(arr,0,19);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.