- 비교 중
- 표시(최솟값, 피벗, 키)
- 교환 또는 이동됨
- 제자리
| 순위 | 정렬 | 비교 또는 읽기 | 교환 또는 이동 | 연산 |
|---|
정렬 대결
가장 빠른 정렬 알고리즘은 무엇일까요? 목록에 따라 다릅니다. 정렬 대결은 여덟 가지 정렬 알고리즘을 같은 목록으로 한꺼번에 실행하고, 각각 레인 하나씩 배정해 비교, 읽기, 교환, 이동을 모두 연산 한 번으로 셉니다. 레인은 횟수가 늘어나는 만큼 나아가므로, 효율적인 정렬이 끝나는 동안 느린 정렬은 아직 교환 중인 모습을 볼 수 있고, 목록이 거의 정렬되었거나 역순일 때 순위가 어떻게 바뀌는지도 볼 수 있습니다. ‘재생’을 눌러 여덟 가지 정렬 알고리즘이 같은 목록으로 경주하는 모습을 보거나, ‘단계’와 ‘뒤로’로 연산을 하나씩 진행하세요. 슬라이더를 끌면 원하는 곳으로 이동합니다. 비교, 읽기, 교환, 이동은 각각 연산 한 번으로 세며, 각 레인은 자기 연산 횟수가 늘어나는 만큼 나아가므로 연산이 가장 적은 정렬이 먼저 끝납니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.
작동 원리
- 막대 개수와 시작 순서를 고르세요: 무작위, 거의 정렬됨, 역순, 값 종류 적음. 직접 숫자를 입력해도 됩니다.
- ‘재생’을 누르고 여덟 레인을 지켜보세요. ‘단계’와 ‘뒤로’는 연산을 하나씩 이동하고, 슬라이더로 경주의 원하는 지점으로 이동합니다.
- 결과 표를 비교한 뒤, 거의 정렬된 목록과 역순 목록도 시도해 순위가 어떻게 바뀌는지 보세요.
경주 방식
여덟 가지 정렬은 같은 목록을 받습니다. 두 값의 비교, 기수 정렬과 계수 정렬이 읽는 자릿수나 값, 그리고 교환이나 이동은 각각 연산 한 번으로 셉니다. 경주의 매 순간, 각 레인은 해당 정렬이 그만큼의 연산으로 어디까지 진행했는지 보여 줍니다. 연산이 적게 필요한 정렬일수록 먼저 끝에 도착합니다. 결과 표에는 정렬마다 비교 횟수, 교환 또는 이동 횟수, 합계가 나옵니다.
결과가 보여 주는 것
무작위 값 40개에서 계수 정렬은 약 120번, 기수 정렬은 약 240번, 퀵 정렬은 약 260번, 병합 정렬은 약 380번의 연산이 필요합니다. 그다음은 약 490번인 힙 정렬이고, 선택 정렬과 삽입 정렬은 약 820번, 버블 정렬은 1,100번이 넘습니다. 거의 정렬된 목록에서는 삽입 정렬이 약 50번으로 이기고 버블 정렬이 2위입니다. 역순 목록에서는 버블 정렬과 삽입 정렬 모두 1,560번이 필요합니다. 계수 정렬과 기수 정렬이 자주 이기는 것은 값이 작은 정수이기 때문이며, 다른 데이터에는 아예 쓸 수 없습니다.
자주 묻는 질문
가장 빠른 정렬 알고리즘은 무엇인가요?
데이터에 따라 다릅니다. 작은 정수라면 계수 정렬과 기수 정렬이 연산을 가장 적게 씁니다. 일반 데이터라면 무작위 목록에서는 퀵 정렬과 병합 정렬이, 거의 정렬된 목록에서는 삽입 정렬이 가장 빠릅니다. 버블 정렬과 선택 정렬은 아주 작은 목록이 아니면 느립니다.
무엇이 연산 한 번인가요?
두 값의 비교, 기수 정렬과 계수 정렬이 읽는 자릿수나 값 하나, 값 하나의 교환이나 이동이 각각 한 번입니다. 간단한 모델이며, 실제 실행 시간은 메모리 접근과 각 연산의 비용에도 좌우됩니다.
계수 정렬과 기수 정렬은 왜 자주 이기나요?
값을 비교하지 않기 때문입니다. 값이 작은 정수라는 점을 이용하므로, 작업량이 n log n이 아니라 n에 값의 범위를 더한 만큼 늘어납니다. 작은 정수로 이루어지지 않은 데이터에는 쓸 수 없습니다.
거의 정렬된 목록에서는 왜 삽입 정렬이 이기나요?
삽입 정렬의 작업량은 값의 개수에 순서가 뒤바뀐 쌍의 개수를 더한 것이기 때문입니다. 거의 정렬된 목록에는 그런 쌍이 매우 적어서 각 값이 한두 칸만 움직입니다.
입력한 숫자가 어딘가로 전송되나요?
아니요. 경주는 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동