정렬
- 원소들을 순서대로 배열하는 것이다.
- 크기가 작은 순으로 정렬하기도 하고, 크기가 큰 순으로 정렬하기도 한다.
기본 정렬
선택 정렬
- 배열에서 가장 큰 원소를 찾아 배열의 맨 끝자리 원소 A[n-1]과 자리를 바꾼다.
- 그러면 방금 맨 끝 자리로 옮긴 원소(가장 큰 원소)는 자기 자리를 찾았으므로 정렬이 끝날 때 까지 자기 자리를 지킨다.
- 이제 가장 오른쪽에 자리 잡은 원소에 관해서는 정렬이 끝난 것으로 간주되어 이 원소를 제외한 나머지 원소들을 대상으로 같은 작업을 반복한다.
버블 정렬
- 선택정렬처럼 유사한 아이디어에 기반하지만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다.
삽입 정렬
- 선택 정렬, 버블 정렬과 정반대로 착상한 정렬이다.
- 선택 정렬과 버블 정렬은 '정렬되지 않은' 배열의 크기를 n부터 시작하여 하나씩 줄인다.
- 삽입 정렬은 '정렬된 배열'의 크기를 1에서 시작하여 하나씩 늘린다.
- 핵심 작업은 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개의 배열을 만드는 과정이다.
고급 정렬
병합 정렬
- 먼저 입력을 반으로 나눈다.
- 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다.
- 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다.
- 여기서 전반부를 정렬할 때도 역시 반으로 나눈다면 정렬해서 병합한다.
- 요약하자면, 병합 정렬은 원래 크기를 반으로 나눈 문제를 2개 푼 다음, 이들을 병합하는 작업을 재귀적으로 반복하는 것이다.
퀵 정렬
- 병합 정렬은 먼저 재귀적으로 작은 문제를 해결한 다음 후처리를 하는 데 반해
- 퀵 정렬은 선행작업을 한 다음 재귀적으로 작은 문제를 해결하면서 바로 끝난다.
- 기준 원소를 하나 잡아 기준 원소보다 작은 원소와 큰 원소 그룹으로 나누어 기준 원소의 좌우로 분할한 다음 각각을 정렬하는 방법이다.
힙 정렬
- 힙 자료구조를 통해서 정렬한다는 점이 색다르다.
- 앞선 8장에서 힙을 만든 다음 원소를 하나씩 제거하면서 percolateDown()으로 수선해주면서 하나씩 빼주면서 차례대로 저장하면 정렬이 된다.
셸 정렬
- 평균적으로 시간이 들고, 가장 운이 좋은 경우, 시간이 든다.
- 이미 정렬되어 있거나 거의 정렬되어 있다면 삽입 정렬의 시간은 이 된다.
특수 정렬
계수 정렬
- 정렬하고자 하는 원소들의 값이 ~의 범위에 있는 정수인 경우에 사용할 수 있다.
- 예를 들어, 배열 A[0...n-1]에 있는 원소들의 값이 0~2n, -n~3n등의 범위에 있는 정수인 경우이다.
기수 정렬
- 원소들이 모두 상수 k개 이하의 자릿수를 가진 자연수와 같은 특수한 경우에(자연수가 아닌 제한된 길이를 가진 알파벡 등도 해당된다.) 사용할 수 있는 방법이며 시간이 소요되는 정렬 알고리즘이다.
버킷 정렬
- 정렬하고자 하는 원소들이 균등 분포할 때를 가정한 유용한 정렬 알고리즘이다.
- 균등 분포는 데이터가 전 영역에 걸쳐 고루 존재하는 분포를 의미한다.
정렬의 구현
public class Sorting {
int A[];
public Sorting(int B[]) {
A = B;
}
// 선택 정렬
public void selectionSort() {
int k; int tmp
for(int last = A.length -1; last >= 1; last--) {
k = theLasrgest(last); //A[0...last]중 가장 큰수 찾기
tmp = A[k];
A[k] = A[last];
A[last] = tmp;
}
}
private int theLargest(int last) {
// A[0...last]에서 가장 큰 수의 인덱스를 리턴한다.
int largets = 0;
for (int i = 0; i <= last; i++)
if(A[i] > A[largest]) largest = i;
return larges;
}
// 버블 정렬
public void bubbleSort() {
int tmp = 0;
boolean swapped;
for (int last = A.length-1; last >= 2; last--) {
swapped = false;
for (int i = 0; i <= last-1; i++) {
if (A[i] > A[i+1]) {
tmp = A[i];
A[i] = A[i+1];
A[i+1] = tmp;
swapped = true;
}
if(swapped = false)
break;
}
}
tmp = tmp;
}
// 삽입 정렬
public void insertionSort() {
for(int i = 1; i <= A.length-1; i++) {
int loc = i-1;
int newItem = A[i];
while (loc >= 0 && newItem < A[loc]) {
A[loc+1] = A[loc];
loc--;
}
A[loc+1] = newItem;
}
}
//병합 정렬
public void mergeSort() {
int[] B = new int[A.length];
mSort(0, A.length-1, B);
}
private void mSort(int p, int r, int[] B) {
if ( p < r ) {
int q = (p+r)/2;
mSort(p, q, B);
mSort(q+1, r, B);
merge(p, q, r, B);
}
}
private void merge(int p, int q, int r, int[]B) {
int i = p;
int j = q+1;
int t = 0;
while (i <= 1 && j <= r) {
if(A[i] <= A[j]) B[t++] = A[i++];
else B[t++] = A[j++];
}
while (i <= q) // 왼쪽 부분 배열이 남은 경우
B[t++] = A[i++];
while (j <= r) // 오른쪽 부분 배열이 남은 경우
B[t++] = A[j++];
i = p;
t = 0;
while (i <= r) // 결과를 A[p...r]에 저장
A[i++] = B[t++];
}
// 퀵 정렬
public void quickSort() {
qSort(0, A.length-1);
}
private void qSort(int p, int r) {
if(p < r) {
int q = partition(p, r);
qSort(p, q-1);
qSort(q+1, r);
}
}
private int partition(int p, int r) {
int x = A[r];
int i = p-1;
int tmp;
for (int j = p; j <= r-1; j++) {
if(A[j] <= x) {
i++;
tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
tmp = A[i+1];
A[i+1] = A[r];
A[r] = tmp;
return i+1;
}
//힙 정렬
public void heapSort() {
buildHeap();
int tmp;
for (int i = A.length-1; i>=1; i--) {
tmp = A[0];
A[0] = A[1];
A[i] = tmp;
percolateDown(0, i-1);
}
}
public void buildHeap() {
if(A.length >= 2) {
for(int i = (A.length-2)/2 ; i>= 0 ; i--) {
percolateDown(i, A.length-1);
}
}
}
public void percolateDown(int i) {
// A[0...numItems-1]에서 A[i]를 루트로 스며내리기
int child = (2*i)+1; //왼쪽 자식
int rightchild = (2*i)+2; //오른쪽 자식
if(child<=numItems-1) {
if(rightchild <= numItems-1 && A[child].compareTo(A[rightchild]) < 0) {
child = rightchild; // 더 큰자식의 인덱스
}
if(A[i].compareTo(A[child])<0) {
E temp = A[i];
A[i] = A[child];
A[child] = temp;
percolateDown(child);
}
}
}
// 셸 정렬
public void shellSort() {
for(int h = A.length/7; h>5; h = h/5-1)
for(int k = 0; k <= h-1; k++)
stepInsertionSort(k, h);
stepInsertionSort(0, 1);
}
void steopInsertionSort(int k, int h) {
int j, insItem;
for (int i = k+h; i<= A.length-1; i += h) {
insItem = A[i];
for (j=i-h; j>=0 && A[j] > insItem; j -= h)
A[j+h] = A[j];
A[j+h] = insItem;
}
}
// 계수 정렬
public int[] countingSort(int k) { // A[0...n-1] bewlong to integers 0~k-1
int[] cnt = new int[K];
for(int i = 0; int < K; i++)
cnt[i] = 0;
for(int i = 0; i < A.length; i++)
cnt[A[i]]++;
cnt[0]--; // A[0]부터 시작하므로 조정
for(int i = 1; i <K; i++)
cnt[i] += cnt[i-1];
int[] B = new int[A.length];
for(int j = A.length-1; j>=0; j--) { //stable sorting을 만들기 위해 역순으로
B[cnt[A[j]]] = A[j];
cnt[A[j]]--;
}
return B
}
// 기수 정렬
pubic void radixSort() { //A[0...n-1]은 최대 numDigits 자릿수의 양의 정수
int[] cnt = new int[10], start = new int[10];
int[] B = new int[A.length];
innt max = -1;
for (int i = 0; i< A.length; i++) {
if(A[i] > max) max = A[i]
}
int numDigits = (int)Math.log10(max) + 1; //최대 자릿수 계산
for (int digit = 1; digit <= numDigits; digit++)
for(int d= 0; d <= 9; d++)
cnt[d] = 0;
for(int i = 0; i < A.length; i++)
cnt[(int)(A[i]/Math.pow(10, digit-1)) % 10]++;
start[0] = 0;
for(int d = 1; d <= 9; d++)
start[d] = start[d-1] + cnt[d-1];
for(int i = 0; i < A.length; i++)
B[start[(int)(A[i]/Math.pow(10, digit-1) % 10]++] = A[i];
for(int i = 0l i< A.length; i++)
A[i] = B[i];
}
// 버킷 정렬
public void bucketSort() {
// A[0...]: 음이 아닌 정수 범위에서 균등 분포 배열
intLinkedList B[];
int numLists = A.length;
B = new intLinkedList[numLists]
for (int i = 0; i < numLists; i++)
B[i] = new intLinkedList();
int max;
if(A[0] < A[1]) max = 1;
else max = 0;
for (int i = 2; i < A.length; i++)
if(A[max] < A[i]) max = i;
int band = A[max] + 1;
int bucketId;
for (int i = 0; i < A.length; i++) {
bucketId = (int)((float)(A[i]/band)*numLists);
B[bucketId].add(0, A[i]);
}
int finger = 0, p, r = -1;
for (int i = 0; i < numLists; i++) {
for (int j = 0; j < B[i].len(); j++)
A[finger++] = B[i].getNode(j).item;
p = r+1;
r = finger - 1;
rangeInsertionSort(p, r);
}
}
private void rangeInsertionSort(int p, int r) {
for(int i = p+1; i <= r; i++) {
int loc = i-1;
int x = A[i];
while (loc >= p&& x < A[loc]) {
A[loc+1] = A[loc];
loc--;
}
A[loc+1] = x;
}
}
}
천방지축 개발자