Summary of Sorting Algorithms

Congratulations on completing session 3 of this module. This marks the end of this module.

In this module, you learnt about the following topics:

• Searching

  • Linear search

  • Binary search

Binary search was found to have O(log N) time complexity, compared to O(N) time complexity of linear search

• Sorting

  • Bubble sort

  • Selection sort

  • Insertions sort

  • Merge sort

  • Quicksort

Among all the five sorting algorithms, merge sort and quicksort were found to have O(N log N) time complexity. Rest of them have O(N${}^2$) time complexity in average and worst cases.

Please download the lecture notes for this module from the link given below.

Video Transcript

Congratulations. With this session you have finished the second module of this course. In this session you learnt about the various sorting algorithms, namely bubble sort, selection sort, insertion sort, quicksort and Merge sort. Bubble sort, selection sort and insertion sort were all found to have $O\left(N\right)$Square complexity. We also mentioned that despite all three of them having the same big O, they were not equally efficient. The efficiency depends on the kind of data sets you deal with. Then we learned about two sorting algorithms merge sort and Quicksort, which used the divide and conquer technique in their implementation. These algorithms showcased improved efficiency by huge margins as both of them had complexities of $O\left(log\right(N\left)\right)$, which is very fast in comparison to $O\left(N^2\right)$ You can read about a few other sorting algorithms in the links below.

Video Recap

 The session marks the end of the second module of the course.

• The session covers different sorting algorithms, including bubble sort, selection sort, insertion sort, quicksort, and merge sort.

• Bubble sort, selection sort, and insertion sort have$O\left(N\right)$Square complexity.

• Despite having the same big(O), these algorithms are not equally efficient, and their efficiency depends on the kind of data sets.

• Merge sort and Quicksort use the divide and conquer technique in their implementation, leading to improved efficiency by huge margins.

• Both merge sort and Quicksort have complexities of $O\left(log\right(N\left)\right)$, which is faster than $O\left(N^2\right)$.