Sorting Algorithms  Bubble Sort (Part 1/3)
The goal of a Sorting Algorithm is to change the order of the elements in an array. The sorting can be done either inplace, reorder the datastructure within, or notinplace by copying to a new datastructure. The inplace 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 inplace 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
The efficiency is:
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.
Because there is no extra array (the sorting is inplace), 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: