빠른 정렬 알고리즘 학습

빠른 정렬은 가장 효율적인 알고리즘 중 하나이며 분할 정복 기술을 사용하여 배열을 정렬합니다.

빠른 정렬의 작동 방식

빠른 정렬의 주요 아이디어는 정렬되지 않은 배열에서 한 번에 하나의 요소를 올바른 위치로 이동하도록 돕는 것입니다. 이 요소를 피벗이라고 합니다.

다음 경우에 피벗 요소가 올바른 위치에 있습니다.:

1. 왼쪽의 모든 요소가 더 작습니다.
2. 오른쪽의 모든 요소가 더 큽니다.

아직 왼쪽이나 오른쪽의 숫자가 정렬되어 있는지는 중요하지 않습니다. 중요한 것은 피벗이 배열의 올바른 위치에 있다는 것입니다.

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

이 모든 것은 피벗이 23인 배열의 유효한 출력입니다.

피벗의 올바른 위치 찾기

빠른 정렬은 피벗이 배열에서 올바른 위치를 찾는 데 도움이 됩니다. 예를 들어 피벗이 배열의 시작 부분에 있지만 가장 작은 숫자가 아닌 경우 Quick Sort는 배열에 5개의 작은 요소를 위한 공간을 만들기 위해 5단계를 이동해야 한다고 결정합니다. 즉, 그러한 요소가 5개 있다고 가정합니다. 숫자.

[10, 4, 15, 6, 23, 40, 1, 17, 7, 8] 배열이 있고 10이 피벗이라고 가정해 보겠습니다:

이 시점에서:

• 숫자 10은 자신이 올바른 위치에 있는지, 거기에 도달하려면 몇 걸음을 움직여야 하는지 모릅니다. Quick Sort는 10을 다음 인덱스의 값과 비교하는 것으로 시작됩니다.
• 4가 더 작은 것을 확인하면 Quick Sort는 4가 그 앞에 오도록 피벗이 한 단계 앞으로 이동해야 한다고 기록합니다.
• 따라서 numberOfStepsToMove는 1씩 증가합니다.

다음 인덱스 2에서 값은 15로 10보다 큽니다. 조정이 필요하지 않으므로 Quick Sort는 걸음 수를 변경하지 않고 배열의 다음 요소로 이동합니다.

다음 인덱스에서 값은 10보다 작은 6입니다. Quick Sort는 걸음 수를 2로 늘립니다. 이제 피벗은 두 개의 작은 숫자인 4와 6을 위한 공간을 만들어야 하기 때문입니다. .

이제 배열의 왼쪽에 더 작은 숫자를 나란히 유지하려면 6을 15로 바꿔야 합니다. 현재 인덱스와 numberOfStepsToMove 값을 기준으로 숫자를 바꿉니다.

Quick Sort는 계속해서 배열을 반복하면서 피벗보다 작은 숫자 수에 따라 numberOfStepsToMove를 늘립니다. 이는 피벗이 올바른 위치로 이동하는 데 필요한 거리를 결정하는 데 도움이 됩니다.

numberOfStepsToMove는 23 또는 40에 대해 변경되지 않습니다. 두 값 모두 피벗보다 크고 배열에서 피벗 앞에 오면 안 되기 때문입니다.

이제 Quick Sort가 인덱스 6의 값 1로 반복되면 numberOfStepsToMove는 3으로 증가하고 인덱스 3의 숫자로 바꿉니다.

Quick Sort는 배열의 끝에 도달할 때까지 이 프로세스를 계속합니다.

이제 배열의 끝에 도달했으므로 10보다 작은 숫자가 5개 있다는 것을 알게 되었습니다. 따라서 피벗(10)은 모든 숫자보다 큰 올바른 위치로 5단계 앞으로 이동해야 합니다. 그 앞에 숫자가 있습니다.

코드에서 어떻게 보이는지 살펴보겠습니다:

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

이제 피벗을 배치할 위치를 찾는 데 도움이 되는 함수가 있으므로 Qucik Sort가 배열을 더 작은 배열로 나누고 getNumberOfStepsToMove 함수를 활용하여 모든 배열 요소를 배치하는 방법을 살펴보겠습니다.

const getNumberOfStepsToMove = (arr, start = 0, end = arr.length - 1) => {
  let numberOfStepsToMove = start;
  // we're picking the first element in the array as the pivot
  const pivot = arr[start];

  // start checking the next elements to the pivot
  for (let i = start + 1; i <= end; i++) {
    // is the current number less than the pivot?
    if (arr[i] < pivot) {
      // yes - so w should increase numberOfStepsToMove
// or the new index of the pivot
      numberOfStepsToMove++;

      // now swap the number at the index of numberOfStepsToMove with the smaller one
      [arr[i], arr[numberOfStepsToMove]] = [arr[numberOfStepsToMove], arr[i]];
    } else {
      // what if it's greater?
      // do nothing -- we need to move on to the next number
      // to check if we have more numbers less that pivot to increase numberOfStepsToMove or not
    }
  }

  // now we know the pivot is at arr[start] and we know that it needs to move numberOfStepsToMove
  // so we swap the numbers to place the pivot number to its correct position
  [arr[start], arr[numberOfStepsToMove]] = [
    arr[numberOfStepsToMove],
    arr[start],
  ];

  return numberOfStepsToMove;
};

빠른 정렬은 재귀를 활용하여 배열을 더 작은 하위 배열로 효율적으로 나누고 피벗과 비교하여 요소를 정렬합니다.

function quickSort(arr, left = 0, right = arr.length - 1) {
  // pivotIndex the new index of the pivot in in the array
  // in our array example, at the first call this will be 5, because we are checking 10 as the pivot
  // on the whole array
  let pivotIndex = getNumberOfStepsToMove(arr, left, right);
}

• 알고리즘은 피벗보다 작은 요소가 포함된 왼쪽 하위 배열을 재귀적으로 정렬합니다.
• 하위 배열에 이미 정렬된 요소가 1개 또는 0개 있으면 재귀가 중지됩니다.

이제 배열의 오른쪽에도 동일한 프로세스를 수행해야 합니다.

// examples of the pivot 23 positioned correctly in the array:
[3, 5, 6, 12, 23, 25, 24, 30]
[6, 12, 5, 3, 23, 24, 30, 25]
[3, 6, 5, 12, 23, 30, 25, 24]

이 예에서는 오른쪽이 이미 정렬되어 있지만 알고리즘은 이를 알지 못하므로 그렇지 않았다면 정렬되었을 것입니다.

위 내용은 빠른 정렬 알고리즘 학습의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!