Sort(정렬)에 대해서 (1) - Bubble Sort와 Counting Sort

Sort(정렬)이란?  

2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순) 혹은 그 반대의 순서(내림차순)대로 재배열 하는 것

Sort 방식의 종류

1. Bubble Sort(버블 정렬)
2. Counting Sort(카운팅 정렬)
3. Selection Sort(선택 정렬)
4. Quick Srot(퀵 정렬)
5. Insertion Sort(삽입 정렬)
6. Merge Sort(병합 정렬)

Bubble Sort(버블정렬) - O^2 

입전한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

1. 첫번째 원소부터 인접한 원소끼리 게속 자리를 교환하면서 맨 마지막 자리까지 이동
2. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 마지막 자리로 정렬됨 

{55, 7, 78, 12, 42} 를 Bubble Sort하는 과정

1단계	55	7	78	12	42
2단계	7	55	78	12	42
3단계	7	55	78	12	42
4단계	7	55	12	78	42
5단계	7	55	12	42	78

1. 55와 7을 비교하여 55가 더 큰 숫자이니 7과 자리를 바꾼다.
2. 자리를 바꾼 후 55와 78을 비교하는데 78이 더 크므로 자리 이동이 일어나지 않는다.
3. 78과 12를 비교하여 78이 더 큰 숫자이니 12와 자리를 바꾼다.
4. 자리를 바꾼 후 78과 42를 비교하여 78이 더 크니 42와 자리를 바꾼다.
5. 78이 가장 마지막 위치에 자리하였으므로 원소 1개에 대해서 정렬이 완료된 것이다.

1단계	7	55	12	42	78
2단계	7	55	12	42	78
3단계	7	12	55	42	78
4단계	7	12	42	55	78

1. 7과 55를 비교하였으나 55가 더 크므로 자리를 변경하지 않는다.
2. 55와 12를 비교하여 숫자 55가 더 크므로 12와 자리를 바꾼다
3. 55와 42를 비교하여 5가 더 크므로 42와 자리를 바꾼다
4. 78은 이미 정렬된 원소이기 때문에 비교대상이 아니고, 55는 마지막 위치에 자리하였기 때문에 또 하나의 원소에 대해서 정렬이 완료된 것이다.

위와 같은 작업을 반복하면 최종적으로 {7, 12, 42, 55, 78} 로 정렬이 완료될 것이다.

Bubble Sort 구현하기. 

Counting Sort(카운팅 정렬)

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 Algorithm

→ 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능. 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스되는 카운트들의 배열을 사용하기 때문임.  예를 들어 { 0, 4, 1, 3, 1, 2, 4, 1 } 를 Counting Sort를 이용하여 정렬하기 위해서는 { 1, 3, 1, 1, 2 } 란 Counts 배열이 필요함.

{ 0, 4, 1, 3, 1, 2, 4, 1 } 을 Counting Sort 하는 과정.

1. Data 배열과 Counts 배열 준비

Data 배열

data[0]	data[1]	data[2]	data[3]	data[4]	data[5]	data[6]	data[7]
0	4	1	3	1	2	4	1

Counts 배열

  - Counts 배열은 Data 배열의 요소를 인덱스로 하고 그 값은 요소의 개수로 한다. 그 작업 결과는 아래와 같다.

counts[0]	counts[1]	counts[2]	counts[3]	counts[4]
1	3	1	1	2

 - Data 배열의 원소가 정렬될 때 배열의 몇 번째 위치에 들어가야 하는지 보여주는 Counts 배열로 변경해야 한다. 그 작업은 다음과 같다.

counts[0] = counts[0], counts[1] = counts[0]+counts[1], counts[2] = counts[1]+counts[2] ... counts[4] = counts[3] + counts[4] 

counts[0]	counts[1]	counts[2]	counts[3]	counts[4]
1	4	5	6	8

2. Data의 마지막 항목부터 정렬을 진행한다. Data의 마지막 항목은 1 이므로 Counts 배열의 1번 인덱스를 확인(4)하고 값을 1감소 시킨 후(3) Counts에       저장하고 Temp 배열에 4번째에 1을 삽입한다.

data[0]	data[1]	data[2]	data[3]	data[4]	data[5]	data[6]	data[7]
0	4	1	3	1	2	4	1

counts[0]	counts[1]	counts[2]	counts[3]	counts[4]
1	3	5	6	8

temp[0]	temp[1]	temp[2]	temp[3]	temp[4]	temp[5]	temp[6]	temp[7]
			1

3. Data의 마지막에서 두 번째 항목은 4이므로 Counts 배열의 4번 인덱스를 확인(8)하고 값을 1 감소시킨 후 Counts에 저장(7)한 뒤 Temp 배열의 8번째     에 4 저장. 

data[0]	data[1]	data[2]	data[3]	data[4]	data[5]	data[6]	data[7]
0	4	1	3	1	2	4	1

counts[0]	counts[1]	counts[2]	counts[3]	counts[4]
1	3	5	6	7

temp[0]	temp[1]	temp[2]	temp[3]	temp[4]	temp[5]	temp[6]	temp[7]
			1				4

4. 위와같은 작업을 반복하면 최종적인 결과는 아래와 같음

data[0]	data[1]	data[2]	data[3]	data[4]	data[5]	data[6]	data[7]
0	4	1	3	1	2	4	1

counts[0]	counts[1]	counts[2]	counts[3]	counts[4]
0	1	4	5	6

temp[0]	temp[1]	temp[2]	temp[3]	temp[4]	temp[5]	temp[6]	temp[7]
0	1	1	1	2	3	4	4

Counting Sort 구현하기

import java.util.Scanner;
 
public class CountingSort {
    public static void main(String[] args) {
        int[] data = new int[8]; 
        
        Scanner sc = new Scanner(System.in);
        for(int i=0; i<data.length; i++) {
            data[i] = sc.nextInt();
        }
        int[] counts = getCounts(data);
        int[] sorted = countingSort(data, new int[data.length] , counts);
        
        for(int i=0;i <sorted.length; i++) {
            System.out.printf(sorted[i]+" ");
        }
    }
    
    public static int[] getCounts(int[] data) {
        // 요소의 최대값 구함
        int max = data[0];
        for(int i=0; i<data.length; i++) {
            if(max < data[i]) {
                max = data[i];
            }
        }
        // 요소의 값을 인덱스로 하고, 요소의 개수를 값으로 가지는 count 배열 생성
        int[] counts = new int[max+1];
        for(int i=0; i<data.length; i++) {
            counts[data[i]] = counts[data[i]]+1;
        }
        
        // count배열에 요소를 정렬하였을 때 위치를 표시
        for(int i=1; i<counts.length; i++) {
            counts[i] = counts[i-1] + counts[i];
        }
        return counts;
    }
    
    public static int[] countingSort(int[] data, int[] sort, int[] counts) {
        for(int i=data.length-1; i>=0; i--) {
            counts[data[i]] = counts[data[i]] - 1;
            sort[counts[data[i]]] = data[i];
        }
        
        return sort;
    }
}