Wow, time flies, especially when its a good case scenario for sorting. Its already the end of the term, and CSC148 is coming to an end. One week of classes remain, and then it's time for finals. Looking back at all the concepts we've learned, sorting was quite complex. There were many sorting methods; bubble, insertion, selection, merge, quick. It was also possible to combine multiple methods, dictating which sorting algorithm to use depending on the condition (i.e. length of list, length of segment being sorted, etc).
The earlier sorting algorithms we touched upon (bubble, inserting, selection) were the less complex sorting algorithms, usually having a run time of O(n^2), were easier for programmers and coders to re-create on their own, and could handle small arrays of items to sort with ease. The problem is when the array of elements becomes too large. For example, using bubble sort, given the worst case scenario, on a list of 10000 elements means that we'd have to compare the first element (position 0) with the remaining 9999 elements, moving it over each time until it reaches the end of the list. Then the new first element at position 0, must be compared and move with the remaining 9998 elements... Repeat this until we reach comparing the first element with none, since the rest are sorted. Bubble sort takes a run-time of O(n^2) meaning it'd take 10000*10000 steps to sort the worse case scenario list of 10000 elements.
To solve the problem of taking hours or days to complete the sorting, programmers and coders had developed more complex, but stronger sorting algorithms, such as merge sort and quick sort, which have O(n log(n)) for worst case scenarios. Comparatively, merge or quick sort takes significantly less time to sort larger arrays of elements than bubble, insertion, or selection sort since the big O comparisons are n*log(n) against n^2.
Some people may say that sorting methods and algorithms are redundant, since there is no need to sort the elements if you can just dive into the array and search for your desired element. However, sorting an array can help provide further insight on the elements and certain properties of the array, and can also help detect a possibility of a pattern in the elements. Sorting an array can also reduce consequent run-time of searches because you can narrow your range for searching in a sorted array since you know approximately where to find specific elements.
I've had some friends tell me that computer science isn't something you could easily apply to other courses or situations in life, but I've proved them wrong with sorting! Finals are approaching... I can leave all my notes unsorted and spend an extended period of time every time I wanted to find a certain note to study from, or I can spend a small amount of time to sort my notes in chronological order. this way, when I want to find a note from somewhere between mid-February and early-March, I know I can spend less time looking for it by looking only between the first quarter and the middle of my notes since that would correspond to the notes taken within that time frame!
HAH, take that non comp-sci friends! Computer science is everywhere!... Now, lets determine how long it will take me to use insertion sort to organize my notes.... Will it be in the minutes or hours....
No comments:
Post a Comment