I need to know what each line of code is doing. Please explain!! //Bubblesort al
ID: 3705305 • Letter: I
Question
I need to know what each line of code is doing. Please explain!!
//Bubblesort algo function
void bubbleSort(){
//double timediff;
int count;
struct car cars[SIZE];//created array with limited space
struct car cars2[SIZE];
readCars(&cars[0], &count);//reads aray and places the frist item n the first index of array
//clock begin
long start =getMicroTime();
//bubble sort
for(int j=0; j bool swapped = true;
memcpy(&cars2, &cars, sizeof(car)*SIZE);
while(swapped){
swapped = false;
for(int i=0; i int cmp =strcmp(cars2[i].make, cars2[i+1].make);
if(cmp>0){
car temp= cars2[i];
cars2[i]= cars2[i+1];
cars2[i+1]=temp;
swapped=true;
}
}
}
}
//insertion sort algo function
void insertionSort(){
//double timediff;
int count;
struct car cars[SIZE];//created array with limited space
struct car cars2[SIZE];
readCars(&cars[0], &count);//reads aray and places the frist item n the first index of array
//clock begin
long start =getMicroTime();
for(int x=0; x memcpy(&cars2, &cars, sizeof(car)*SIZE);
int i, j;
car key;
for(i=1; i key = cars2[i];
j= i-1;
while(j>=0 && strcmp(cars[j].make, key.make)>0){
cars[j+1]=cars[j];
j-=1;
}
cars[j+1]=key;
}
}
long end =getMicroTime();
long elapsed = end - start;
cout << "" << endl;
cout << "Time taken using insertion sort:" << ((double)elapsed)/LOOPS << "us"<< endl;
cout << "" << endl;
cout << "This list is sorted" << endl;
for(int i=0; i cout <<"Make:"< }
}
//QuickSort function
void quickSort(){
//double timediff;
int count;
struct car cars[SIZE];//created array with limited space
struct car cars2[SIZE];
readCars(&cars[0], &count);//reads aray and places the frist item n the first index of array
//clock begin
long start =getMicroTime();
for(int j=0; j memcpy(&cars2, &cars, sizeof(car)*SIZE);
int low = 0;
int high = count-1;
quickSortRecursive(cars2, low, high);
}
long end =getMicroTime();
long elapsed = end - start;
cout << "" << endl;
cout << "Time taken using quickSort sort:" << ((double)elapsed)/LOOPS << "us"<< endl;
cout << "" << endl;
cout << "This list is sorted" << endl;
for(int i=0; i cout <<"Make:"< }
}
void quickSortRecursive(car cars[], int low,int high){
if(low int pi = partition(cars, low, high);
quickSortRecursive(cars, low, pi-1);
quickSortRecursive(cars, pi+1, high);
}
}
int partition(car cars[], int low, int high){
car pivot = cars[high];
int i=(low-1);
for(int j=low; j<=high-1; j++){
int cmp = strcmp(cars[j].make, pivot.make);
if(cmp<=0){
i++;
car temp= cars[i];
cars[i]= cars[j];
cars[j]=temp;
}
}
car temp= cars[i+1];
cars[i+1]= cars[high];
cars[high]=temp;
return (i+1);
}
Explanation / Answer
This algorithm is for comparing the efficiencies of bubble sort and quick sort algorithm for sorting cars structure based on their make. How ever this algorithm is not that much clear. Please find my comments to each line in the algorithm .
/Bubblesort algo function
void bubbleSort(){
//double timediff;
int count;this is to keep track of how many cars we have read
struct car cars[SIZE];//created array with limited space
struct car cars2[SIZE];//created another struct array of type cars of size SIZE
readCars(&cars[0], &count);//reads aray and places the frist item n the first index of array //this is the function to read details of car into first index of car array
//clock begin
long start =getMicroTime();//this will get the time in micro seconds before the start of bubble sort algorithim
//bubble sort
for(int j=0; j bool swapped = true;//
memcpy(&cars2, &cars, sizeof(car)*SIZE);//copying cars into cars2
while(swapped){//this will continue till swapped is true
swapped = false;
for(int i=0; i int cmp =strcmp(cars2[i].make, cars2[i+1].make);//where we are sorting based on the car make so we are comparing the make of car in index i with i+1//incrementing the i for next iteration to compare next car
if(cmp>0){//here we are sorting in descending order so if ith car is greater than i+1 th car then we are swapping the cars
car temp= cars2[i];
cars2[i]= cars2[i+1];
cars2[i+1]=temp;
swapped=true;//as cars are swapped we are setting swapped to true which means that sorting has to continue. This process will continue till the end of all the cars in the struct are sorted
}
}
}
}
//insertion sort algo function
void insertionSort(){
//double timediff;
int count;
struct car cars[SIZE];//created array with limited space
struct car cars2[SIZE];
readCars(&cars[0], &count);//reads aray and places the frist item n the first index of array
//clock begin
long start =getMicroTime();//getting the time before the start of insertion sort
for(int x=0; x memcpy(&cars2, &cars, sizeof(car)*SIZE);//this loop will continue till the end of iterating the whole cars structure
int i, j;
car key;
for(i=1; i key = cars2[i];//taking key as car in index i for every iteration
j= i-1;//in insertion sort we will compare elements left to the i till begin of array
while(j>=0 && strcmp(cars[j].make, key.make)>0){//that is what we are doing in this loop comparing the cars from j to index 0 if condition ssatisfies we are swapping
cars[j+1]=cars[j];
j-=1;
}
cars[j+1]=key;
}
}
long end =getMicroTime();//getting the time after the completion of execution of insertion sort
long elapsed = end - start;//calculating the total time taken
cout << "" << endl;
cout << "Time taken using insertion sort:" << ((double)elapsed)/LOOPS << "us"<< endl;//printing the time
cout << "" << endl;
cout << "This list is sorted" << endl;//printing the sorted array
for(int i=0; i cout <<"Make:"< }
}
//QuickSort function
void quickSort(){
//double timediff;
int count;
struct car cars[SIZE];//created array with limited space
struct car cars2[SIZE];
readCars(&cars[0], &count);//reads aray and places the frist item n the first index of array
//clock begin
long start =getMicroTime();//getting the time before the start of quick sort algorithm
for(int j=0; j memcpy(&cars2, &cars, sizeof(car)*SIZE);//copying the cars into cars
int low = 0;//low is the starting of the array
int high = count-1;//high is the no of cars we read since array index starts with zero and count is the no of cars we read we are initializing high to count-1 which indicates the end index of array
quickSortRecursive(cars2, low, high);//calling quicksort function
}
long end =getMicroTime();//here after quick sort gets completed we are getting time again
long elapsed = end - start;//here we are calculating the time taken for quick sort algorithm
cout << "" << endl;
cout << "Time taken using quickSort sort:" << ((double)elapsed)/LOOPS << "us"<< endl;//printing the time taken
cout << "" << endl;
cout << "This list is sorted" << endl;
for(int i=0; i cout <<"Make:"< }//printing the sorted list
}
void quickSortRecursive(car cars[], int low,int high){
if(low int pi = partition(cars, low, high);//this will continue till the all the cars are sorted and here we are calculating the pivoot element by calling the
partition function
//once we get the partition which means that pivot element is correctly placed in its position and the elements that are to be sorted are elements that are left
to the pivot and right to the pivot. That is what we are doing with the below two statements
quickSortRecursive(cars, low, pi-1);
quickSortRecursive(cars, pi+1, high);
}
}
int partition(car cars[], int low, int high){
car pivot = cars[high];//here we are taking pivot as the last element
int i=(low-1);//initializing i to low - 1
for(int j=low; j<=high-1; j++){//continuing upto element that was at the high in the cars structure
int cmp = strcmp(cars[j].make, pivot.make);//comparing the maje of j and make of pivit
if(cmp<=0){//if cars[j] is lessthan pivot then
i++;//incrementing the i and swapping cars at ith position and jth position
car temp= cars[i];
cars[i]= cars[j];
cars[j]=temp;
}
}
//swapping pivot and car in position i+1 with is pivot will be placed at correct position
car temp= cars[i+1];
cars[i+1]= cars[high];
cars[high]=temp;
return (i+1);
}