우승
연산
완료

  • 비교 중
  • 표시(최솟값, 피벗, 키)
  • 교환 또는 이동됨
  • 제자리
순위 정렬 비교 또는 읽기 교환 또는 이동 연산

정렬 알고리즘 자세히 알아보기

정렬 대결

가장 빠른 정렬 알고리즘은 무엇일까요? 목록에 따라 다릅니다. 정렬 대결은 여덟 가지 정렬 알고리즘을 같은 목록으로 한꺼번에 실행하고, 각각 레인 하나씩 배정해 비교, 읽기, 교환, 이동을 모두 연산 한 번으로 셉니다. 레인은 횟수가 늘어나는 만큼 나아가므로, 효율적인 정렬이 끝나는 동안 느린 정렬은 아직 교환 중인 모습을 볼 수 있고, 목록이 거의 정렬되었거나 역순일 때 순위가 어떻게 바뀌는지도 볼 수 있습니다. ‘재생’을 눌러 여덟 가지 정렬 알고리즘이 같은 목록으로 경주하는 모습을 보거나, ‘단계’와 ‘뒤로’로 연산을 하나씩 진행하세요. 슬라이더를 끌면 원하는 곳으로 이동합니다. 비교, 읽기, 교환, 이동은 각각 연산 한 번으로 세며, 각 레인은 자기 연산 횟수가 늘어나는 만큼 나아가므로 연산이 가장 적은 정렬이 먼저 끝납니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 막대 개수와 시작 순서를 고르세요: 무작위, 거의 정렬됨, 역순, 값 종류 적음. 직접 숫자를 입력해도 됩니다.
  2. ‘재생’을 누르고 여덟 레인을 지켜보세요. ‘단계’와 ‘뒤로’는 연산을 하나씩 이동하고, 슬라이더로 경주의 원하는 지점으로 이동합니다.
  3. 결과 표를 비교한 뒤, 거의 정렬된 목록과 역순 목록도 시도해 순위가 어떻게 바뀌는지 보세요.

경주 방식

여덟 가지 정렬은 같은 목록을 받습니다. 두 값의 비교, 기수 정렬과 계수 정렬이 읽는 자릿수나 값, 그리고 교환이나 이동은 각각 연산 한 번으로 셉니다. 경주의 매 순간, 각 레인은 해당 정렬이 그만큼의 연산으로 어디까지 진행했는지 보여 줍니다. 연산이 적게 필요한 정렬일수록 먼저 끝에 도착합니다. 결과 표에는 정렬마다 비교 횟수, 교환 또는 이동 횟수, 합계가 나옵니다.

결과가 보여 주는 것

무작위 값 40개에서 계수 정렬은 약 120번, 기수 정렬은 약 240번, 퀵 정렬은 약 260번, 병합 정렬은 약 380번의 연산이 필요합니다. 그다음은 약 490번인 힙 정렬이고, 선택 정렬과 삽입 정렬은 약 820번, 버블 정렬은 1,100번이 넘습니다. 거의 정렬된 목록에서는 삽입 정렬이 약 50번으로 이기고 버블 정렬이 2위입니다. 역순 목록에서는 버블 정렬과 삽입 정렬 모두 1,560번이 필요합니다. 계수 정렬과 기수 정렬이 자주 이기는 것은 값이 작은 정수이기 때문이며, 다른 데이터에는 아예 쓸 수 없습니다.

자주 묻는 질문

가장 빠른 정렬 알고리즘은 무엇인가요?

데이터에 따라 다릅니다. 작은 정수라면 계수 정렬과 기수 정렬이 연산을 가장 적게 씁니다. 일반 데이터라면 무작위 목록에서는 퀵 정렬과 병합 정렬이, 거의 정렬된 목록에서는 삽입 정렬이 가장 빠릅니다. 버블 정렬과 선택 정렬은 아주 작은 목록이 아니면 느립니다.

무엇이 연산 한 번인가요?

두 값의 비교, 기수 정렬과 계수 정렬이 읽는 자릿수나 값 하나, 값 하나의 교환이나 이동이 각각 한 번입니다. 간단한 모델이며, 실제 실행 시간은 메모리 접근과 각 연산의 비용에도 좌우됩니다.

계수 정렬과 기수 정렬은 왜 자주 이기나요?

값을 비교하지 않기 때문입니다. 값이 작은 정수라는 점을 이용하므로, 작업량이 n log n이 아니라 n에 값의 범위를 더한 만큼 늘어납니다. 작은 정수로 이루어지지 않은 데이터에는 쓸 수 없습니다.

거의 정렬된 목록에서는 왜 삽입 정렬이 이기나요?

삽입 정렬의 작업량은 값의 개수에 순서가 뒤바뀐 쌍의 개수를 더한 것이기 때문입니다. 거의 정렬된 목록에는 그런 쌍이 매우 적어서 각 값이 한두 칸만 움직입니다.

입력한 숫자가 어딘가로 전송되나요?

아니요. 경주는 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동