1 min read
The Simplest Sorting Ever Bubble Sort
Last Update: 29 September, 2022Bubble sort is probably the simplest way of sorting you can think of when creating a sorting algorithm. The idea is that you go through the algorithm sorting the adjacent items again and again until we have a sorted array.
§Let Us Begin
Bubble sort was probably the first sorting algorithm I learned and knew we could probably do better than that. It might not be the fastest algorithm but it's still important to know and understand. One of the very good reasons to learn this algorithm is that it's apparently one of the most asked interview questions. So let's get to it.
As explained above, we just go through and through the array until the array is sorted. We need two loops (nested) for this algorithm. In the first loop we will go from the beginning to the end and in the second one we will go from the beginning to array's length minus one minus first loop's index n-1-i. This is important because we are always finding the biggest value in our array and carrying to the last index (if we are sorting min to max of course). So in each finalization of the second loop we carry the biggest value to the end of the array and as we are done with them we don't need to check those values anymore.
Ok, I know this is more than enough text for an algorithm this simple. We can start with the code now, I wrote it in python because I like to practice algorithms with python and I believe it's much easier than alternatives (such as Java) :
def bubbleSort(arr, n):
for i in range(n): # Go through the array
for j in range(0, n-i-1): # Loop through the unsorted parts
# In each iteration carry the current max to the last by switching
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
if __name__ == "__main__":
arr = [2, 3, 5, 1, 7, 6, 4]
length = len(arr)
bubbleSort(arr, length)
print(arr)
§Conclusion and Complexity
As we can see bubble is sort definitely not the fastest soting algorithm around in most cases. Because of the nested loop and basically going through the array n * n times our worst case is O(N²). We won't need an auxiliary array for this algorithm so our space complexity is constant (O(1)).
Maybe consider this algorithm when you have the time but not the space.
Keep on learning!
Ilker AkbiyikTable of Contents
Related Posts
