Sorting algorithms are the backbone of many computational tasks, playing a crucial role in organizing data for efficient access and processing. Whether you’re a beginner just starting to explore the world of algorithms or a seasoned developer looking to refresh your knowledge, understanding these fundamental sorting techniques is essential. In this post, we’ll explore some of the more basic sorting algorithms – Bubble Sort, Selection Sort, and Insertion Sort.
Bubble Sort
Bubble Sort is a simple, comparison-based sorting algorithm. It repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until no more swaps are needed, indicating that the list is sorted. While easy to understand and implement, Bubble Sort is inefficient for large datasets, making it suitable mainly for educational purposes and small data sets.
Bubble Sort has a time complexity of O(n2).
// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]
function bubbleSort (input) {
const n = input.length
const sortedArray = [...input]
// loop n times
for (let i = 0; i < n; i++) {
// loop through all n-1 pairs
for (let j = 0; j < n-1; j++) {
// if a > b, swap; else do nothing
if (sortedArray[j] > sortedArray[j+1]) {
const temp = sortedArray[j]
sortedArray[j] = sortedArray[j+1]
sortedArray[j+1] = temp
}
}
}
return sortedArray
}
console.log("Input:", inputArray)
console.log("Ouput:", bubbleSort(inputArray))
Selection Sort
Selection Sort is a straightforward, comparison-based sorting algorithm. It works by dividing the list into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and swaps it with the first unsorted element, gradually growing the sorted region. Selection Sort is not the most efficient for large datasets but is easy to understand and has the advantage of minimizing the number of swaps.
Selection Sort has a time complexity of O(n2).
// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]
function selectionSort (input) {
const n = input.length
const sortedArray = [...input]
// loop n times
for (let i = 0; i < n; i++) {
// start from i'th position
let lowestNumberIndex = i
for (let j = i; j < n-1; j++) {
// identify lowest number
if (sortedArray[j] < sortedArray[lowestNumberIndex]) {
lowestNumberIndex = j
}
}
// swap the lowest number with that in i'th position
const temp = sortedArray[i]
sortedArray[i] = sortedArray[lowestNumberIndex]
sortedArray[lowestNumberIndex] = temp
}
return sortedArray
}
console.log("Input:", inputArray)
console.log("Ouput:", selectionSort(inputArray))
Insertion Sort
Insertion Sort is an intuitive, comparison-based sorting algorithm that builds the final sorted list one element at a time. It works by taking elements from the unsorted portion of the list and inserting them into their correct position within the sorted portion. Insertion Sort is efficient for small datasets or nearly sorted data and is often used in practical applications as a simpler alternative to more complex algorithms.
Insertion Sort has a time complexity of O(n2).
function insertionSort (input) {
const n = input.length
const sortedArray = [...input]
// loop n times, starting at index 1
for (let i = 1; i < n; i++) {
// start at index 1
const comparedNumber = sortedArray[i]
let tempIndex = i
// compare with previous numbers (right to left)
for (let j = i-1; j >= 0; j--) {
// if number in current index is larger than compared number, swap
if (sortedArray[j] > comparedNumber) {
sortedArray[tempIndex] = sortedArray[j]
sortedArray[j] = comparedNumber
tempIndex = j
} else {
// OPTIONAL: else exit
break
}
}
}
return sortedArray
}
console.log("Input:", inputArray)
console.log("Ouput:", insertionSort(inputArray))
Wrapping Up
While basic sorting algorithms like Bubble Sort, Selection Sort, and Insertion Sort may not be the most efficient for large datasets, they offer a great foundation for understanding algorithm design. If you found this post helpful, I’d love to hear your thoughts. Drop a comment below, share your insights, or ask any questions you have – I will try my best to answer them.
Happy coding!
Leave a Reply