What are Sorting Algorithms
Sorting algorithms are used to rearrange elements in a collection (such as an array or a list) into a particular order. For example, taking an input of [2, 3, 1, 4] and sorting it in ascending order: [1, 2, 3, 4]. In programming there are many different sorting algorithms. We’re going to explore the most basic, Bubble Sort, in this blog post, but here’s a quick overview of other common sorting algorithms, along with links where you can learn more about them:
Selection Sort: Finds the smallest (or largest, depending on the sorting order) element in the unsorted portion of the list and swaps it with the first unsorted element.
Insertion Sort: Builds the sorted portion of the list one element at a time by repeatedly taking the next element from the unsorted portion and inserting it into its correct position in the sorted portion.
Merge Sort: Divides the list into smaller sublists, recursively sorts each sublist, and then merges them back together.
QuickSort: Selects a pivot element from the list and partitions the other elements into two sublists according to whether they are less than or greater than the pivot.
What is Bubble Sort
Bubble Sort is a simple sorting algorithm that starts at the beginning of a list and compares each pair of adjacent elements. If the elements are in the wrong order (i.e., the element on the left is greater than the element on the right if you’re sorting in ascending order), the elements are swapped. This process is repeated for each pair of adjacent elements in the list.
Eg. Bubble Sort in Ascending Order:
Code Examples
Let’s dive into how you would set up an iterative Bubble Sort in Python:
The outer loop (for i in range(n)) loops through the array from 0 to n-1. N is the length of the array. The inner loop (for j in range(0, n-i-1)) starts another loop that iterates from 0 to n-i-2. This loop performs the comparison and swaps elements with each pass through the array. Since the array’s index starts at zero, we subtract 1 from n, and n-i-1 ensures that the algorithm doesn’t compare already sorted elements in subsequent passes.
if arr[j] > arr[j+1]: checks if the current element (arr[j]) is greater than the next element (arr[j+1]). If it is, it means they are in the wrong order and need to be swapped. arr[j], arr[j+1] = arr[j+1], arr[j] swaps the current element (arr[j]) with the next element (arr[j+1]). This sorts the adjacent elements in the array.
For reference, here’s the same code in JavaScript:
Big O Analysis
Time Complexity: O(N^2)
The time complexity of a Bubble sort algorithm is O(N^2), where N represents the number of elements in the array. In the worst-case scenario, the algorithm would need to perform comparisons and swaps with every other element in the array, so it would need to run through N elements. Since we have a nested loop, we take the time complexity of the outer loop (0(N)) and multiply it by the time complexity of the inner loop (O(N)) to arrive at O(N^2).
Space Complexity: O(1)
Bubble Sort is an in-place sorting algorithm because it doesn’t require any extra space proportional to the size of the input array. Its space complexity is O(1) since the space used by the algorithm is constant regardless of the size of the input array.
Advantages & Disadvantages
Some of the advantages of Bubble Sort compared to other sorting algorithms is that it is easy to understand and to set up, and it doesn’t require any additional memory space. Since Bubble Sort algorithms have a relatively high time complexity of O(N^2), one of their disadvantages is that they can be slow for large data sets.
Sources:
Flatiron School Curriculum, Data Structures & Algorithms, Days 1-2: Bubble Sort
GeeksForGeeks, Bubble Sort – Data Structure and Algorithm Tutorials
W3Schools, DSA Bubble Sort
YouTube, Telusko, #70 Python Tutorial for Beginners | Bubble Sort in python | List Sort
