Sorting: bubble, selection, and insertion · 정렬: 버블, 선택, 삽입
Putting an array in order
- Sorting rearranges an array so the items go from smallest to largest.
- We sort in place: we move items around inside the same array, with no return value.
- Three classic methods do this: bubble, insertion, and selection sort.
배열을 순서대로 만들기
- 정렬은 배열의 항목들이 작은 값에서 큰 값으로的顺序로 가도록 배열을 재배열하는 것입니다.
- 우리는 인플레이스로 정렬합니다: 동일한 배열 내부에서 항목들을 이동하며, 반환값이 없습니다.
- 이를 수행하는 세 가지 고전적인 방법이 있습니다: 버블, 삽입, 그리고 선택 정렬입니다.
Swapping two elements
- Every sort needs to swap two items. Save one in a temporary, then overwrite.
int t = a[i]; a[i] = a[j]; a[j] = t;exchanges positionsiandj.- Forgetting the temporary loses one of the values — always keep it.
두 요소 swapping
- 모든 정렬 알고리즘은 두 항목을 swap해야 합니다.其中一个를 임시 변수에 저장한 후, 다른 하나를 덮어씌우십시오.
int t = a[i]; a[i] = a[j]; a[j] = t;는 위치i과j를交換합니다.- 임시 변수를 잊어버리면 하나의 값이 사라집니다 — 반드시 유지하십시오.
Bubble sort
- Go through the array and compare each pair of neighbours:
a[j]anda[j + 1]. - If they are in the wrong order, swap them. The biggest value "bubbles" to the end.
- Repeat the passes until the whole array is in order.
버블 정렬
- 배열을 순회하며 각 인접한 쌍을 비교하십시오:
a[j]와a[j + 1]. - 순서가 틀려 있다면 swap하십시오. 가장 큰 값이 "버블"처럼 끝으로 이동합니다.
- 전체 배열이 순서대로 될 때까지 passes를 반복하십시오.
Insertion sort
- Treat the left part of the array as already sorted, and grow it one item at a time.
- Take the next item as a key, shift bigger sorted items to the right, then drop the key into the gap.
- This is how many people sort playing cards in their hand.
삽입 정렬
- 배열의 왼쪽 부분을 이미 정렬된 것으로 간주하고, 한 번에 한 항목씩 확장하십시오.
- 다음 항목을 **키(key)**로 취하고, 더 큰 정렬된 항목들은 오른쪽으로 밀어낸 뒤, 키를 빈 공간에 떨어뜨리십시오.
- 이는 사람들이 손안에서 카드 정리를 할 때 사용하는 방법입니다.
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
Common mistakes
- Bubble, selection and insertion sort are all O(n²).
- Trace a small array by hand to check your sort.
흔한 실수
- 버블, 선택, 삽입 정렬은 모두 O(n²)입니다.
- 정렬이 올바른지 확인하기 위해 작은 배열을 손으로 추적해 보십시오.
Now you try
- Sort ascending (smallest first), in place, with no return value.
- The checker tries several arrays, including negatives and an already-sorted one.
- Do not write a
main— the checker provides one.
이제 직접 해보기
- 오름차순(작은 값 먼저), 인플레이스로, 반환값 없이 정렬하십시오.
- 체크러는 음수 및 이미 정렬된 배열 등 여러 배열을 시도합니다.
main을 작성하지 마세요; 검증程序가 제공해 줍니다.
Watch a sort run · 정렬 과정 보기
Bubble / selection / insertion all compare and swap into order. · 버블/선택/삽입 모두 비교 및 스왑을 통해 순서대로 배치합니다.
Complete void swap(int a[], int i, int j) so it exchanges the items at index i and j, in place (no return). Do not write a main. · void swap(int a[], int i, int j)을 완성하여 인덱스 i과 j에 있는 항목을 위치 swaps(인-place)로 교환하도록 하십시오. (반환값 없음). **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do not write a main. · void bubble_sort(int a[], int n)을 완성하여 버블 정렬을 사용하여 배열을 오름차로 정렬하고, 위치 swaps(in-place)로 처리하십시오. **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete void insertion_sort(int a[], int n) so it sorts the array ascending, in place, using insertion sort (take each item as a key and shift bigger items right). Do not write a main. · void insertion_sort(int a[], int n)을 완성하여 삽입 정렬을 사용하여 배열을 오름차로 정렬하고, 위치 swaps(in-place)로 처리하십시오. (각 항목을 키로 설정하고 더 큰 항목들을 오른쪽으로 이동시킴). **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.