Sorting Algorithms?
So, you're probably wondering, "What exactly are sorting algorithms?". Well, a sorting algorithm is simply used to rearrange a given array or some list of elements in an ascending or descending order. With the use of a comparison operator that decides the new order of the elements in the data structure.
An example would be if we had an array of unsorted numbers, we wanted our algorithm to sort them in ascending order.
[3,5,7,1,2] => [1,2,3,5,7]
Bubble Sort
Now, A Bubble Sort algorithm is one of the simplest sorting algorithms to understand. Bubble sort works by repeatedly swapping the adjacent elements if they are in the wrong order. Let's say we are ascending from smallest to largest in an array:
What Exactly Is Happening Here?
What our bubble sort algorithm is doing here is, through every single iteration, it is continuously comparing each pair of integers, determining where to place those two integers in regards to how we design the code. In the example above, it is sorting in ascending order from smallest to largest.
Pseudocode
Here are some steps to get you started on how you can implement a __bubble sort algorithm.
- First, create a function called bubbleSort that takes in an array.
- Using a for loop, with a variable i from the end of the array to the beginning.
- Using an inner loop, with a variable of j that starts at the beginning and ends i - 1.
- Compare if arr[j] is greater than arr[j + 1], swap those two values.
- at the end return the sorted array
The Code
function bubbleSort(arr){
for(let i = arr.length - 1; i > 0; i++){
for(let j = i -1; j < arr.length; j++){
if(arr[j] > arr[j + 1]){
var temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
If you take a good look at this code, we aren't quite finished just yet! In the scenario of our data almost sorted or is already sorted, it doesn't need to be sorted again. Yet, right now our bubble sort algorithm doesn't regard if the array is somewhat or already there. If we had an array of lengths 32 or more, this kind of logic will take up unnecessary space.
To combat this, we can have checks within our code asking, "Did we make any swaps here?", If no, then we must be done in our iteration.
Opimization
So, to optimize this code to prevent unnecessary swapping from happening, we can use a noSwaps variable that will take in a boolean.
function bubbleSort(arr){
var noSwaps;
for(let i = arr.length - 1; i > 0; i++){
noSwaps = true
for(let j = i -1; j < arr.length; j++){
console.log(arr, arr[j], arr[j + 1])
if(arr[j] > arr[j + 1]){
var temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
nSoSwaps = false
}
}
if(noSwaps) break
}
return arr
}
Here, if there aren't anymore swaps within an iteration, we must break out of the code and return our array. This gets rid of the unnecessary actions of our code iterating through the area for a possible swap.
Conclusion
That concludes this blog on bubble sort! Stay tuned for my next blog that will focus on Selection Sort
Top comments (2)
I still struggle with understanding sorting algorithms and this actually helped! ✌
Thank you Oscar! Some times I get the hang of it! Colt Steele's master class on udemy has been helping a lot