there are some interesting sort visualizations at
https://imgur.com/a/voutF
Videohere is a little demo on performance
For this lab we will do 3 variants of the bubble sort
here is a little demo on how to make a pass through an array
the code is basically
for (int loop =0; loop < size -1;loop++)
{
if (array[loop] > array[loop+1])
std::swap(array[loop],array[loop+1]);
}
all 3 sorts will use this method of passing through the array, we will change how many times we pass through the array and how and when we stop to increase efficiency
now you will notice that after each pass the largest value gets pushed to the back
after the first pass the largest value will be at the end
after the second pass the largest two values will be at the end
after the third pass the largest three values will be at the end
IMPORTANT:
there are 20 values in this array, the size is 20
we dont loop from 0 to 20, we loop from 0 to 18 (size-2)
the valid index values are 0 to 19
but since we compare loop and loop+1
when loop is 0 we are comparing 0 and 1
when loop is 5 we are comparing 5 and 6
when loop is 18 we are comparing 18 and 19 (19 is the last value so we want to stop here)
imagine if we go one more
when loop is 19 we are comparing 19 and 20 , index 20 is past the end of our array
this will not always cause a segmentation fault, generally if you only go one past the end of our
array it will just simply do it and not have an issue .. what is in the position one past the end of our array??
we dont know so it will make the comparison and maybe a swap.. if this happens we pull some random number
into the array we are trying to sort.
Two test mains have been provided to test your functions, make your output match FOR BOTH examples
AND make sure your logging matches the examples as well
put your function bodies in the functions.h file
File: functions.h
#pragma once
#include "cmpslib19.h"
#include "easylogging++.h"
int Sort1(int *array, int N)
{
// parameter one is a pointer to our array, parameter two is our size
// a basic bubble sort
// since one pass through the array will not sort it so just repeat the inner loop N times
// for the outer loop use a for loop ( 0 to N-1 )
// do the inner loop to make a pass through the array, just like the example
// for loop inner ( 0 to N-2)
// compare two adjacent items (inner and inner+1) and std::swap if necessary
// log the start , end and the value returned ( look at the example log)
// use an int to count up of how many comparisons occur and return it
// everytime you compare array[loop] with array[loop+1] increment your count
// note: basically requires n^2 comparisons, always the same
}
int Sort2(int *array, int N)
{
// make temp int end set to N-1
// for the outer loop use a while loop .. while (end >1)
// change the inner loop to only to from 0 to end not N-2
// for loop inner( 0 to < end) )
// compare two adjacent items (inner and inner+1) and std::swap if necessary
// after inner loop decrement end
// note: basically requires (n(n+1))/2 comparisons, always the same
// log the start , end and the value returned ( look at the example log)
// like Sort1 return the number of comparisons we did
}
int Sort3(int *array, int N)
{
// same basic logic as Sort2
// make a bool flag called IsSorted , set to false
// change the outer while loop to
// while ( IsSorted == false)
// just before starting the inner loop set IsSorted = true
// use the same inner loop from Sort2
// if during the pass through the array we need to swap two values it is not sorted
// so set storted to false so we will repeat the outer while loop one more time at least
// note: this takes basically <= (n(n+1) / 2 comparisons, can vary greatly depending on how unsorted the target is
// log the start , end and the value returned ( look at the example log)
// like Sort1 and 2 return the number of comparisons we did
}