06-1 정렬
정렬은이름 , 학번, 키 등 핵심 항목의 의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다.
오름차순 ascending order 내림차순 descending order
정렬 알고리즘의 안정성
안정 된 정렬: 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말합니다.
안정되지 않은 알고리즘은 같은 점수인 경우 반드시 학번 순서대로 정렬되지는 않습니다.
내부정렬과 외부 정렬
정렬 알고리즘도 하나의 배열에서 작업할 수 있는 경우에는 내부 정렬 internal sorting
하나의 배열에서 작업할 수 없는 경우에는 외부 정렬 external sorting
정렬 알고리즘의 핵심 요소
교환 , 선택 ,삽입
06-2 버블 정렬
버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복합니다.
←----------------------------
←----------------------------
static void swap(int[] a,int idx1,int idx2){
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void bubbleSort(int[] a,int n){
for(int i = 0; i< n-1;i++)
for (int j = n-1; j>i ; j--)
if (a[j-1] > a[j])
swap(a, j-1,j);
}
알고리즘 개선
static void bubbleSort(int[] a,int n){
for(int i = 0; i< n-1;i++){
int exchg =0;
for (int j = n-1; j>i ; j--)
if (a[j-1] > a[j]){
swap(a, j-1,j);
exchg++;
}
if(exchg == 0) break;
}
}
알고리즘 개선(2)
static void bubbleSort(int[] a,int n){
int k = 0;
while( k < n-1){
int last = n-1;
for (int j = n-1; j>i ; j--)
if (a[j-1] > a[j]){
swap(a, j-1,j);
last= j;
}
k = last;
}
}
06-3 단순 선택 정렬
가장 작은 요소부터 정렬하는 알고리즘이기 때문에 가장 작은 값의 요소인 1을 선택해 정렬을 시작합니다.
1을 6과 교환합니다.
static void selectoinSort(int[] a, int n){
for(int i = 0; i< n-1; i++){
int min = i; //아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록합니다.
for(int j = i+1; j <n;j++)
if(a[j] < a[min])
min = j;
swap(a,i,min); //아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환합니다.
}
}
06-4 단순 삽입 정렬
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘입니다.
트럼프 카드를 한 줄로 늘어놓을 때 사용하는 방법과 비슷한 알고리즘입니다.
아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입힙니다.
static void insertionSort(int[] a, int n){
for (int i = 1; i <n;i++){
int j ;
int tmp = a[i];
for (j = 1; j>0 && a[j-1] > tmp; j--)
a[j] = a[j-1];
a[j] = tmp;
}
}
06-5 셸 정렬
단순 삽입 정렬 :
장점:정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라집니다.
단점:삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아집니다.
단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알고리즘으로 도널드 셸이 고안했습니다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고 , 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법입니다.
static void shellShort(int[] a, int n){
for (int h = n/2; h >0; h/=2)
for(int i = h; i<n;i++){
int j;
int tmp = a[i];
for(j = i-h; j>=0 && a[j] > tmp; j-=h)
a[j+h] = a[j];
a[j+h] = tmp;
}
}
증분값(h값)의 선택
h값은 n부터 감소시켜 마음에 1이 되면 됩니다.
static void shellShort(int[] a, int n){
int h ;
for (h = 1; h < n /9; h = h * 3 + 1)
;
for (; h >0; h/=3)
for(int i = h; i<n;i++){
int j;
int tmp = a[i];
for(j = i-h; j>=0 && a[j] > tmp; j-=h)
a[j+h] = a[j];
a[j+h] = tmp;
}
}
06-6 퀵 정렬
퀵 정렬은 일반적으로 사용되고 있는 아주 빠른 정렬알고리즘입니다.
피벗 pivot
pl
pr
static void quickSort(int[] a, int left, int right){
int pl = left;
int pr = right;
int x = a[(pl+pr) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr)
swap(a, pl++, pr--);
}while(pl <= pr);
if(left < pr) quickSort(a, left, pr);
if(pr<ringht) quickSort(a, pl, right);
}
시간 복잡도 : O(n log n)
최악의 시간 복잡도 O(n^2)
06-7 병합 정렬
먼저 정렬마친 두 배열의 병합을 살펴보겠습니다. 각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을 마치는 배열을 만듭니다.
//정렬을 마친
static void merge(int[] a, int na,int[] b, int nb, int[] c){
int pa = 0;
int pb = 0;
int pc = 0;
while(pa<na&& pb <nb)
c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
while(pa < na)
c[pc++] = a[pa++];
while(pb < nb)
c[pc++] = b[pb++]
}
Arrays.sort로 퀵 정렬과 병합 정렬하기
06-8 힙 정렬
힙을 사용하여 정렬하는 알고리즘 입니다.
힙은 '부모의 값이 자식의 값보다 향상 크다'는 조건을 만족하는 완전이진트리입니다.
가장 큰 값이 루트에 위치
부모이 값 >= 자식의 값
힙 정렬
루트를 없애고 힙 상태 유지하기
루트 꺼냅니다. 그런 다음 비어 있는 루트 위치로 힙의 마지막 요소를 옮깁니다.
static void downHeap(int[] a, int left, int right){
int temp = a[left];
int child;
int parent;
for(parent = left; parent < (right+1)/2 ; parent = child){
int cl = parent * 2 +1;
int cr = cl +1;
child = (cr <= right && a[cr] > a[cl]) ? cr:cl;
if (temp >= a[child])
breakl
a[parent] = a[child];
}
a[parent] = temp;
}
static void heapSort(int[] a, int n){
for (int i = (n-1) / 2 ; i >=0;i--)
downHeap(a,i,n-1);
for(int i = n-1; i>0; i--){
swap(a, 0, i);
downHeap(a,0,i-1);
}
}
06-9 도수 정렬
도수 정렬 요소를 비교할 필요가 없다는 특징이 있습니다.
도수 정렬 알고리즘은 도수분포표 작성, 누적도수 분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어집니다.
도수분포표 작성:
각 점수에 해당하는 학생이 몇 명인지를 나타내는 도수분포표를 작성합니다.
누적도수 분포표 작성:
'0점 부터 점수 n까지 몇 명의 학생이 있는지 ' 누적된 값을 나타내는 누적도수분포표를 만든다..
목적 배열 만들기:
각각의 점수를 받은 학생이 몇 번쨰에 위치하느닞 알수 있으므로 이 시점에서 정렬은 거의 마쳤다고 할 수 있습니다.
배열 복사
정렬은 끝났지만 정렬 결과를 저장한 곳은 작업 배열입니다.
static void fSort(int[] a, int n, int max){
int[] f = new int[max+1];
int[] b = new int[n];
for(int i = 0; i<n;i++) f[a[i]]++;
for(int i = 1; i<=max;i++) f[i] += f[i-1];
for(int i = n-1; i>=0;i--) b[--f[a[i]]] = a[i];
for(int i = 0; i<n;i++) a[i] = b[i];
}
[출처] :Do it! 자료구조와 함께 배우는 알고리즘 java편