버블정렬, 선택정렬, 삽입정렬 | JavaScript의 데이터 구조 및 알고리즘

정렬 알고리즘은 많은 계산 작업의 중추이며 효율적인 액세스 및 처리를 위해 데이터를 구성하는 데 중요한 역할을 합니다. 알고리즘의 세계를 이제 막 탐구하기 시작한 초보자이거나 지식을 새롭게 하려는 숙련된 개발자라면 이러한 기본 정렬 기술을 이해하는 것이 필수적입니다. 이번 게시물에서는 버블 정렬, 선택 정렬, 삽입 정렬 등 보다 기본적인 정렬 알고리즘에 대해 살펴보겠습니다.

버블정렬

버블 정렬은 간단한 비교 기반 정렬 알고리즘입니다. 목록을 반복적으로 살펴보고, 인접한 요소를 비교하고, 순서가 잘못된 경우 교체합니다. 이 프로세스는 더 이상 교체가 필요하지 않을 때까지 계속되며 이는 목록이 정렬되었음을 나타냅니다. 버블 정렬은 이해하고 구현하기 쉽지만 대규모 데이터 세트에는 비효율적이므로 주로 교육 목적과 소규모 데이터 세트에 적합합니다.

버블 정렬의 시간 복잡도는 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))

선택 정렬

선택 정렬은 간단한 비교 기반 정렬 알고리즘입니다. 목록을 정렬된 영역과 정렬되지 않은 영역으로 나누어 작동합니다. 정렬되지 않은 영역에서 가장 작은(또는 가장 큰) 요소를 반복적으로 선택하고 정렬되지 않은 첫 번째 요소와 교환하여 정렬된 영역을 점차적으로 확장합니다. 선택 정렬은 대규모 데이터 세트에 가장 효율적이지는 않지만 이해하기 쉽고 교체 횟수를 최소화할 수 있다는 장점이 있습니다.

선택 정렬의 시간 복잡도는 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))

삽입 정렬

삽입 정렬은 한 번에 한 요소씩 최종 정렬 목록을 작성하는 직관적인 비교 기반 정렬 알고리즘입니다. 목록의 정렬되지 않은 부분에서 요소를 가져와서 정렬된 부분 내의 올바른 위치에 삽입하는 방식으로 작동합니다. 삽입 정렬은 작은 데이터세트나 거의 정렬된 데이터에 효율적이며 더 복잡한 알고리즘에 대한 간단한 대안으로 실제 애플리케이션에서 자주 사용됩니다.

삽입 정렬의 시간 복잡도는 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))

마무리

버블 정렬, 선택 정렬, 삽입 정렬과 같은 기본 정렬 알고리즘은 대규모 데이터세트에 가장 효율적이지는 않지만 알고리즘 설계를 이해하는 데 훌륭한 기반을 제공합니다. 이 게시물이 도움이 되었다면 귀하의 의견을 듣고 싶습니다. 아래에 의견을 남기거나 통찰력을 공유하거나 질문이 있으면 최선을 다해 답변해 드리겠습니다.

즐거운 코딩하세요!

위 내용은 버블정렬, 선택정렬, 삽입정렬 | JavaScript의 데이터 구조 및 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!