Bubble Sort

Simple Algorithms

This is a simple one that everyone has probably run into in any software engineering interview, so it's worth knowing. Though as a web developer must of my career, I was able to get away with not knowing this, but the day I wanted to start doing more complex tasks, it started me down the path of having to learning, at least what is is, and what it is used for.

Copy

The bubble_sort function takes an array arr as input and starts iterating through it using an outer loop. The variable n stores the length of the array.

Inside the outer loop, there's an inner loop that goes through the array elements, comparing adjacent elements. The loop condition n - i - 1 ensures that the last i elements, which are already in their correct positions, are not checked again.

If the current element is greater than the next element, a swap is performed using tuple unpacking (arr[j], arr[j + 1] = arr[j + 1], arr[j]). This places the larger element to the right.

A swapped flag is used to optimize the algorithm. If no swaps occur during an entire pass through the array, it means that the array is already sorted, and the outer loop can be broken early.

After the outer loop completes, the array is sorted, and the sorted array is printed.

Keep in mind that while bubble sort is conceptually simple, it's not very efficient for large arrays due to its O(n^2) time complexity. Other sorting algorithms like merge sort or quick sort are more commonly used for larger datasets.

I'll also be posting what this will look like in Javascript for reference.