Could anyone complete normal vector sort in C++? I need to keep track of how muc
ID: 3811932 • Letter: C
Question
Could anyone complete normal vector sort in C++?
I need to keep track of how much work they do while they do their sorting as well. I need to count the number of comparisons it does and how many moves or swaps the algorithm does.
sample bubble sort:
void instrumentedBubbleSort( vector<int> & a, SortStats & stats )
{
bool swapp = true;
while(swapp){
swapp = false;
for (size_t i = 0; i < a.size()-1; i++) {
if ( stats.compares++ && a[i] > a[i+1] ) { // Log the comparison
stats.moves++; // Log that we swapped (moved)
a[i] += a[i+1];
a[i+1] = a[i] - a[i+1];
a[i] -= a[i+1];
swapp = true;
}
}
}
}
need insertion, merge, and quicksort.
void instrumentedInsertionSort( vector<int> & a, SortStats & stats )
{
}
void instrumentedMergeSort( vector<int> & a, SortStats & stats )
{
}
void instrumentedQuickSort( vector<int> & a, SortStats & stats )
{
}
need to track compares + moves for all sorts and please attack short comment to understand how it works.
thx
Explanation / Answer
Here is how it is done for InsertionSort, and MergeSort...
#include <vector>
using namespace std;
void instrumentedBubbleSort( vector<int> & a, SortStats & stats )
{
bool swapp = true;
while(swapp){
swapp = false;
for (size_t i = 0; i < a.size()-1; i++) {
if ( stats.compares++ && a[i] > a[i+1] ) { // Log the comparison
stats.moves++; // Log that we swapped (moved)
a[i] += a[i+1];
a[i+1] = a[i] - a[i+1];
a[i] -= a[i+1];
swapp = true;
}
}
}
}
//need insertion, merge, and quicksort.
void instrumentedInsertionSort( vector<int> & a, SortStats & stats )
{
int temp,i,j;
for(i=1;i<a.size();i++)
{
stats.compares++; //Everytime a comparison is done for i < a.size().
temp = a[i];
for(j=i-1;j>=0 && a[j] > temp;j--)
{
stats.compares += 2; //Everytime 2 comparisons are done for j >= 0, and a[j] > temp.
a[j+1] = a[j];
stats.moves++; //a[j] is moved to right.
}
stats.compares++; //The exit loop comparison which is not counted from inside.
a[j+1] = temp; //A move here...
stats.moves++;
}
stats.compares++; //The exit loop comparison.
}
void instrumentedMergeSort( vector<int> & a, SortStats & stats )
{
MergeSort(a, 0, a.size()-1, stats);
}
void Merge(vector<int> &A, int p, int q, int r, SortStats& stats)
{
int n1 = q - p + 1;
int n2 = r - q;
int L[n1+1], R[n2+1];
for(int i = 0; i < n1; i++)
L[i] = A[p + i];
for(int j = 0; j < n2; j++)
R[j] = A[q + j + 1];
L[n1] = 999;
R[n2] = 999;
int i = 0, j = 0;
for(int k = p; k <= r; k++)
if(L[i] <= R[j])
{ A[k] = L[i++]; stats.moves++; stats.compares++; }
else
{ A[k] = R[j++]; stats.moves++; stats.compares++; }
}
void MergeSort(vector<int> &Array, int p, int r, SortStats& stats)
{
int q;
if(p < r)
{
stats.compares++; //p < r.
q = (p + r) / 2;
MergeSort(Array, p, q, stats);
MergeSort(Array, q+1, r, stats);
Merge(Array, p, q, r, stats);
}
}
void instrumentedQuickSort( vector<int> & a, SortStats & stats )
{
}