Sorting · 정렬
Putting items in order
- Sorting arranges a list into order, usually smallest first.
- The key move is a swap: exchange two items.
- In Python:
a[i], a[j] = a[j], a[i]swaps two list items in one line.
항목 정리하기
- **정렬(Sorting)**은 목록을 정제하여 보통最小的值를 먼저 배치합니다.
- 핵심 동작은 교체(swap): 두 항목의 위치를 바꿉니다.
- Python에서:
a[i], a[j] = a[j], a[i]는 한 줄로 두 목록 항목을 교체합니다.
Bubble sort
- Compare each pair of neighbours; swap them if they are out of order.
- After one full pass, the largest item has "bubbled" to the end.
- Repeat the passes until no swaps are needed.
버블 정렬
- 인접한 두 쌍을 비교하고 순서가 맞지 않으면 교체합니다.
- 한 번의 완전한 pass를 마치면 가장 큰 항목이 "버블"처럼 맨 끝으로 이동합니다.
- 교체가 더 필요 없을 때까지 passes를 반복합니다.
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
Insertion sort
- Treat the left part of the list as already sorted.
- Take the next item and slide it left until it sits in the right place.
- Like sorting playing cards in your hand, one at a time.
삽입 정렬
- 목록의 왼쪽 부분을 이미 정렬된 것으로 간주합니다.
- 다음 항목을 가져와서 올바른 위치에 올 때까지 왼쪽으로 밀어 넣습니다.
- 손에 든 카드-sorting하는 것처럼, 하나씩 처리합니다.
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
Compare them
- Both check roughly
n × npairs, so both are slow on big lists. - Insertion sort is fast when the list is almost sorted already.
- Faster methods exist, but bubble and insertion are easy to understand.
비교하기
- 둘 다 대략
n × n쌍을 비교하므로 큰 목록에서는 모두 느립니다. - 삽입 정렬은 이미 거의 정렬된 목록일 때 빠릅니다.
- 더 빠른 방법들이 있지만, 버블 및 삽입 정렬은 이해하기 쉽습니다.
In Cambridge pseudocode
- Bubble sort with a
tempvariable for the swap.
캐미지아 가위코드에서
- 버블 정렬 시 swap을 위한
temp변수 사용.
FOR i ← 0 TO LENGTH(list) - 2
FOR j ← 0 TO LENGTH(list) - 2 - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
Common mistakes
- Bubble and insertion sort are both O(n²).
- Trace a small list by hand to check your sort works.
흔한 실수
- 버블 정렬과 삽입 정렬 모두 O(n²)입니다.
- 손으로 작은 목록을 추적하여 정렬이 올바르게 작동했는지 확인하세요.
Now you try
- Each task changes the list in place — no need to return it.
- Press Check answer to test your code.
이제 직접 해보기
- 각 작업은 목록을 in place로 변경하므로 반환할 필요가 없습니다.
- Answer 확인 버튼을 눌러 코드를 테스트하세요.
Watch a sort run · 정렬 과정 보기
Sorting repeatedly compares and swaps until everything is in order. · 정렬은 모든 요소가 올바른 순서가 될 때까지 반복적으로 비교하고交换합니다.
Write swap(items, i, j) that exchanges the items at index i and index j in the list. Change the list in place (no return). · swap(items, i, j)을 작성하여列表中의 인덱스 i과 인덱스 j에 있는 요소를交換하세요.列表를 **제자리(in place)**에서 변경하고 반환하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place. · bubble_sort(items)을 작성하여 버블 정렬(bubble sort)을 사용하여列表를 오름차순으로 정렬하세요.列表를 **제자리(in place)**에서 변경합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place. · insertion_sort(items)을 작성하여 삽입 정렬(insertion sort)을 사용하여列表를 오름차순으로 정렬하세요.列表를 **제자리(in place)**에서 변경합니다.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.