[[분류:정보]] ==개요== 이 문서는 '쉽게 배우는 알고리즘'이라는 책에 기반하여 작성되었다. 어떤 항목들을 정렬하는 알고리즘으로, 매우 다양한 방법과 시간복잡도를 가진다. 배열뿐만 아니라 힙과 같은 트리 구조 등을 사용할 수 있다. 분석에 관해서는 [[시간 복잡도]] 문서 참고. ==기초적인 정렬 알고리즘== ===선택 정렬(Selection Sort)=== 가장 작은(또는 큰) 원소를 찾아 맨 앞(또는 뒤)의 원소와 교환하는 과정을 반복하여 전체를 정렬하는 방식이다. 본 문서에서는 가장 큰 원소를 찾는 것을 기준으로 서술한다. ====의사 코드(간이화)==== 선택 정렬의 의미를 간단히 서술한 코드이다. {{{#!syntax java selectionSort(A[], n): for last ← n-1 downto 1 A[0…last] 중 가장 큰 수 A[k]를 찾는다. A[k] ↔ A[last] }}} ====의사 코드==== 의사코드 1에서 큰 수를 찾고, 두 수를 교환하는 과정을 엄밀하게 서술한 코드이다. {{{#!syntax java selectionSort(A[], n): for last ← n-1 downto 1 k ← theLargest(A, last) tmp ← A[k]; A[k] ← A[last]; A[last] ← tmp theLargest(A[], last): largest ← 0 for i ← 1 to last if (A[i] > A[largest]) largest ← i return largest }}} ====분석==== 의사코드 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))]이다. ===버블 정렬(Bubble Sort)=== 인접한 두 요소를 반복적으로 비교하고, 순서가 맞지 않으면 서로 자리를 바꾸는 방식으로 데이터를 정렬하는 알고리즘이다. ====의사 코드 (간이화)==== 버블 정렬의 의미를 간단히 서술한 코드이다. {{{#!syntax java bubbleSort(A[], n): for last ← n-1 downto 1 for i ← 0 to last-1 if (A[i] > A[i+1]) A[i] ↔ A[i+1] }}} ====의사 코드==== 이미 정렬이 완료된 상태이면 작업을 종료한다. {{{#!syntax java bubbleSort(A[], n): sorted ← FALSE for last ← n-1 downto 1 sorted ← TRUE for i ← 0 to last-1 if (A[i] > A[i+1]) A[i] ↔ A[i+1] sorted ← FALSE if (sorted) return }}} ====분석==== ===삽입 정렬(Insertion Sort)=== 이미 정렬된 부분 데이터에 새로운 데이터를 하나씩 비교하며 올바른 위치에 '삽입'하여 정렬을 완성하는 알고리즘이다. ====의사 코드 (간이화)==== 삽입 정렬의 의미를 간단히 서술한 코드이다. {{{#!syntax java insertionSort(A[], n): for i ← 1 to n-1 A[0…i]의 적합한 자리에 A[i]를 삽입한다. }}} ====의사 코드 (재귀)==== {{{#!syntax java insertionSort(A[], n): if (n>1) insertionSort(A[], n-1) A[0…n-1]의 적합한 자리에 A[n-1]를 삽입한다. }}} ====의사 코드 ==== 적합한 자리를 찾는 로직을 풀어 서술한 코드이다. {{{#!syntax java insertionSort(A[], n): for i ← 1 to n-1 newItem ← A[i] for (j←i-1; 0 ≤ j and newItem < A[j]; j--) A[j] ← A[j+1] A[j+1] ← newItem }}} ====분석==== ==고급 정렬 알고리즘== ===병합 정렬(Merge Sort)=== ===퀵 정렬(Quick Sort)=== ===힙 정렬(Heap Sort)=== ===셸 정렬(Shell Sort)===
