The algorithms we analyzed in class were mainly selection
sort, merge sort, and quick sort.
In selection sort, we would look for the largest value by
going through the list and keeping track of the largest value thus far, and
then put it in its proper location (the right-most spot). Selection sort has a
running time of O(n^2).
In merge sort we would keep splitting the list into halves
and each of those halves into halves until we have one-element lists. Then we
would compare each pair to make those mini lists to create bigger sorted lists,
and eventually we would reach the sorted list. Merge sort has a running time of
O(n log n).
In quick sort we choose a value in the list as a 'pivot'.
Numbers to the left of the pivot are to be smaller than the pivot, and numbers
to the right are to be greater than the pivot. We start from the left side and
keep going right until we reach a number that is greater than or equal to the
pivot. This is the ‘leftmark’. We also start from the right side and keep going
left until we reach a number that is less than or equal to the pivot. This is
the ‘rightmark’. Then we swap the leftmark and rightmark. We continue going
left and right nor new leftmarks and rightmarks to swap until the leftmark and
rightmark reach each other. We then put a pivot in between. Then we repeat the
process with left and right sides of pivot as two different lists. Quick sort
has a running time of O(n log n) in its best case scenario and O(n^2) in its
worst case scenario (this worst case scenario is extremely rare).
Choosing the most efficient algorithm will generally involve
choosing the algorithm with the lowest big-O notation. In lab 9 we analyzed the
running time of these algorithms by sorting a few thousand values. As we
increased the number of values the algorithms with O(n^2) running time lagged
significantly compared to the O(n log n) algorithms. Efficiency is increased
dramatically when the algorithm sorts recursively as opposed to using multiple
loops.
After reading the slogs of my classmates, it seems that
everyone has a tight grasp on comparing different sorting algorithms.
No comments:
Post a Comment