이번 시간에는 정렬 알고리즘에 대해 학습할 예정이다.
정렬 알고리즘은 양이 방대해서 정렬 종류에 대해 집중적으로 실습할 예정이다.
정렬
이름, 학번, 키 등 Key의 대소 관게에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말한다.
키 값이 작은 데이터부터 앞 쪽에 두면 오름차순
키 값이 큰 데이터부터 앞 쪽에 두면 내림차순
- 안정된 정렬
- 같은 키 값을 가진 요소의 순서가 정렬 전 후에도 유지되는 것을 말한다.
- 내부정렬
- 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘
- 외부정렬
- 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
이번 시간은 모두 내부 정렬을 다룬다.
정렬 알고리즘
1. 교환 2. 선택 3. 삽입
이 세 요소를 응용한 것이 정렬 알고리즘이다.
버블 정렬
이웃한 두 요소의 대소관계를 비교하여 교환을 반복한다.
n개의 요소가 있는 배열에서는 n - 1번 비교한다.
이러한 비교, 교환 과정들을 패스 라고 한다.
배열을 한 번 스캔하면서 요소들을 비교하고 교환하는 과정!
- 프로그램
- 변수 i의 값을 0부터 n - 2 까지 1씩 증가하며 n - 1 회의 패스를 수행한다
- 비교하는 두 요소의 인덱스를 j - 1, j 라고 할 때 a[j - 1], a[j] 의 값을 비교하여 앞 쪽이 크면 교환합니다.
- j의 시작값이 n - 1 이면 a[n - 2] 의 값과 a[n - 1] 의 값을 비교해야 한다.
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);
}
}
}
}알고리즘 개선
이미 배열이 정렬을 마친 상태라면, 그 이후의 패스에서는 요소끼리 교환하지 않는다.
즉, 어떤 패스에서 요소의 교환 횟수가 0이라면 더 이상 정렬할 요소가 없다는 뜻이기 때문에
정렬 작업을 멈추면 된다.
static void bubbleSort(int[] a, int n){
int exchg = 0;
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);
exchg++;
}
}
if(exchg == 0){
break; //교환 횟수가 0이면 정렬 작업을 멈춘다.
}
}
}
exchg의 값은 한 번의 패스에서 시도한 교환 횟수와 같다.
따라서 값이 0이면 정렬할 요소가 없는 것이므로 break문으로 메서드를 종료한다.
알고리즘 개선(2)
교환을 마치고 난 이후 교환이 수행되지 않는다면 그보다 앞 쪽의 요소들은 이미 정렬되어 있는 상태라고 할 수 있다.
static void bubbleSort(int[] a, int n){
int k = 0; //a[k]보다 앞쪽은 정렬을 마친 상태
while(k < n -1){
int last = n - 1; //마지막으로 요소를 교환한 위치
for(int j = n - 1; j > k; j--){
if(a[j - 1] > a[j]){
swap(a, j - 1, j);
last = j;
}
}
k = last;
}
}
하나의 패스를 마쳤을 때 last의 값을 k에 대입하여 다음에 수행할 패스의 범위를 제한한다.
그렇게 되면 다음 패스에서 마지막으로 비교할 두 요소는 a[k] 와 a[k - 1] 이 된다.
단순 선택 정렬
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다.
- 제일 작은 수를 택하여 첫 번째 요소와 교환
- 첫 번째 요소를 제외한 요소 중 제일 작은 수를 선택하여 두 번째 요소와 교환
- 결론: 값이 가장 작은 요소를 선택하고 아직 정렬하지 않은 부분의 첫 번째 요소와 교환
이 과정을 n - 1 회 반복하면 된다.
static void swap(int[] a, int idx1, int idx2){
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void selectionSort(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);
}
}
이 정렬은 안정적이지 않다.
그림으로 보면 같은 요소일 때 왼쪽, 오른쪽의 순서가 깨질 수 있기 때문이다.
단순 삽입 정렬
선택한 요소를 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘이다.
단순 선택은 작은 요소를 앞으로 옮기는 작업이지만, 삽입 정렬은 작은 요소를 알맞은 위치에 삽입한다!
- 2번째 요소부터 선택하여 진행한다.
- 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입한다.
- 앞에 있는 요소와 비교하여 큰 요소를 뒤로 밀어내는 그림이다.
'알맞은 위치 삽입'
앞으로 이동하면서 선택한 요소보다 크면 자리를 바꾸면서 이동한다.
그러다 선택한 요소보다 작은 요소를 만나면 검사할 필요가 없으므로 해당 위치에 삽입한다.
static void insertionSort(int[] a, int n){
for(int i = 1; i < n; i++){
int j;
int tmp = a[i];
for(j = i; j > 0 && a[j - 1] > tmp; j--){
a[j] = a[j - 1];
}
a[j] = tmp;
}
}
단순 삽입 정렬 알고리즘은 요소들이 떨어져 있어도 서로 뒤바뀌지 않아 안정적이다.
지금까지의 버블, 단순 선택, 단순 삽입 정렬 알고리즘은 O(NxN) 시간을 가진다.
셸 정렬
단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘이다.
- 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빠르다. (장점)
- 삽입할 위치가 멀리 떨어져 있으면 대입해야 하는 횟수가 많아진다. (단점)
셸 정렬은 정렬할 배열의 요소를 그룹으로 나워 각 그룹 별로 단순 삽입 정렬을 수행하고,
그 그룹을 합치면서 정렬을 반복하면서 요소의 이동 횟수를 줄이는 방법이다.
- 2개 요소씩 묶인 그룹에 대해 4-정렬
- 4개 요소식 묶인 그룹에 대해 2-정렬
- 1-정렬
결론: 조금이라도 정렬에 가까운 상태에서 단순 삽입 정렬을 수행한다.
static void shellSort(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;
}
}
}
정렬 횟수는 늘지만, 요소 이동의 횟수가 줄어든다.
퀵 정렬
가장 빠른 정렬 알고리즘 중 하나이다.
보통 피벗을 기준으로 그룹을 나눈 다음에 정렬을 실행한다.
Pivot : 그룹을 나누는 기준
- 피벗 이하의 요소는 왼쪽
- 피벗 이상의 요소는 오른쪽
계속 스캔하면 pl, pr이 교차하면서 그룹을 나누는 과정을 마친다.
pl, pr 이 동일한 요소 위에 있는지 매번 검사해줘야 한다!
static void partition(int[] a, int n){
int pl = 0;
int pr = n - 1;
int x = a[n/2];
do{
while(a[pl] < x){
pl++;
}
while(a[pr] > x){
pr--;
}
if(pl <= pr){
swap(a, pl++, pr--);
}
}while(pl <= pr);
이러한 방법을 더 발전시키면 퀵 정렬 알고리즘이 된다.
분할 정복 알고리즘이기 때문에 재귀적으로 구현할 수 있다.
요소가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없으므로 요소의 개수가 2개 이상인 그룹만 나누면 된다.
import java.util.Scanner;
public class QuickSort {
static void swap(int[] a, int idx1, int idx2){
int tmp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = tmp;
}
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(pl<right){
quickSort(a, pl, right);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("퀵 정렬");
System.out.println("요솟수: ");
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++){
System.out.println("x[" + i + "] : ");
a[i] = sc.nextInt();
}
quickSort(a, 0, n-1);
System.out.println("오름차순");
for(int i = 0; i < n; i++){
System.out.println(a[i]+" ");
}
}
}
비재귀적인 퀵 정렬
재귀 메서드를 비재귀적으로 구현한 적이 있었다.
스택을 이용해서 퀵 정렬을 비재귀적으로 구현해보자
- lstack: 나눌 범위의 왼쪽 끝 요소의 인덱스를 저장하는 스택
- rstack: 나눌 범위의 오른쪽 끝 요소의 인덱스를 저장하는 스택
static void quickSort(int[] a, int left, int right){
IntStack lstack = new IntStack(right - left + 1);
IntStack rstack = new IntStack(right - left + 1);
lstack.push(left);
rstack.push(right);
while(!lstack.isEmpty()) {
int pl = left = lstack.pop();
int pr = right = rstack.pop();
int x = a[(left + right) / 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) {
lstack.push(left);
rstack.push(pr);
}
if (pl < right) {
lstack.push(pl);
rstack.push(right);
}
}
}
이 배열을 스택과 그림으로 나타내면 오른쪽 요소부터 스택에 들어갔다가 팝하면서 나오고
왼쪽으로 나누어진 배열이 다시 팝하면서 나뉜다.
스택에 푸시한 값을 그룹으로 나눌 배열의 첫 요소와 끝 요소의 인덱스이다.
- 스택의 용량
- 스택의 용량을 배열의 요솟수로 추가한다.
- 요소의 개수가 많은 그룹을 먼저 푸시하는 경우
- 요소의 개수가 적은 그룹을 먼저 푸시하는 경우
일반적으로 요소의 개수가 적은 배열일수록 적은 횟수로 분할을 종료할 수 있다.
따라서 요소의 개수가 많은 그룹을 먼저 푸시하는 경우처럼
많은 그룹을 나누기보다는 요소의 개수가 적은 그룹을 먼저 분할하는 것이 효과적이다.
- 피벗 선택하기 (기준이 되는 수)
- 빠른 정렬을 위해서는 배열을 정렬한 다음에 가운데 값을 피벗으로 하면 된다.
배열의 크기가 균등하게 나누어지기 때문이다. - 가운데 값을 구하고자 하면 이에 대한 처리가 또 필요하다.
- '나눌 배열의 요소의 개수가 3 이상이면 임의로 요소 3을 선택하고 그중에서 중앙값인 요소를 피벗으로 선택한다.'
- 임의로 요소 3 이라는 것은 처음, 가운데, 끝을 의미한다.
- 빠른 정렬을 위해서는 배열을 정렬한 다음에 가운데 값을 피벗으로 하면 된다.
- 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소 a[right - 1] 를 교환한다.
피벗으로 끝에서 두 번째 요소의 값을 선택하여 나눌 대상의 범위를 a[left + 1] ~ a[right - 2] 로 좁힌다.
그룹의 크기가 한 쪽으로 치우치는 것을 피하면서도 나눌 때 스캔할 요소를 3개씩 줄일 수 있다는 장점이 있다.
퀵 정렬은 배열을 나누어 보다 작은 문제를 해결하는 과정을 반복하므로 시간 복잡도는 O(n log n) 이다.
다만 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간 복잡도가 증가하는 경우가 존재한다.
만약, 매번 단 하나의 요소와 나머지 요소로 나누어지면 n번의 분할이 필요하다. 따라서 최악의 시간 복잡도는 O(n2)이 된다.
병합 정렬
배열의 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘이다.
- 배열의 병합
import java.util.Scanner;
public class mergeSort {
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++];
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] a = {2, 4, 6, 8, 11, 13};
int[] b = {1, 2, 3, 4, 9, 16, 21};
int[] c = new int[13];
System.out.println("두 배열의 병합");
merge(a,a.length,b,b.length,c);
System.out.println("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
System.out.println("배열 a : ");
for(int i=0;i<a.length;i++){
System.out.println("a[" + i + "] = " + a[i]);
}
System.out.println("배열 b : ");
for(int i=0;i<b.length;i++){
System.out.println("b[" + i +"] = " + b[i]);
}
System.out.println("배열 c : ");
for(int i=0;i<c.length;i++){
System.out.println("c[" + i +"] = " + c[i]);
}
}
}
병합에 필요한 시간 복잡도는 O(N)이다.
- 병합 정렬
- 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.
- 배열을 앞부분, 뒷부분으로 나누고 정렬한 후, 나눈 두 배열을 병합하면 배열 모두를 정렬할 수 있다.
- 이때 앞부분, 뒷부분을 정렬할 때도 병합 정렬을 적용한다.
import java.util.Scanner;
public class MergeSort {
static int[] buff;
static void __mergeSort(int[] a, int left, int right){
if(left<right){
int i;
int center = (left + right) / 2;
int p = 0;
int j = 0;
int k = left;
__mergeSort(a, left, center);
__mergeSort(a, center + 1, right);
for(i = left; i <= center; i++){
buff[p++] = a[i];
}
while(i <= right && j < p){
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
}
while(j < p){
a[k++] = buff[j++];
}
}
}
static void mergeSort(int[] a, int n){
buff = new int[n];
__mergeSort(a, 0, n-1);
buff = null;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("병합 정렬");
System.out.print("요솟수 : ");
int nx = sc.nextInt();
int[] x =new int[nx];
for(int i=0;i<nx;i++){
System.out.print("x[" + i + "]: ");
x[i] = sc.nextInt();
}
mergeSort(x,nx);
System.out.println("오름차순으로 정렬했습니다.");
for(int i = 0; i < nx; i++){
System.out.println("x[" + i +"]="+x[i]);
}
}
}
배열의 앞부분을 buff[0] ~ buff[center - left]에 복사한다.
배열의 뒷부분과 buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 a에 저장한다.
배열 buff에 남아 있는 요소를 배열 a에 복사한다.
병합의 시간 복잡도는 O(N)이고, 병합 정렬의 단계는 O(log n)이다.
서로 떨어져 있는 요소들을 교환하는 것이 아니므로 안정적인 정렬 방법이라고 할 수 있다.
Array.sort 메서드
이전에 봤던 binarySearch 메서드처럼 java.util.Arrays 클래스 메서드에서 sort도 제공한다.
sort 메서드는 모두 오름차순으로 정렬한다.
- 기본 자료형 배열의 정렬(퀵 정렬)
- sort메서드가 사용하는 알고리즘은 퀵 정렬 알고리즘을 개선한 것으로 안정적이지는 않다.
- 배열에 같은 요소가 있을 경우 순서가 바뀔 수 있다.
import java.util.Scanner;
import java.util.Arrays;
public class ArraySortTester {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("요솟수 : ");
int num = sc.nextInt();
int[] x = new int[num];
for(int i=0;i<num;i++){
System.out.print("x[" + i + "] : ");
x[i] = sc.nextInt();
}
Arrays.sort(x);
System.out.println("오름차순으로 정렬했습니다.");
for(int i=0;i<num;i++){
System.out.println("x[" + i + "] = " +x[i]);
}
}
}
- 클래스 객체 배열의 정렬(병합 정렬)
- 자연 정렬이 필요한 배열
- 요소의 대소 관계를 비교
- 자연 정렬이 필요한 배열
import java.util.*;
import static java.util.Calendar.*;
class SortCalendar {
public static void main(String[] args) {
GregorianCalendar[] x = {
new GregorianCalendar(2017,Calendar.NOVEMBER,01),
new GregorianCalendar(1963,Calendar.OCTOBER,18),
new GregorianCalendar(1985,Calendar.APRIL,5),
};
Arrays.sort(x);
for(int i=0;i<x.length;i++){
System.out.printf("%04d년 %02d월 %02d일\n",
x[i].get(YEAR),
x[i].get(MONTH),
x[i].get(DATE)
);
}
}
}- 자연 정렬이 필요하지 않은 배열
- Comparator C를 이용하여 정렬
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
public class PhyscExamSort {
static class PhyscData{
String name;
int height;
double vision;
PhyscData(String name,int height,double vision){
this.name=name;
this.height=height;
this.vision=vision;
}
public String toString(){
return name + " " + height + " " + vision;
}
static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData>{
@Override
public int compare(PhyscData d1, PhyscData d2) {
return (d1.height > d2.height) ? 1 : (d1.height < d2.height) ? -1 : 0;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PhyscData[] x = {
new PhyscData("이나령", 162, 0.3),
new PhyscData("전서현", 173, 0.7),
new PhyscData("이수민", 175, 2.0),
new PhyscData("홍준기", 171, 1.5),
new PhyscData("유지훈", 168, 0.4),
new PhyscData("김한결", 174, 1.2),
};
Arrays.sort(x, PhyscData.HEIGHT_ORDER);
System.out.println("신체검사 리스트");
System.out.println(" name height vision");
System.out.println("--------------------");
for(int i = 0; i < x.length; i++){
System.out.printf("%-8s%3d%5.1f\n", x[i].name, x[i].height, x[i].vision);
}
}
}
제네릭 기법을 활용하여 compare를 구현해주면 된다.
힙 정렬
힙의 특성을 이용하여 정렬을 수행한다.
힙은 '부모의 값이 자식의 값보다 항상 크다' 라는 조건을 만족하는 완전이진트리이다.
부모의 값이 자식보다 항상 작아도 힙이다. => 부모와 자식의 관계만 일정하면 된다.
- 힙을 배열에 대입하기
- 가장 위쪽에 있는 루트를 0번째 인덱스에 넣고
- 한 단계 아래 요소를 왼쪽에서 오른쪽으로 따라 가면서 대입한다.
- 관계식
- 부모: a[(i - 1) / 2]
- 왼쪽 자식: a[i * 2 + 1]
- 오른쪽 자식: a[i * 2 + 2]
- 힙 정렬
- 가장 큰 값이 루트에 위치하는 특징을 이용하는 알고리즘
- 선택정렬을 응용한 알고리즘이다 => 가장 작은 값을 찾아서 맨 앞 요소와 바꿨던 기억이 있다.
- 힙 정렬에서는 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰 값을 구해야한다.
따라서 남은 요소들도 힙의 형태를 유지해야 한다.
- 순서 (이 과정을 진행하기 위해서는 초기 상태의 배열을 힙 상태로 만들어야 한다.)
- 루트를 꺼낸다.
- 마지막 요소를 루트로 이동시킨다.
- 루트에서부터 자식 요소 2개와 비교하며 자신보다 큰 값을 가지는 요소들과 자리를 바꾸며 내려간다.
- 자식의 값이 자신보다 작거나 교환할 자식이 없으면 작업이 종료된다.
- 배열로 힙 만들기
- 작은 부분트리부터 시작하여 올라가는 방식으로 전체 배열을 힙으로 만들 수 있다.
- 부분트리의 선택 범위를 위로 한 칸씩 확장해가며 트리 전체를 선택합니다.
- 시간 복잡도
- 선택 정렬에서 최대나 최솟값을 찾기 위해서는 정렬되지 않은 요소 전체를 탐색해야 했다.
- 힙 정렬에서는 배열이 힙 상태를 유지하기 때문에 찾는 것에는 O(1) 로 줄지만,
다시 힙으로 만드는 작업은 O(log n)으로 된다. (이진 검색과 비슷하기 때문) - 따라서 힙 정렬의 시간 복잡도는 O(n log n) 이다.
import java.util.Scanner;
public class HeapSort {
static void swap(int[] a, int idx1, int idx2){
int temp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = temp;
}
static void downHeap(int[] a, int left, int right){
int temp = a[left]; //left에서 right의 요소를 힙으로 만든다.
int child;
int parent;
//a[left] 이외의 요소들을 힙으로 만든다.
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]){
break;
}
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);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("힙 정렬: ");
System.out.println("요소수: " );
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++){
System.out.print("x["+i+"] = ");
a[i] = sc.nextInt();
}
heapSort(a, n);
System.out.println("오름차순으로 정렬했습니다.");
for(int i = 0; i < n; i++){
System.out.println(a[i]);
}
}
}
도수 정렬
도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.
지금까지의 정렬 알고리즘은 두 요소의 키 값을 비교해야 했다.
도수 정렬은 요소를 비교할 필요가 없다는 특징이 있다.
- 도수분포표 만들기
- 도수분포표를 나타내기 위해 다른 배열(f)을 추가적으로 사용한다.
- 만약 a[0] 이 4점이라면 f[a[0]]의 요소를 증가시킨다.
- 이런 작업을 배열 끝까지 반복하면 도수분포표가 완성된다.
- 누적도수분포표 만들기
- 도수분포표를 기록한 배열 f 에서 바로 앞의 요솟값을 더하는 과정을 진행한다.
- 이렇게 되면 f[4]의 값을 f[0] ~ f[3] 의 누적합을 가지게 된다.
- 목적 배열 만들기
- 기존 배열의 값들과 누적도수분포표 f를 대조하여 정렬을 완성할 수 있다.
- a[8]의 값이 3일 때 누적도수분포표 배열 f[3]의 값이 5이다.
- 목적 배열인 b[4] 에 3을 대입한다.
- f의 값이 5인데 b[4]에 대입하는 이유는 미리 값을 감소시켜 중복되는 값을 저장하기 위함이다.
- 배열 복사하기
- 목적 배열 b를 기존 배열인 a에 복사해주면 끝난다.
도수 정렬은 for문 만으로 구현할 수 있는 아름다운 알고리즘이다! (main제외,,)
import java.util.Scanner;
public class FSort {
static void fSort(int[] a, int n, int max){
int[] f = new int[max + 1];
int[] b = new int[n];
//1단계
for(int i = 0; i < n; i++){
f[a[i]]++;
}
//2단계: Add front of index
for(int i = 1; i <= max; i++){
f[i] += f[i - 1];
}
//3단계: Add Extra Array
for(int i = n - 1; i >= 0; i--){
b[--f[a[i]]] = a[i];
}
//4단계: Copy Extra Array
for(int i = 0; i < n; i++){
a[i] = b[i];
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("도수 정렬");
System.out.println("요솟수: ");
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i++){
do{
System.out.print("x[" + i + "] : ");
a[i] = sc.nextInt();
}while(a[i] < 0);
}
int max = a[0];
for(int i = 1; i < n; i++){
if(a[i] > max){
max = a[i];
}
}
fSort(a, n, max);
System.out.println("오름차순으로 정렬했습니다.");
for(int i = 0; i < n; i++){
System.out.println(a[i]);
}
}
}
자바에서는 배열을 생성하면 기본적으로 모든 요소가 0으로 초기화 되기 때문에 f와 b 배열에 일일이 대입할 필요가 없다.
도수 정렬 알고리즘은 데이터의 비교, 교환 작업이 필요없어 매우 빠르지만,
도수분포표가 필요하기 때문에 최솟값과 최댓값을 미리 알고 있는 경우에만 사용할 수 있다.
요소를 건너뛰지 않기 때문에 안정적인 정렬 알고리즘이다.
지금까지 정렬 알고리즘에 대해 학습했다.
종류가 워낙 많아서 시간이 오래 걸렸지만, 중요하게 여기는 퀵 정렬이나
새로 배웠던 도수 정렬까지 배운 내용들이 많다.
다음엔 집합에 대해 알아볼 계획이다!