Javascript를 사용한 정렬 알고리즘(2부)

약속대로 게시물의 두 번째 부분이 있습니다. 첫 번째 부분을 읽을 수 있습니다.

세 가지 추가 정렬 알고리즘의 Javascript 구현을 보여 드리겠습니다.

퀵 정렬

힙 정렬

카운팅 정렬

다시 말하지만 이것은 알고리즘의 작동 방식과 성능에 대한 자세한 설명이 아닙니다. 그것에 대해 읽고 싶다면 여기 내가 찾은 멋진 리소스가 있습니다. Sorting Algorithms

간단하게 하기 위해 5개의 요소list만 있는 간단한 목록[4, 2, 3, 1, 5]을 정렬하겠습니다.

빠른 정렬

병합 정렬과 마찬가지로 이 알고리즘은 분할 정복 방식을 사용합니다. 피벗을 선택하고 해당 피벗과 관련하여 목록을 나누는 방식으로 작동합니다. 피벗보다 큰 모든 요소는 피벗의 오른쪽으로 이동하고 피벗보다 작거나 같은 모든 요소는 피벗의 왼쪽으로 이동합니다. 양쪽의 요소는 빠르게 정렬되며 전체 목록이 정렬될 때까지 반복됩니다.

비주얼

이것에 대한 시각은 알고리즘이 실제로 어떻게 작동하는지 설명하는 데 명확하지 않았습니다.

암호

function quickSort(list) {
    if (list.length <= 1) { 
        return list
    } else {
        const left = []
        const right = []
        const sorted = []
        const pivot = list.pop() // we're picking the last item to act as the pivot
        const length = list.length

        for (let i = 0; i < length; i++) {
            if (list[i] <= pivot) {
                left.push(list[i])
            } else {
                right.push(list[i])
            }
        }

        return sorted.concat(quickSort(left), pivot, quickSort(right))
    }
}

const list = [4, 2, 3, 1, 5]

const sorted = quickSort(list)

console.log(sorted)

힙 정렬

이 알고리즘은 binary-heap 이라는 데이터 구조를 활용합니다. 힙 정렬은 오름차순으로 요소를 정렬하기 위해 최대 힙을 생성한 다음 루트 노드를 마지막 노드로 교체하고 이 작업이 수행될 때마다 힙에서 정렬된 노드를 삭제하는 방식으로 작동합니다.

비주얼

암호

// create max heap
function maxHeap(input, i) {
    const left = 2 * i + 1
    const right = 2 * i + 2
    let max = i

    if (left < arrLength && input[left] > input[max]) {
        max = left
    }

    if (right < arrLength && input[right] > input[max])     {
        max = right
    }

    if (max != i) {
        swap(input, i, max)
        maxHeap(input, max)
    }
}

function swap(input, indexA, indexB) {
    const temp = input[indexA]

    input[indexA] = input[indexB]
    input[indexB] = temp
}

function heapSort(input) {   
    arrLength = input.length

    for (let i = Math.floor(arrLength / 2); i >= 0; i -= 1)      {
        maxHeap(input, i)
      }

    for (i = input.length - 1; i > 0; i--) {
        swap(input, 0, i)
        arrLength--

        maxHeap(input, 0)
    }
    return
}

let arrLength

const list = [4, 2, 3, 1, 5]

const sorted = heapSort(list)

console.log(list)

카운팅 정렬

지금까지 다룬 알고리즘에 비해 카운팅 정렬이 다소 독특하다는 것을 알게 될 것입니다. 정렬하는 동안 요소를 비교하지 않기 때문입니다. 숫자 키를 기반으로 작동합니다. 계산 배열을 만든 다음 이를 사용하여 요소의 올바른 위치를 결정함으로써 이를 수행합니다.

비주얼

암호

function countingSort(list, min, max)
  {
      let i
      let z = 0
      const count = []

      for (i = min; i <= max; i++) {
          count[i] = 0
      }

      for (i=0; i < list.length; i++) {
          count[list[i]]++
      }

      for (i = min; i <= max; i++) {
          while (count[i]-- > 0) {
              list[z++] = i
          }
      }
      return list
  }

const list = [4, 2, 3, 1, 5]
const min = Math.min(...list)
const max = Math.max(...list)
const sorted = countingSort(list, min, max)

console.log(sorted)

즐거운 코딩하세요!