[TIL] 알고리즘&자료구조 _ 퀵 정렬

'퀵 정렬'이란?

분할 정복(Divide and Conquer) 알고리즘을 기반으로 한다. 이 알고리즘은 평균적으로 매우 빠르게 동작하며 일반적으로 정렬 알고리즘 중에서 가장 빠른 알고리즘 중 하나로 알려져 있다.

자바스크립트로 구현한 퀵 정렬

function quicSort(arr) {
  let answer = arr
  if (arr.length <= 1) return answer

  let pivot = arr[0]
  let left = []
  let rigth = []

  // 피봇값+1 번째부터 시작
  for (let i = 1; i < answer.length; i++) {
    // 값이 피봇값보다 작거나 같으면 왼쪽에
    if (arr[i] <= pivot) left.push(arr[i])
    // 크면 오른쪽에 넣음
    else rigth.push(arr[i])
  }

  // 재귀함수 -> 더 자를수 없을때까지 함수 안에 함수를 돌림
  let leftSort = quicSort(left)
  let rigthSort = quicSort(rigth)

  // 전개구문으로 한 배열안에 넣어 리턴
  answer = [...leftSort, pivot, ...rigthSort]
  return answer
}

1. 퀵 정렬이 언제나 옳을까?

평균적인 시간복잡도의 경우 O(n log n)이지만, 최악의 경우(이미 정렬된 배열이 주어진 경우 등)에는 O(n^2)의 시간 복잡도를 가질 수 있다.
-> 피봇 선택이 잘못되어 있는 경우 등

2. 주로 사용되는 피봇 선택 전략

1) 첫 번째 원소를 피벗으로 선택 : 이미 정렬된 배열이나 거의 정렬된 배열의 경우에는 성능이 나빠질 수 있음
2) 중간값(median)을 피벗으로 선택: 중간값을 선택하면 배열이 무작위로 섞인 것과 유사한 효과를 얻을 수 있어 최악의 경우 시간 복잡도가 크게 개선될 수 있음 -> 최악의 경우 시간 복잡도 문제 완전한 해결은 안되나 많은 경우에 효과적

3. 정적인 데이터를 처리하기에 좋고 실시간으로 데이터가 업데이트 되는 동적인 데이터의 경우 힙정렬,병합정렬이 더 유용함

4. 하이브리드 퀵 정렬

큰 배열에 대해서만 퀵 정렬 사용: 배열의 크기가 특정 임계값 이상인 경우에만 퀵 정렬을 사용합니다. 퀵 정렬은 평균적으로 매우 빠르게 동작하며 큰 배열에 대해 효과적임.
배열의 크기가 작은 경우(10개 이하 정도) 일반적으로 다른 정렬 알고리즘(삽입정렬 등)을 사용하여 정렬함.
-> 더욱 효율적인 정렬이 가능해짐.

5. 데이터의 안정성(stability)을 보장하지 않음.

퀵 정렬은 두 원소의 크기만을 비교하기 때문에 동일한 키값을 가진 원소들의 상대적인 순서가 보존되지 않을 수 있다.
-> 안정성이 중요한 경우에는 안정적인 정렬 알고리즘(예: 병합 정렬, 삽입 정렬)을 사용하는 것이 좋다. 이러한 알고리즘들은 동일한 키값을 가진 원소들의 상대적인 순서를 보존하면서 정렬을 수행하기 때문이다.

오늘 공부한 퀵 정렬에 대해 정리해 보았다.
아직 알고리즘, 자료구조 등 배우고 있는 단계라 모르는 개념도 있고 이해는 되는데 와닿지 않는 내용도 있다.
하나하나 꾸준히 정복해 봐야지!!

혹시 잘못된 정보가 있거나 수정할 사항이 있다면 언제든 댓글 환영합니다!