sorting, end of csc148

well, csc148 has come to an end. the only problem i have now is that most of the stuff in the practice exam we haven't seemed to have learned such as heaps and stuff. hopefully these practice exams aren't representative of the actual exam.

onto today's topic: sorting.

selection sort is when you find the biggest/smallest value of the list, and swap it with the first position. move the position up, and repeat. it has an big O of n^2 because it has to run through the list of n n times. since the entire list is processed to one value, repeated for n values.

quicksort is when you take a list, find a pivot, and split the list into 2 lists, one with values greater than the pivot, and one with smaller values than the pivot. the lists are then recursively processed, and then reassembled. since we're breaking a list of n values down to lists of length 1, the big O of quicksort is nlog(n)

finally, mergesort is similar to quicksort, because we're breaking down a list of n values to lists with length one. then we compare the lists, and then merge the lists based on value. if the top of one list has a greater value, then that is entered into the merged list first, and the comparisons continue until you have one list. likewise, similar to quicksort, the big O of mergesort is nlog(n)

i really enjoyed csc148. im glad that i took this over 108. the only thing now is to ace the exam and to get my assignment 2 remarked because the two mentioned errors earlier managed to chunk a huge mark off.