TOP 25 알고리즘 | Quick Sort

Source: Dev.to

요약

분할 정복을 기반으로 하는 정렬 알고리즘으로, 피벗으로 사용할 요소를 선택하고 제공된 배열을 선택된 피벗을 중심으로 분할하여 피벗을 정렬된 배열에서 올바른 위치에 배치합니다.

코드

function partition(arr, low, high){
  // Escolha o pivô
  let pivot = arr[high];

  // Índice do menor elemento e indica a posição correta do pivô encontrada até agora
  let i = low - 1;

  // Percorre arr[low..high] e move todos os elementos menores para o lado esquerdo.
  // Elementos de low para i são menores após cada iteração
  for (let j = low; j <= high - 1; j++) {
      if (arr[j] < pivot) {
          i++;
          swap(arr, i, j);
      }
  }

  // Move o pivô após elementos menores e retorna sua posição
  swap(arr, i + 1, high);
  return i + 1;
}

function swap(arr, i, j){
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

시간 복잡도

(정보 제공되지 않음)

공간 복잡도

(정보 제공되지 않음)

장점

(정보 제공되지 않음)

단점

• 안정적이지 않음.