This is the last blog entry. This week, we just had one class. No new topic was taken up, as this was a review session. We discussed what we did throughout the semester, and were given some tips and possible list of topics that would be included in the final exam. We were advised to refer to assignments, exercises and labs for possible questions. Other than that, this has been a good semester. I have learnt some new things and made some old topics stronger. Had fun studying this course under Professor Danny, but only hated to come at 9 in the morning. Made some friends and enjoyed the labs also with Amir Ali sir. Hoping that the final exam goes well and I finish the course with an A or A+.
The mandatory part was to include selection sort, quick sort, merge sort and efficiency.
1)Selection sort: The selection sort selects the minimum element from a particular index to the end in an iterable and sets the value of that index to it. It then moves on to the next index. The total number of comparisons become n + (n-1) + (n-2)......+1, which gives us n(n+1)/2, and the efficiency becomes O(n2 ). It gets slower as the input size increases.
2)Quick sort: The quick sort involves choosing a pivot element. Then, all values are compared with it, and divided into two partitions, either larger than it, or smaller. Thus, the pivot is at its correct position. This is recursively applied to the two partitions and we finally get a sorted iterable. The efficiency of this sort is O(n logn).
3)Merge sort: The merge sort involves dividing the iterable into two, and doing this recursively until we get a sorted iterable(An iterable with a single element). We then merge these halves.While merging the two halves, we compare each element of the halves, and merge them so as to produce a sorted, larger iterable. We do this until we have just one iterable, fully sorted. The efficiency of this sort is O(n logn).
As we have seen these algorithms, and their efficiencies, we can clearly see that merge and quick sorts take much smaller time as compared to the selection sort, as the size of the input increases. Hence, the use of selection sort is avoided as the input size goes higher.
The mandatory part was to include selection sort, quick sort, merge sort and efficiency.
1)Selection sort: The selection sort selects the minimum element from a particular index to the end in an iterable and sets the value of that index to it. It then moves on to the next index. The total number of comparisons become n + (n-1) + (n-2)......+1, which gives us n(n+1)/2, and the efficiency becomes O(n2 ). It gets slower as the input size increases.
2)Quick sort: The quick sort involves choosing a pivot element. Then, all values are compared with it, and divided into two partitions, either larger than it, or smaller. Thus, the pivot is at its correct position. This is recursively applied to the two partitions and we finally get a sorted iterable. The efficiency of this sort is O(n logn).
3)Merge sort: The merge sort involves dividing the iterable into two, and doing this recursively until we get a sorted iterable(An iterable with a single element). We then merge these halves.While merging the two halves, we compare each element of the halves, and merge them so as to produce a sorted, larger iterable. We do this until we have just one iterable, fully sorted. The efficiency of this sort is O(n logn).
As we have seen these algorithms, and their efficiencies, we can clearly see that merge and quick sorts take much smaller time as compared to the selection sort, as the size of the input increases. Hence, the use of selection sort is avoided as the input size goes higher.
