| r1 ➤ r2 |
| 4 | 이 문서는 '쉽게 배우는 알고리즘'이라는 책에 기반하여 작성되었다. |
| 5 | |
| 6 | 어떤 항목들을 정렬하는 알고리즘으로, 매우 다양한 방법과 시간복잡도를 가진다. 배열뿐만 아니라 힙과 같은 트리 구조 등을 사용할 수 있다. 시간복잡도 문서는 [[시간 복잡도]] 문서 참고. |
| 7 | ==기초적인 정렬 알고리즘== |
| 8 | ===선택 정렬(Selection Sort)=== |
| 9 | 가장 작은(또는 큰) 원소를 찾아 맨 앞(또는 뒤)의 원소와 교환하는 과정을 반복하여 전체를 정렬하는 방식이다. 본 문서에서는 가장 큰 원소를 찾는 것을 기준으로 서술한다. |
| 10 | ====의사 코드 1==== |
| 11 | 선택 정렬의 의미를 간단히 서술한 코드이다. |
| 12 | |
| 13 | {{{#!syntax java |
| 14 | selectionSort(A[], n): |
| 15 | for last ← n-1 downto 1 |
| 16 | A[0…last] 중 가장 큰 수 A[k]를 찾는다. |
| 17 | A[k] ↔ A[last] |
| 18 | }}} |
| 19 | ====의사 코드 2==== |
| 20 | 의사코드 1에서 큰 수를 찾고, 두 수를 교환하는 과정을 엄밀하게 서술한 코드이다. |
| 21 | |
| 22 | {{{#!syntax java |
| 23 | selectionSort(A[], n): |
| 24 | for last ← n-1 downto 1 |
| 25 | k ← theLargest(A, last) |
| 26 | tmp ← A[k]; A[k] ← A[last]; A[last] ← tmp |
| 27 | |
| 28 | theLargest(A[], last): |
| 29 | largest ← 0 |
| 30 | for i ← 1 to last |
| 31 | if (A[i] > A[largest]) |
| 32 | largest ← i |
| 33 | return largest |
| 34 | }}} |
| 35 | ====분석==== |
| 36 | 의사코드 1을 보자. 선택 정렬의 수행 시간은 모든 경우에 [math(\Theta(n^2))]이다. for 루프는 [math(n-1)]번 순환하고, index 교환은 상수 시간이 든다. 큰 수를 찾는 것은 작업은 부분 배열의 크기에 비례한다.[* 크기가 k인 배열에서 가장 큰 수를 찾는 데는 [math(k-1)]번의 비교가 필요하다.] 부분 배열의 크기는 for문에서 n부터 시작하여 2까지 감소한다. 그러므로 비교하는 총 횟수는 [math((n-1)+(n-2)+…+1=\dfrac{n(n+1)}{2})], 즉 [math(\Theta(n^2))]이다. |
| 37 | ===버블 정렬(Bubble Sort)=== |
| 38 | 인접한 두 요소를 반복적으로 비교하고, 순서가 맞지 않으면 서로 자리를 바꾸는 방식으로 데이터를 정렬하는 알고리즘이다. |
| 39 | ====의사 코드 1==== |
| 40 | 버블 정렬의 의미를 간단히 서술한 코드이다. |
| 41 | |
| 42 | {{{#!syntax java |
| 43 | bubbleSort(A[], n): |
| 44 | for last ← n-1 downto 1 |
| 45 | for i ← 0 to last-1 |
| 46 | if (A[i] > A[i+1]) |
| 47 | A[i] ↔ A[i+1] |
| 48 | }}} |
| 49 | ===삽입 정렬(Insertion Sort)=== |
