So, I have to write a program that takes in a string of numbers from the Serial monitor and saves them to two arrays. Both arrays must be sorted from lowest to highest and then have the median calculated. In addition I need to report the time it took for the sort operation to complete so I can compare which is faster. Everything seems to be working, except I don't even know where to start with the in-place sort. I can give you the entirety of my code, but for right now here is just my bubbleSort function. Any help as to where to start with the inplaceSort function would be much appreciated, as well as any comments on my bubbleSort code.
void bubbleSort(int array[], int length)
{
unsigned long time;
unsigned long time0 = millis();
unsigned long time1;
int temp;
int swap;
do
{
swap = 0;
for(int i = 1; i < length; ++i){
if(array[i-1] > array[i]){
temp = array[i];
array[i] = array[i-1];
array[i-1] = temp;
++swap;
}
}
--length;
}
while(swap != 0);
time1 = millis();
time = time1 - time0;
Serial.print("Time: ");
Serial.println(time, DEC);
}
Apart from teaching you to parse data from the serial port, this seems a very strange problem to solve using an arduino - nothing is going on here that couldn't just as easily be done on a PC. Any idea what the aim of the exercise is?
When sorting long Strings, it may be smart to use a second array of numbers:
e.g.
String names[100]; // contails long strings - not smart to swap theese
int tbl [100]; // initially containg numbers from 0..99
then compare. names[tbl[i-1]] >names[tbl*] ==> swap values in tbl // fastes than swapping Strings !* This is waste if problem is to sprt 'int's
macro_c: I believe what my professor meant was insertion sort. That one seems to match up with what he showed us.
cjdelphi: He told us that there are faster sorts, but that he specifically wanted us to use these two. I guess my question would be, how would I begin with implementing an insertion sort?
wildbill: We have already done a lab that was designed to teach us how to parse data from the serial. I think that this lab is designed to teach us how to pass arrays between functions and doing math operations with arrays.
knut_ny: He told us to make an array of int values with a max length of 100, so I don't know if that would do me any good. He also told us that we should only have two arrays, no more. Both arrays get filled with the same data that the user enters into the serial, then one of the array has a bubble sort performed while the other has an insertion sort.
An insertion sort is just what it sounds like. As each new member of a list is received, it is placed in the order location of the array. You shuffle all the other elements in the array along by one to 'insert' the new element where it belongs.
Have you tried Googling "insertion sort"? It will probably get you what you need.