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 

78 

12 

42 

 2단계

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


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


 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


 counts[0]

counts[1] 

counts[2] 

counts[3] 

counts[4] 

 0


temp[0] 

temp[1] 

temp[2] 

temp[3] 

temp[4] 

temp[5] 

temp[6] 

temp[7] 

 0



Counting Sort 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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;
    }
}
 
cs


'알고리즘 > SW Expert Academy' 카테고리의 다른 글

검색  (0) 2019.02.09
부분 집합 문제  (0) 2019.02.09
2차원 배열  (0) 2019.02.03
탐욕 알고리즘(Greedy Algorithm)을 이용한 Baby-gin  (0) 2019.01.20
완전 검색을 이용한 Baby-gin  (0) 2019.01.19

+ Recent posts