| English | 의미 |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | 정렬 |
| selection sort/sɪˈlekʃn sɔːt/ | 선택 정렬 |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | 삽입 정렬 |
| in place/ɪn pleɪs/ | 온디emand(in place) |
정렬하기
- 정렬은 요소를 순서에 맞춰 재배열합니다(예: 작음에서 큼으로).
- AP 과정에서는 두 가지 간단한 정렬을 다룹니다: **선택 정렬(selection sort)**과 **삽입 정렬(insertion sort)**입니다.
- 둘 다 중첩 루프를 사용하며 요소를 스왑하거나 밀어 넣어 제자리에 배치합니다.
- 먼저 정렬하는 것이 이후 빠른 이진 검색 사용을 가능하게 합니다.
선택 정렬
- 남은 요소 중 가장 작은 것을 찾아 앞으로 이동(스왑) 시킨다.
- 그다음 남은 것들 중 가장 작은 것을 찾아 다음 빈 자리로 이동시키고, 이 과정을 반복한다.
- 배열의 앞쪽은 정렬된 상태로 커지고, 뒤쪽은 정렬되지 않은 상태로 줄어든다.
- 한 번의 패스마다 스왑은 하나씩—but 매 패스마다 나머지 요소를 모두 스캔해야 한다.
삽입 정렬(Insertion Sort)
- 다음 요소를 가져와 이미 정렬된 앞부분에서 제자리로 밀어넣는다(이동).
- 카드 손에 쥐고 정리하는 것과 같다: 새 카드를 제자리에 꽂는 식이다.
- 각 패스마다 정렬된 영역이 하나씩 커진다.
- 데이터가 이미 거의 정렬되어 있을 때 빠르다.
작업량
- 두 정렬 모두 중첩 루프를 사용하므로 최악의 경우 약
n²번의 비교를 수행한다. - 작은 배열에는 괜찮지만 매우 큰 배열에서는 느리다.
- 인플레이스(in-place) 로 정렬된다—별도의 두 번째 배열이 필요 없다.
- 시험에서는 단순히 이름을 외우는 것이 아니라 추적(trace) 하도록 요구한다.
선택 정렬은 남은 최소 요소를 스왑하여 앞으로 보내고, 삽입 정렬은 새 요소를 정렬된 부분으로 밀어넣는다—혼동하지 말라. 둘 다 중첩 루프 기반, 인플레이스, O(n²) 정렬이다. 단계별로 추적trace하며(AP 시험은 각 패스 후 배열 상태를 묻음), 이름만 외우지 마라.
[3, 1, 2]에 대한 선택 정렬:
- 1패스: 최소값은
1; 스왑 →[1, 3, 2]. - 2패스: ⟨
[3, 2]⟩의 최소값은2; 스왑 →[1, 2, 3]. - 정렬 완료—앞부분이 패스마다 하나씩 커졌다.
정렬(sorting) 은 요소를 순서대로 배치하는 것이다. 선택 정렬은 남은 최소 요소를 반복해 스왑하여 앞으로 보내고, 삽입 정렬은 새 요소를 정렬된 부분으로 밀어넣는다. 둘 다 중첩 루프, 인플레이스, O(n²) 정렬이다. 이후 빠른 이진 검색(binary search) 을 위해 정렬이 필수적이다.
정렬 과정 따라가기
각 pass마다 하나 이상의 요소를 순서대로 배치합니다.
선택 정렬은 ...을 통해 작동합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
선택 정렬은 최소값을 선택하여 앞으로 밀어냅니다.
삽입 정렬은 ...을 통해 작동합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
삽입 정렬은 각 요소를 제자리인 정렬된 위치에 삽입합니다.
최악의 경우, 두 정렬 모두 약 ...의 연산을 수행합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
중첩 루프는 O(n²)의 복잡도를 가집니다.
선택 정렬과 삽입 정렬 모두 인플레이스(in-place)로 작동합니다(보조 배열 불필요).
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
동일한 배열을 재배열합니다.
[3, 1, 2]에 대한 선택 정렬의 pass 순서를 정리하십시오.
난이도 3/5 · 200 코인 + 오늘 첫 완료 시 소액 보너스
맨 앞부분이 정렬되어 커지고, 각 pass마다 요소 하나씩 추가됩니다.
먼저 정렬하는 것이 유용한 이유는 나중에 ...을 사용할 수 있기 때문입니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
이진 검색은 정렬된 데이터가 필요합니다.