Bubble Sort

Bubble sort is a simple algorithm, which works by swapping the adjacent elements if they are placed in wrong order (for example, for ascending order should be: arr[i] <= arr[i+1]). For sorting, iterate array n times, and on each iteration look at pairs of adjacent elements. For each pair, if arr[i+1] > arr[i], swap these elements. This way, in the end of current iteration, we'll move the greatest element to the end of the unsorted array. At the end, you'll get the sorted array.

Example 1

Example 2

Let's do the Bubble Sort setp by step.

arr = [4, 2, 1, -1, 7]

First iteration:

[4, 2,1, -1, 7] -> [2, 4, 1, -1, 7]

[2, 4, 1, -1, 7] -> [2,1, 4, -1, 7]

[2, 1, 4, -1, 7] -> [2, 1, -1, 4, 7]

[2, 1, -1, 4, 7] -> [2, 1, -1, 4, 7]

Second iteration:

[2, 1, -1, 4, 7] -> [1, 2, -1, 4, 7]

[1, 2, -1,4, 7] -> [1, -1, 2, 4, 7]

[1, -1, 2, 4, 7] -> [1, -1, 2, 4, 7]

Third iteration:

[1, -1, 2, 4, 7] -> [-1, 1, 2, 4, 7]

[-1, 1, 2, 4, 7] -> [-1, 1, 2, 4, 7]

Fourth iteration:

[-1, 1, 2, 4, 7] -> [-1, 1, 2, 4, 7]

Thus, on each iteration the biggest element from the unsorted part relocates to its position in sorted subarray.

Time complexity of the algorithm is O(N^2), because there are two nested loops of length up to N.

Space complexity: O(1). We can swap elements in-place, so no additional memory is needed.