Bubble Sort, Selection Sort, Insertion Sort | Data Structures & Algorithms in JavaScript

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(n²).

// 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(n²).

// 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(n²).

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!

The above is the detailed content of Bubble Sort, Selection Sort, Insertion Sort | Data Structures & Algorithms in JavaScript. For more information, please follow other related articles on the PHP Chinese website!