- 분할 중인 부분
- 피벗
- 비교 중
- 교환됨
- 제자리
퀵 정렬
퀵 정렬은 피벗을 고르고, 더 작은 값은 모두 그 앞으로, 나머지 값은 모두 그 뒤로 옮긴 다음 양쪽을 같은 방식으로 정렬합니다. 분할이 끝날 때마다 피벗은 최종 위치에 놓입니다. 피벗 고르는 방법을 정하고, 원하는 속도로 정렬을 재생하거나 비교를 하나씩 진행하며, 정렬된 목록에서 나쁜 피벗이 왜 퀵 정렬을 느리게 만드는지 확인해 보세요. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 타일에는 비교, 교환, 분할 횟수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하고, 피벗 고르는 방법도 정하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.
작동 원리
- 막대 개수와 시작 순서를 고르세요: 무작위, 거의 정렬됨, 역순, 값 종류 적음. 직접 숫자를 입력해도 됩니다.
- ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
- 피벗 규칙을 고르세요: 마지막 값, 가운데 값, 무작위 값, 세 값의 중앙값. 정렬된 목록에서 하나씩 시험해 보세요.
퀵 정렬의 원리
정렬할 부분에서 값 하나를 피벗으로 골라 끝으로 옮깁니다. 나머지 값을 왼쪽에서 오른쪽으로 살피며, 피벗보다 작은 값은 맨 앞에서부터 늘어나는 왼쪽 부분으로 교환합니다. 그런 다음 피벗을 왼쪽 부분 바로 뒤로 교환합니다. 이제 피벗 앞의 값은 모두 더 작고 뒤에는 더 작은 값이 없으므로, 피벗은 최종 위치에 있습니다. 피벗 앞 부분과 뒤 부분도 같은 방식으로 정렬하며, 모든 부분이 값 하나가 될 때까지 반복합니다.
피벗이 중요한 이유
피벗이 가운데 근처에 놓이면 분할할 때마다 문제가 절반으로 줄고, 비교 횟수는 n log n에 비례해 늘어납니다. 무작위 값 40개라면 약 190번입니다. 피벗이 가장 작거나 가장 큰 값이면 한쪽은 비고 다른 쪽에 나머지가 모두 들어갑니다. 마지막 값을 피벗으로 쓰면 정렬된 목록이나 역순 목록에서 매 단계 이런 일이 생겨, 정렬에 n(n − 1)/2번, 값 40개라면 780번의 비교가 필요합니다. 무작위 피벗이나 처음, 가운데, 마지막 값의 중앙값을 쓰면 실제로는 이를 피할 수 있습니다.
자주 묻는 질문
퀵 정렬은 어떻게 작동하나요?
피벗을 고르고, 작은 값은 피벗 앞에, 나머지는 뒤에 오도록 목록을 분할한 다음, 양쪽을 퀵 정렬로 정렬합니다. 분할이 끝날 때마다 피벗은 최종 위치에 놓입니다.
정렬된 목록에서 퀵 정렬이 느린 이유는 무엇인가요?
첫 값이나 마지막 값을 피벗으로 쓰면, 정렬된 목록에서는 항상 가장 작거나 가장 큰 값이 피벗이 됩니다. 그러면 분할의 한쪽이 비어 분할마다 값이 하나씩만 줄어들고, 정렬에 n(n − 1)/2번의 비교가 필요합니다. 무작위 피벗이나 세 값의 중앙값을 쓰면 실제로는 이 문제가 해결됩니다.
퀵 정렬이 병합 정렬보다 빠른가요?
실제로는 대개 그렇습니다. 제자리에서 정렬하고, 버퍼가 필요 없으며, 안쪽 루프가 매우 단순하기 때문입니다. 평균 비교 횟수는 병합 정렬보다 조금 많고 최악의 경우는 n²인 반면, 병합 정렬은 항상 n log n입니다. introsort 같은 라이브러리 정렬은 퀵 정렬로 시작해 분할이 너무 고르지 않으면 힙 정렬로 바꿉니다.
퀵 정렬은 안정 정렬인가요?
아니요. 분할은 값을 먼 거리로 교환하므로 같은 값의 순서가 바뀔 수 있습니다.
제 숫자가 어딘가로 전송되나요?
아니요. 정렬은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 보관됩니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동