비교
교환
패스

  • 비교 중
  • 현재 최솟값
  • 교환됨
  • 제자리

선택 정렬 자세히 알아보기

선택 정렬

선택 정렬은 정렬된 목록을 앞에서부터 만들어 갑니다. 각 패스는 아직 정렬되지 않은 값을 훑으면서 가장 작은 값을 기억해 두었다가, 정렬되지 않은 첫 자리로 교환합니다. 원하는 속도로 재생하거나 비교를 하나씩 진행하면서 비교, 교환, 패스 횟수를 확인하세요. ‘재생’을 눌러 정렬을 보거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 타일에는 비교, 교환, 패스 횟수가 표시됩니다. 막대 개수와 시작 순서를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 막대 개수와 시작 순서를 고르세요: 무작위, 거의 정렬됨, 역순, 값 종류 적음. 직접 숫자를 입력해도 됩니다.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 정렬의 원하는 지점으로 이동합니다.
  3. 탐색이 진행되면서 현재 최솟값이 바뀌는 모습과, 각 패스 끝에 그 값을 제자리로 보내는 교환을 지켜보세요.

선택 정렬의 원리

목록의 모든 값을 보고 가장 작은 값을 기억합니다. 그 값을 첫 번째 값과 교환하면 첫 자리가 확정됩니다. 그런 다음 한 칸 뒤에서 시작해 나머지 목록에 같은 일을 반복합니다. n − 1번의 패스가 끝나면 모든 값이 제자리에 놓이며, 마지막 값은 저절로 제자리에 남습니다.

비교는 많고 교환은 적다

탐색은 중간에 멈추지 않습니다. 남은 값을 모두 봐야만 어느 값이 가장 작은지 확신할 수 있기 때문입니다. 그래서 선택 정렬은 목록이 정렬되어 있든, 역순이든, 무작위든 n개의 값에 대해 정확히 n(n − 1)/2번 비교합니다. 대신 교환은 패스마다 한 번, 최대 n − 1번뿐입니다. 그래서 값을 옮기는 비용이 두 값을 비교하는 비용보다 훨씬 클 때 괜찮은 선택입니다.

자주 묻는 질문

선택 정렬은 어떻게 동작하나요?

아직 정렬되지 않은 값 중 가장 작은 값을 골라 정렬되지 않은 첫 자리로 교환하는 일을 반복합니다. k번째 패스가 끝나면 처음 k자리에 가장 작은 k개 값이 순서대로 놓입니다.

선택 정렬은 비교와 교환을 몇 번 하나요?

n개의 값에 대해 비교는 항상 n(n − 1)/2번입니다. 값이 10개면 45번, 40개면 780번입니다. 교환은 패스마다 한 번으로 최대 n − 1번이며, 가장 작은 값이 이미 제자리에 있으면 그보다 적습니다.

정렬된 목록이 역순 목록만큼 오래 걸리는 이유는 무엇인가요?

각 패스가 가장 작은 값을 찾았다고 확신하려면 남은 값을 모두 봐야 하기 때문입니다. 버블 정렬이나 삽입 정렬과 달리, 선택 정렬은 비교 결과로 목록이 이미 정렬되었는지 알 수 없습니다.

선택 정렬은 안정 정렬인가요?

일반적인 형태로는 아닙니다. 교환 때문에 어떤 값이 같은 값을 건너뛸 수 있습니다. 2, 2, 1에서는 첫 번째 2가 1과 교환되어 두 번째 2 뒤로 갑니다. 교환 대신 값을 밀어 옮기는 방식은 안정적이지만 이동이 더 많습니다.

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

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

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

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

편집기로 이동