정렬

선택 정렬

가장 작은 것부터 꺼내 놓기

카드 여섯 장을 작은 수부터 왼쪽에 늘어놓아 보세요. 한 장씩 보며 가장 작은 카드를 찾아 왼쪽 끝으로 보냅니다.

이미 정렬돼 있어도 훑는 횟수는 같다

• 바퀴마다 — 남은 카드를 끝까지 봐야 가장 작은 카드를 안다. 앞에서 찾아도 끝까지 본다
• 훑는 횟수 — 5 + 4 + 3 + 2 + 1 = 15번. 카드가 n장이면 n(n−1)/2번이다
• 정렬된 카드도 — 맨 앞이 가장 작은지 끝까지 봐야 안다. 위의 「이미 정렬된 카드로 해 보기」로 세어 보면 여전히 15번이다

코드는 후보 하나를 들고 훑는 것이 전부다

다음을 눌러 한 줄씩 넘기며 후보가 바뀌는 걸 보세요. 앞에서부터 확정된 칸이 쌓입니다.

• i — 지금 채우는 칸. 앞 i칸은 이미 자리를 잡았다
• min_idx — 지금까지 본 카드 중 가장 작은 카드의 칸 번호(후보)
• j — 지금 견주는 칸. i + 1 부터 끝까지 간다

선택 정렬에서 틀리는 자리

• 같은 값의 순서가 뒤집힌다 — 먼 칸과 맞바꾼다. 2a 2b 1c 를 정렬하면 1c 2b 2a 가 된다. 안정 정렬이 아니다
• < 대신 <= — 같은 값 중 뒤쪽을 후보로 잡는다. 이미 정렬된 1a 1b 2c 가 1b 1a 2c 로 바뀐다
• range(i + 1, n) 대신 range(i, n) — 자기 자신과도 견줘 비교가 15번에서 20번으로 는다. 답은 그대로 맞다

쓸 일은 적지만 이럴 때 나온다

실전에서 정렬이 필요할 때는 sorted() 한 줄이면 됩니다.

다음 장에서는 카드를 한 장씩 알맞은 자리에 끼워 넣는 삽입 정렬을 봅니다.