I am supposed to implement (bubble sort) and use the function (time) to calculat
ID: 3639526 • Letter: I
Question
I am supposed to implement (bubble sort) and use the function (time) to calculate the (running time) for the algorithms before and after sorting in both best case (sorted list) and worst case( sorted reversely) . The problem I am getting is that it gives me the same exact time before and after sorting!!! can someone help please, thanks..
here is my code:
#include<iostream>
#include<windows.h>
using namespace std;
int time_s()
{
SYSTEMTIME st;
GetSystemTime(&st);
int time1 = (st.wHour*60*60*1000) + (st.wMinute*60*1000) +
(st.wSecond*1000) + (st.wMilliseconds);
return time1;
}
void bubble_sort(int arr[], int n) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < n - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
int main()
{
int A[10000];
int start, end;
long dif;
cout<<"Bubble sort in Best Case already sorted list” ";
for ( int j = 0; j < 10000; j++ )
start = time_s();
bubble_sort(A,10000);
end = time_s();
dif = end - start;
cout<<"The time in milliseconds it takes before sorting: "<<start<<endl;
cout<<"The time in milliseconds it takes after sorting: "<<end<<endl;
cout<<"The difference in time in milliseconds : "<<dif<<endl;
cout<<" Bubble sort in worst case sorted in reverse order” ";
for ( int j = 10000; j >0; j-- )
start = time_s();
bubble_sort(A,10000);
end = time_s();
dif = end - start;
cout<<"The time in milliseconds it takes before sorting: "<<start<<endl;
cout<<"The time in milliseconds it takes after sorting: "<<end<<endl;
cout<<"The difference in time in milliseconds : "<<dif<<endl;
cout << endl;
return 0;
}
Explanation / Answer
please rate - thanks
getting time in ticks, and converting to milliseconds
initializing array with random numbers
#include<iostream>
#include <ctime>
using namespace std;
void bubble_sort(int arr[], int n) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < n - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
void reverse_sort(int arr[], int n) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < n - j; i++) {
if (arr[i] < arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
int main()
{
int A[10000];
clock_t start, end;
long dif;
cout<<"Bubble sort in Best Case already sorted list ";
for ( int j = 0; j < 10000; j++ )
A[j]=rand();
bubble_sort(A,10000);
start = clock();
bubble_sort(A,10000);
end = clock();
dif = end - start;
cout<<"The time in milliseconds it takes before sorting: "<<(start)/(CLOCKS_PER_SEC/1000.)<<endl;
cout<<"The time in milliseconds it takes after sorting: "<<(end)/(CLOCKS_PER_SEC/1000.)<<endl;
cout<<"The difference in time in milliseconds : "<<(dif)/(CLOCKS_PER_SEC/1000.)<<endl;
cout<<" Bubble sort in worst case sorted in reverse order ";
reverse_sort(A,10000);
start = clock();
bubble_sort(A,10000);
end = clock();
dif = end - start;
cout<<"The time in milliseconds it takes before sorting: "<<(start)/(CLOCKS_PER_SEC/1000.)<<endl;
cout<<"The time in milliseconds it takes after sorting: "<<(end)/(CLOCKS_PER_SEC/1000.)<<endl;
cout<<"The difference in time in milliseconds : "<<(dif)/(CLOCKS_PER_SEC/1000.)<<endl;
cout << endl;
system("pause");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.