The goal of a Sorting Algorithm is to change the order of the elements in an array. The sorting can be done either in-place, re-order the datastructure within, or not-in-place by copying to a new datastructure. The in-place algorithms are low space complexity. The choice of an algorithm for an application is mainly driven by the application itself.
Here is a series of 3 short posts on the topic of Sorting Algorithms…in fact the most common ones:
- Bubble Sort
- Merge Sort
- Quick Sort
Part I: Bubble Sort
Bubble Sort is a in-place sorting algorithm, also called Naive approach. The idea is to travel through every element of the array and compare with the next element.
Additional iterations might be required to completely sort the list.
Efficiency
Time efficiency:
Therefore, the Bubble Sort time efficiency is :
-
in the worst case:
-
in the average case:
-
in the best case (the list is already sorted): but w e still need to go through the array at once.
Space efficiency:
Because there is no extra array (the sorting is in-place), the space complexity is constant.
Quizz
The Quizz below is from the Machine Learning Nanodegree of Udacity, and in particular the module related to Technical Interviews.
If you were to perform Bubble Sort on the following array, what would be the 3rd iteration look like?
Answer:
