JS 알고리즘 10일차 - 퀵 정렬

퀵 정렬이란? 기본적으로 데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식이다. 피벗 포인트라 부르는 단일 요소를 선택하여 수행한다. 어떤 배열에서 어떤 요소를 선택하든 사실상 문제가 되지 않는다. 의사코드 배열이 주어지면 요소를 피벗 포인트로 지정하여 배열 속 요소를 재배치하는 함수를 작성한다. 피벗보다 작은 값은 모두 왼쪽으로 이동하며 피벗보다 큰 값을 모두 오른쪽으로 이동한다. 왼쪽과 오른쪽 안에서는 순서가 중요하지 않다. 헬퍼는 제자리에서 수행해야 한다, 새 배열을 만들면 안되고, 피벗 인덱스를 반환해야 한다. 피벗 선정 퀵 정렬의 실행 시간은 피벗 선택 위치에 따라 달라질 수 있다. 이상적으로는 데이터 집합의 중간값이 되도록 선택해야 한다. 하지만 데이터가 무엇인지, 순서가 어떻게 되어 있는지 모른다면 쉽지 않다. 첫 번째요소 혹은 마지막 요소, 중간, 무작위 요소를 선택한다. 첫 번째 요소를 선택하면 시간 복잡도에 영향을 준다...

원문링크 : JS 알고리즘 10일차 - 퀵 정렬