이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
배열을 순서대로 만들기
- **정렬(Sorting)**은 배열의 요소를 작에서 큰 순서로 재배열하는 것입니다.
- 우리는 인플레이스로 정렬합니다: 동일한 배열 내부에서 항목들을 이동하며, 반환값이 없습니다.
- 이를 수행하는 세 가지 고전적인 방법이 있습니다: 버블, 삽입, 그리고 선택 정렬입니다.
두 요소 swapping
- 모든 정렬 알고리즘은 두 요소를 **교체(swap)**해야 합니다. 먼저 한 요소를 임시 변수에 저장한 후, 다른 값으로 덮어씌우세요.
int t = a[i]; a[i] = a[j]; a[j] = t;이 위치i과j를 교환합니다.- 임시 변수를 잊어버리면 하나의 값이 사라집니다 — 반드시 유지하십시오.
버블 정렬
- 배열을 순회하며 각 인접한 쌍을 비교하십시오:
a[j]와a[j + 1]. - 순서가 틀려 있다면 swap하십시오. 가장 큰 값이 "버블"처럼 끝으로 이동합니다.
- 전체 배열이 순서대로 될 때까지 passes를 반복하십시오.
삽입 정렬
- 배열의 왼쪽 부분을 이미 정렬된 것으로 간주하고, 한 번에 한 항목씩 확장하십시오.
- 다음 항목을 **키(key)**로 취하고, 더 큰 정렬된 항목들은 오른쪽으로 밀어낸 뒤, 키를 빈 공간에 떨어뜨리십시오.
- 이는 사람들이 손안에서 카드 정리를 할 때 사용하는 방법입니다.
English
#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;
}
흔한 실수
- 버블, 선택, 삽입 정렬은 모두 O(n²)입니다.
- 정렬이 올바른지 확인하기 위해 작은 배열을 손으로 추적해 보십시오.
이제 직접 해보기
- 오름차순(작은 값 먼저), 인플레이스로, 반환값 없이 정렬하십시오.
- 체크러는 음수 및 이미 정렬된 배열 등 여러 배열을 시도합니다.
main을 작성하지 마십시오—체크기가 하나 제공합니다.
탐색하기
정렬 과정 보기
버블/선택/삽입 모두 비교 및 스왑을 통해 순서대로 배치합니다.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
void swap(int a[], int i, int j)를 완성하여 인덱스 i와 j에 있는 항목을 위치에서 교환하도록 하십시오(반환 값 없음). main를 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
void bubble_sort(int a[], int n)를 완성하여 버블 정렬을 사용하여 배열을 오름차순으로 위치에서 정렬하도록 하십시오. main를 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 4/5 · 280코인 + 오늘 첫 완료 시 작은 보너스 추가
void insertion_sort(int a[], int n)를 완성하여 삽입 정렬을 사용하여 배열을 오름차순으로 위치에서 정렬하도록 하십시오(각 항목을 키로 설정하고 큰 값을 오른쪽으로 이동함). main를 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.