I have a c++ program to sort an random integer array using bubblesort, quicksort
ID: 3745329 • Letter: I
Question
I have a c++ program to sort an random integer array using bubblesort, quicksort, mergesort, and selection sort. Every sorting algorithm sorts correctly except that only one array is given for all 4 sorting functions, so only the first sorting funciton sorts the array, and sorted array is passed to the remaining 3 arrays. How do i make separate arrays so all 4 sorting functions sort their own different arrays?
Below is my code
#include <sstream>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
const long int MIN= 1;
const long int MAX= 1000000000;
void quicksort(long int *list,long int left,long int right){
long int i = left;
long int j = right;
long int pivot = list[(i + j) / 2];
long int temp;
while (i <= j){
while (list[i] < pivot)
i++;
while (list[j] > pivot)
j--;
if (i <= j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
i++;
j--;
}
}
if (j > left)
quicksort(list, left, j);
if (i < right)
quicksort(list, i, right);
}
void bubblesort(long int list[],long int length){
long int temp;
for(long int i = 0; i < length; i++){
for(long j = 0; j < length-i-1; j++) {
if (list[j] > list[j+1]) {
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
void merge(long int *arr,long int size,long int first,long int middle,long int last){
long int temp[size];
for(int i = first; i<=last; i++) {
temp[i] = arr[i];
}
int i=first, j=middle+1, k= first;
while(i<=middle && j<=last) {
if(temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k]=temp[j];
j++;
}
k++;
}
while(i<=middle) {
arr[k]=temp[i];
k++;
i++;
}
}
void mergesort(long int *arr, long int size,long int first,long int last){
if(first<last) {
int middle = ( first + last )/2;
mergesort(arr,size,first,middle);
mergesort(arr,size,middle+1,last);
merge(arr,size,first,middle,last);
}
}
void selectionsort(long int arr[], int n) {
long int i, j, minIndex, tmp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
}
int main(){
int comp;
double t1, t2;
long int size;
while (size != 0){
cout << "enter array size, 0 to quit "<< endl;
cin >> size;
long int arr[size];
srand((int)time(0)); // initialize the random number generator
for (long int i=0; i<size; i++){
arr[i] = MIN + ((long int)rand() % (MAX - MIN + 302));
}
t1 = clock();
bubblesort(arr,size);
t2 = clock();
cout << "Bubble Sort: " <<((t2 - t1)/ CLOCKS_PER_SEC) *1000 << " msec" << " " << endl;
t1 = clock();
selectionsort(arr,size);
t2 =clock();
cout << "selection Sort: " << (t2 - t1)/ CLOCKS_PER_SEC * 1000<< " msec ";
t1 = clock();
mergesort(arr,size, 0, size);
t2 = clock();
cout << "merge Sort: " << (t2 - t1)/ CLOCKS_PER_SEC * 1000<< " msec ";
t1 = clock();
quicksort(arr,0,size);
t2 = clock();
cout << "quick Sort: " << (t2 - t1)/ CLOCKS_PER_SEC * 1000<< " msec ";
}
return 0;
}
Explanation / Answer
You need to store the values of the old array into a temporary array and then after sorting with one function swap the older values from the temporary array into the old array and perform sorting again.
Reason: Whenever we pass an array into a function, the base address gets passed and hence any changes made in the array is permanent.
#include <sstream>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
const long int MIN= 1;
const long int MAX= 1000000000;
void quicksort(long int *list,long int left,long int right){
long int i = left;
long int j = right;
long int pivot = list[(i + j) / 2];
long int temp;
while (i <= j){
while (list[i] < pivot)
i++;
while (list[j] > pivot)
j--;
if (i <= j){
temp = list[i];
list[i] = list[j];
list[j] = temp;
i++;
j--;
}
}
if (j > left)
quicksort(list, left, j);
if (i < right)
quicksort(list, i, right);
}
void bubblesort(long int list[],long int length){
long int temp;
for(long int i = 0; i < length; i++){
for(long j = 0; j < length-i-1; j++) {
if (list[j] > list[j+1]) {
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
void merge(long int *arr,long int size,long int first,long int middle,long int last){
long int temp[size];
for(int i = first; i<=last; i++) {
temp[i] = arr[i];
}
int i=first, j=middle+1, k= first;
while(i<=middle && j<=last) {
if(temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k]=temp[j];
j++;
}
k++;
}
while(i<=middle) {
arr[k]=temp[i];
k++;
i++;
}
}
void mergesort(long int *arr, long int size,long int first,long int last){
if(first<last) {
int middle = ( first + last )/2;
mergesort(arr,size,first,middle);
mergesort(arr,size,middle+1,last);
merge(arr,size,first,middle,last);
}
}
void selectionsort(long int arr[], int n) {
long int i, j, minIndex, tmp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
}
int main(){
int comp;
double t1, t2;
long int size;
while (size != 0){
cout << "enter array size, 0 to quit "<< endl;
cin >> size;
long int arr[size],temp[size];
srand((int)time(0)); // initialize the random number generator
for (long int i=0; i<size; i++){
arr[i] = MIN + ((long int)rand() % (MAX - MIN + 302));
}
for (long int i=0; i<size; i++){
temp[i]=arr[i];
}
t1 = clock();
bubblesort(arr,size);
t2 = clock();
cout << "Bubble Sort: " <<((t2 - t1)/ CLOCKS_PER_SEC) *1000 << " msec" << " " << endl;
for (long int i=0; i<size; i++){
arr[i]=temp[i];
}
t1 = clock();
selectionsort(arr,size);
t2 =clock();
cout << "selection Sort: " << (t2 - t1)/ CLOCKS_PER_SEC * 1000<< " msec ";
for (long int i=0; i<size; i++){
arr[i]=temp[i];
}
t1 = clock();
mergesort(arr,size, 0, size);
t2 = clock();
cout << "merge Sort: " << (t2 - t1)/ CLOCKS_PER_SEC * 1000<< " msec ";
for (long int i=0; i<size; i++){
arr[i]=temp[i];
}
t1 = clock();
quicksort(arr,0,size);
t2 = clock();
cout << "quick Sort: " << (t2 - t1)/ CLOCKS_PER_SEC * 1000<< " msec ";
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.