| English | 의미 |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | 버블 정렬 |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | 삽입 정렬 |
| in place/ɪn pleɪs/ | 인플레이스 |
| stable/ˈsteɪbl/ | 안정성 |
의意적으로 느린 정렬算法
- 모든 주요 라이브러리는exam에서 작성할 것을 요구하지 않는 알고리즘으로 정렬합니다. 버블 정렬과 삽입 정렬은 모두 $O(n^2)$이며, 대용량 리스트에서는 어떠한 합당한 정렬算法에도 밀립니다.
- 어쨌든 과목 과정(syllabus)에 포함되어 있으며, 좋은 이유가 있습니다: 손으로 추迹하기 짧 enough而且, 하나를 추迹하는 것이 정렬算法이 배열에 실제로 무엇을 하는지 배우는 방법입니다.
- 삽입 정렬에도 실제적인 이유가 있습니다. 리스트가 작거나 이미 거의 정렬된 상태라면,它是 genuinely 가장 빠른 것이며, 실제 라이브러리는 정확히 그런 경우들을 위해 이를 사용합니다.
- 이 수업은 버블 정렬과 삽입 정렬입니다: 알고리즘, 그들의 행동, 그리고 각각이 승리를 거두는 곳.
버블 정렬
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
swap A[i], A[i + 1]
swapped ← TRUE
ENDIF
NEXT i
IF NOT swapped THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
- 각 패스는 인접한 쌍(adjacent pairs) 을 비교하고 순서가 틀린 경우를 스왑하므로, 남은 최대 값이 끝으로 "부풀어 오릅니다(bubbles)."
- 패스 $k$ 후 마지막 $k$ 요소들은 최종화되었으며, 이것이 내부 루프가 $n - \text{pass}$에서 멈추는 이유입니다.
swapped플래그는 조기에 멈출 수 있게 합니다: 한 전체 패스에서 스왑이 없다면, 리스트는 이미 정렬된 것입니다.
삽입 정렬(Insertion Sort)
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j] // shift right
j ← j - 1
ENDWHILE
A[j + 1] ← key // drop it in
NEXT i
- 앞쪽에 정렬된 부분(sorted section) 을 형성하여 매번 하나씩 커갑니다. 각 새로운 요소는
key로 잠시 빼놓고, 더 큰 요소들은 오른쪽으로 밀어내어 빈 자리를 만들고, 키(key)를放进去합니다. - 대부분의 사람들이 카드 한 장을 정리하는 방식이며,これが exam에서 예상하는 유비유비(analogy)입니다.
왼쪽은 정렬되고, 오른쪽은 건드리지 않으며, 경계선이 오른쪽으로 이동합니다
정렬 알고리즘
인접한 요소를 비교하고 필요할 때交换
버블 정렬을 단계별로 진행해 보십시오: 각 pass에서 가장 큰 값이 끝까지 떠오릅니다.
버블 정렬은 다음과 같이 작동합니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
각 pass마다 인접 쌍을交換하여 가장 큰 요소를 끝까지 '부풀려(bubbling)' 올립니다.
버블 정렬의 평균/최악의 시간 복잡도는:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
n개 요소에 대한 중첩된 두 루프는 O(n²)을 줍니다; 최상의 경우(이미 정렬됨)는 초기 종료로 O(n)입니다.
worked example: 한 패스 추迹
- 5, 3, 8, 1에 대한 버블 정렬의 첫 번째 패스를 추迹(trace)하세요.
- 5와 3 비교: 순서 틀림, 스왑하여 3, 5, 8, 1. 5와 8 비교: 순서 맞음, 스왑 없음. 8과 1 비교: 스왗하여 3, 5, 1, 8.
- 한 패스 후 최대 값인 8이 최종 위치에 배치되었고, 이제부터 각 패스당 하나의 추가 비교는 생략할 수 있습니다.
- *이제 3, 5, 8, 1에 대한 삽입 정렬의 세 번째 단계를 추迹하세요. 키는 1입니다. 8, 5, 3을 각각 한 자리씩 오른쪽으로 밀어내고, 1을 맨 앞에 배치: 1, 3, 5, 8. 모든 단계 후 배열을 보여주세요;那里就是得分点。
삽입 정렬은 다음을 통해 정렬된 결과를 만듭니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
왼쪽에서 정렬된 접두사전을 성장시키며, 더 큰 요소들을 오른쪽으로 밀어내어 각 키를 제자리에 놓습니다.
삽입 정렬은 새 요소를 어떻게 배치합니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
키를 temporarily 빼놓고 밀어내는 것은 버블 정렬의 반복적인 인접交換과 구별되는 특징입니다.
성능
| 버블 | 삽입 | |
|---|---|---|
| 최선(best case) | $O(n)$, 스왑 없는 한 패스 | $O(n)$, 이미 정렬되어 있어 이동(shift) 없음 |
| 평균 및最差 | $O(n^2)$ | $O(n^2)$ |
| 추가 메모리 | $O(1)$, in place | $O(1)$, in place |
| 안정성(stable) | 예 | 예, 안정적(stable) |
- In place은 상수 수준의 추가 메모리만 필요하며 배열 자체 내에서 정렬함을 의미합니다. Stable은 두 등가 값이 원래의 상대적 순서를 유지함을 의미하며, 이는 리스트가 다른 필드에 의해 이미 정렬된 경우에 중요합니다.
- 둘 다 이미 정렬된 데이터에서 $O(n)$에 도달하지만, 버블 정렬이
swapped플래그를 가질 때만 가능합니다.如果没有它，它总是执行所有passes。
5, 3, 8, 1에 대한 버블 정렬 첫 pass 후 배열은 무엇입니까? 네 숫자를 쉼표로 구분하여 쓰십시오.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
5와 3이交換되고, 5와 8은交换되지 않으며, 8과 1이交換됩니다. 가장 큰 값이 끝에 도달했으므로 다음 pass는 비교 횟수가 하나 줄어듭니다.
worked example: 어떤 정렬算法, 그리고 왜
- 200,000레코드의 리스트를 처음부터 정렬해야 합니다. 둘 다 아닙니다: 둘 다 $O(n^2)$이므로, 병합 정렬이나 퀵 정렬의 $O(n \log n)$이 필요합니다. 선택하지 말고这样说即可。
- *10,000개의 정렬된 리스트末尾に新增5个记录，必须再次排序。插入排序:数据几乎已排序，因此每个新键只移动短距离，趋近于$O(n)$。
- 교수용 예제로 손으로 종이에 추迹해야 합니다. 버블 정렬: 따라가기 가장 쉬우며，这就是它唯一剩下的用途。
- 일반적인 선호도가 아닌 데이터 상태와 크기에서 근거를 제시하세요.
각 정렬 개념을 그 의미를 매칭하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
버블交換는 이웃, 삽입은 정렬된 접두사전 성장; 둘 다 최악의 경우 O(n²); 안정성은 동일한 키의 순서를 의미합니다.
삽입 정렬은 작거나 거의 정렬된 배열에서 O(n)에 가깝게 작동합니다. 왜냐하면 밀어야 하는 요소가 적기 때문입니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
거의 정렬된 데이터에서는 새 항목이 이미 거의 제자리에 있으므로, 삽입 정렬이 작은 입력에서 복잡한 정렬보다 우위임을 알 수 있습니다.
버블 정렬과 삽입 정렬 모두에 맞는 설명은 무엇입니까? 적용되는 모든 것을 선택하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
큰 무작위 목록에서는 O(n log n) 정렬이 압도적으로 승리합니다. 이를 말하는 것이 정답이며, 두 가지 중 덜 나쁜 것을 고르는 것이 아닙니다.
왜 한 패스가 전부가 아님
- 두 정렬算法 모두 반복되는 패스를 수행하며，exam通过区分one pass achieves和when they stop来区分它们。
- 버블 정렬 패스는 인접한 쌍을 비교하고 스왑하므로，one pass carries the largest remaining item to its final place.整个排序需要$n - 1$ passes。
- 삽입 정렬 패스는 다음 항목을 가져와 이미 정렬된 부분에 다시 넣으므로，after $k$ passes the first $k$ items are sorted among themselves but not yet in final position.
- 버블 정렬은 플래그(flag) 로 개선할 수 있습니다:如果一个pass没有做任何swaps，列表已经排序好了，算法停止。在近乎排序的数据上，这使它变成一次pass。
- 플래그가 없으면 최악의 경우 둘 다 $n^2$이 되므로, 큰 파일에서는 부적절한 선택이며 따라서 고사 문제에서는 작은 파일을 묻는 것입니다.
10,000레코드 정렬 목록의末尾에 5개의 새 레코드가 추가되었습니다. 재정렬에 적합한 정렬법은 무엇입니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
거의 정렬된 데이터는 삽입 정렬의 최상향 경우(O(n)에 수렴)를 정확히 나타냅니다. 실제 라이브러리들은 이러한 이유로 이를 사용하도록 전환합니다.
각 정렬 알고리즘이 한 번의 pass에서 달성하는 결과를 매칭하세요.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
이 차이가 바로 추적(trace) 문제에서 실제로 검증하는 내용입니다. 버블 정렬의 플래그 또한 거의 정렬된 데이터에서 조기에 종료되게 하여, 이는 삽입 정렬이 본래 잘 처리할 수 있는 상황입니다.
놓칠 수 있는 점
- 버블 정렬은 인접한 쌍을 비교합니다。比较元素与所有其他元素的回答是在描述不同的算法。
- 내부 루프는 배열의 끝이 이미 고정되어 있으므로 각 passes마다 길이가 짧아집니다. 그 이유를 설명하십시오.
- 삽입 정렬은 공백을 만들기 위해 요소를 오른쪽으로 밀어내며, 반복적으로 스왑하지 않습니다. 이 차이가 바로 이 알고리즘의 핵심입니다.
- 두算法 모두 평균 및 최악의 경우 $O(n^2)$이며, 최상의 경우 $O(n)$입니다. 해당 순서를 가진 사례를 제시하십시오.
이해했습니다
- 버블 정렬: 인접한 쌍을 반복적으로 비교하고 스왑하며, 가장 큰 요소가 끝으로 이동하고, 각 pass마다 내부 루프가 짧아지며, 조기 종료를 위한
swapped플래그가 있습니다. - 삽입 정렬: 앞쪽에서 정렬된 영역을 확장하며, 각 키를 잠시 제외해 두고, 더 큰 요소들을 오른쪽으로 밀어내어 키를 공백에 넣습니다.
- 둘 다 평균 및 최악의 경우 $O(n^2)$, 최상의 경우 $O(n)$이며, **in place(재배치)**이고 **안정적(stable)**입니다.
- 삽입 정렬은 작거나 거의 정렬된 목록에서 진정으로 우월합니다. 하지만 크고 무작위로 정렬되지 않은 목록에서는 어느 것이나 적절한 답이 아닙니다.