Quicksort는 영국의 컴퓨터 과학자 Tony Hoare가 1959년에 개발하여 1961년에 출판한 효율적인 정렬 알고리즘입니다. 이는 정렬할 요소 간의 차이를 측정하는 비교 기반 알고리즘입니다. 이는 요소를 두 개의 하위 그룹으로 나눈 다음 재귀적으로 정렬하는 분할 및 정복 접근 방식을 활용하여 작동합니다.
Quicksort는 선택 정렬과 분할을 조합하여 배열을 정렬합니다. 선택 정렬에서 알고리즘은 배열에서 가장 작은 요소를 찾아 배열의 첫 번째 요소와 바꿉니다. 이렇게 교체하면 가장 작은 요소가 항상 배열의 시작 부분에 있게 됩니다. 그런 다음 분할 단계에서는 현재 요소의 값을 해당 값보다 작은 요소와 큰 요소 사이의 위치로 이동합니다. 이는 먼저 "피벗"이라고 알려진 배열 요소를 선택하여 수행됩니다. 피벗보다 작은 모든 요소는 피벗 앞에 배치되고 피벗보다 큰 모든 요소는 피벗 뒤에 배치됩니다. 이 프로세스는 배열이 정렬될 때까지 새로 생성된 두 하위 그룹에 대해 반복됩니다.
퀵 정렬의 시간 복잡도는 선택한 피벗에 따라 다르지만 대부분의 경우 퀵 정렬의 시간 복잡도는 O(n log n)입니다. 이로 인해 상대적으로 빠른 속도로 인해 퀵 정렬이 선호되는 정렬 알고리즘이 됩니다. 또한 메모리 요구 사항이 낮기 때문에 선호됩니다.
Quicksort는 운영 체제, 데이터베이스, 그래픽 등 컴퓨터 과학의 다양한 영역에서 널리 사용됩니다. 또한 C, Java, Python과 같은 많은 프로그래밍 언어에서 표준 라이브러리의 일부로 자주 사용됩니다.
