This week in lecture we learned about a few sorting
algorithms. Three of the ones we learned are selection sort, quick sort and
merge sort. I already learned about selection sort from CSC108, and I am very
familiar with it. However, quick and merge sort were new to me. It’s
interesting how many different ways there are to sort and produce the same
product.
From what I learned in class, quick sort takes a value or
pivot and uses this pivot to divide the
list into two separate lists. Basically, it compares each value to its pivot
and either places each value into a greater than, or less than list. The pivot
is sorted since it is placed between the two sub lists. Then, using recursion,
quick sort will completely sort the list by picking new pivots until each value
is in its proper place.
The merge sort algorithm is much different. It divides the
list into several sub lists that contain only one element in each. Then, the
algorithm gradually merges sub lists and sorts each new list. This step
continues to happen recursively until there is one sorted list left.
I can’t decide which of the two is faster and more
efficient: merge or quick sort. I guess that it depends on the case. For
example, if you have a large list, and for each new pivot in quick sort your
algorithm happens to choose the smallest value, your quick sort will be vary
slow. However, if your code selects the median value every time, your quick
sort will be much more efficient. Since it chooses a value at random, the
efficiency of your algorithm may vary.