Different Types of Sorting Algorithms
When it comes to sorting algorithms, there are a lot of choices. Let’s have a quick look at some of the most important sorting algorithms:
- bubble sort
- merge sort
- quick sort
- insertion sort
Different sorting algorithms each have their own method of sorting the elements. They also each require different amounts of memory and time. A bubble sort is one of the simplest sorting algorithms, so it’s a popular tool for teaching algorithms.
It has O (n2) complexity in the worst case, but O (n) in the best case. That means if the array to be sorted has n items, the bubble sort algorithm needs a number of steps proportional to n2 to execute.
|algorithm||average time complexity||average space complexity|
|bubble sort||O (n2)||O (1)|
|insertion sort||O (n2)||O (1)|
|quick sort||O (n log n)||O (n log n)|
|merge sort||O (n log n)||O (n)|
How a Bubble Sort Works
In this section, we’ll see how exactly a bubble sort works.
Let’s assume that you have a list of numbers which you want to arrange in ascending order. In a bubble sort, the adjacent elements in a list are compared and positions of the elements are swapped if the first element is greater than the second element. This process is repeated until all the elements are in correct order. Elements are bubbled up in a list during the whole process, and that’s why it’s called a bubble sort.
Usually, if a list contains n elements, you need to perform n passes through the entire array in order to put it in order.
Let’s have a look at the following list:
We’ll try to understand what happens in the first iteration.
In each iteration, the algorithm will start by comparing elements from the beginning of the list. First, it’ll compare the first and second elements, and since the first element is greater than the second element, they are swapped as shown in the following list.
Next, it’ll appear the second and third element in the same way. In our example, they are already in order so there’s no need to swap. At the end of the first pass through, the array will look like this:
Now, the algorithm repeats the same process again in the second iteration. And as we said, if a list contains n number of elements, you will generally need to perform n iterations to sort the whole list — comparing n elements each time for an overall time cost of O (n2). However, if any iteration finds the array already in order — meaning no swaps were required — the algorithm will terminate. So, if the array is already in order, the algorithm will terminate after one iteration, making n comparisons, with an overall complexity of O (n).
As shown in the following snippet, the list is in the correct order after three iterations.
Iteration 1: [9,3,10,2,15] => [3,9,10,2,15] => [3,9,10,2,15] => [3,9,2,10,15] => [3,9,2,10,15] Iteration 2: [3,9,2,10,15] => [3,9,2,10,15] => [3,2,9,10,15] => [3,2,9,10,15] => [3,2,9,10,15] Iteration 3: [3,2,9,10,15] => [2,3,9,10,15] => [2,3,9,10,15] => [2,3,9,10,15] => [2,3,9,10,15]
Let’s have a look at the following example.
As you can see, we’ve implemented the
bubbleSort helper function, which helps you to perform array sorting. In the first argument of the the
bubbleSort function, you need to pass an array, and it’ll sort it and return the sorted array as a response.
Let’s quickly go through the implementation of the
Firstly, we measure the length of the input array and assign it to the
n variable. It’ll be used to decide the number of iterations that we’re going to perform to sort the input array.
Moving ahead, we’ve used the
for loop to perform the
n iterations, where
n is the length of the array. For each iteration, we’ve defined another
for loop, which will compare every pair of adjacent array elements, and swap them if the first element is greater than the second element. After each iteration, we’ll check the value of the
swapped variable, and if it hasn’t changed from
true, it means that no swapping was done at all in the last iteration, and thus the input array is now completely sorted. On the other hand, if the
swapped variable has changed from
true, it means that swapping was done at least once in the last iteration, and we’ll proceed for the next iteration. After all iterations, the input array is completely sorted, and we’ll return it.