삽입정렬(Insertion sort)


삽입 정렬은 정렬이 우리가 카드놀이 할때 카드를 받아 정렬하는 것 처럼 즉 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬 하는 방법 입니다. 예를 들어 5장의 카드 A, 4, 7, J, 2를 순서대로 받았을 때 A, 4, 7, J는 정렬된 부분이므로 손대지 않고 2를 A와 4 사이에 집어 넣는 것을 떠올리시면 됩니다. 


배열  arr[5]={1, 4, 7, 10, 2}  가지고 삽입 정렬을 설명 해보겠습니다. 


14, 7, 10, 2 } temp = 4

배열의 첫번째는 이미 정렬 되어 있다고 가정하고 2번째 값 (arr[1]) 부터 시작합니다. 

먼저 배열의 2번째 값을 임시 변수(temp)에 저장하고 배열의 첫번째 값과 비교 합니다. 

arr[0]<temp 이므로 두 수는 올바르게 정렬되어 있습니다. 따라서 임시 변수에 저장된 값은 다시 원래 위치에 넣어줍니다. 


147, 10, 2 } temp = 7

다음으로 arr[2]을 선택해 임시 배열의 저장하고 이전 배열의 값들과 비교 합니다. 

arr[1]<temp 그리고 arr[0]<temp 이므로 다시 원래 위치로 넣어줍니다. 

마찬가지 방법으로 배열은 arr[3] 까지 정렬 되어 있으므로 생략하겠습니다.  

...

147, 10, 2 } temp = 2

다음으로 arr[4]을 선택해 임시 배열의 저장하고 이전 배열의 값들과 비교 합니다.

arr[3]>temp 이므로 arr[3]을 arr[4]로 밀어냅니다.  147, 1010 } temp=2 

arr[2]>temp 이므로 arr[2]를 arr[3]으로 밀어냅니다. 147, 710 } temp=2

arr[1]>temp 이므로 arr[1]을 arr[2]로 밀어냅니다. 144710 } temp=2 (빨간숫자는 의미없는 값.)

arr[0]<temp 이므로 temp의 저장된 값을 비어 있는 칸(의미없는 값) 에 넣어주면 정렬이 완료 됩니다.  1, 2, 47, 10 }


삽입 정렬은 데이터가 역순으로 주어졌을때 최악의  의 실행 시간을 가집니다.  

간단하게 구현할 수 있으므로 자료수가 적거나 배열이 거의 정렬 되 어있을때 유용 할 수 있습니다.


다음은 자바로 구현한 삽입정렬 입니다.


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
    //정렬된 부분에 정렬되지 않은 데이터를 삽입하는 방법.
    //간단하게 구현 할 수 있음.
    //최악의 경우 시간복잡도 O(n^2)
    //자료수가 적거나 자료의 정렬 정도가 높을때 적용.
 
    public void sort(int[] arr) {
 
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i]; // 임시 변수에 대상 배열 값을 저장한다.
            int j;
            for (j = i - 1; j >= 0; j--) {
                if(arr[j]<temp){ //임시변수가 비교하는 대상보다  클때 탐색 종료.
                    break;
                }else{
                    arr[j+1]=arr[j]; //임시변수가 비교 대상보다 작다면 대상을 한칸 밀어낸다.
                }
            }
            arr[j+1]=temp; //임시변수에 저장한 값을 비어있는 위치에  삽입한다.
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {147102};
        new InsertSort().sort(arr);
        
        for (int a : arr) {
            System.out.print(a + " ");
        }
        
        //출력 : 1 2 4 7 10
 
    }
cs



덧) 삽입 정렬의 비교의 횟수를 줄이기 위해 이진 검색(Binary Search) 을 이용 할 수 있습니다. 


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
//삽입정렬에서 탐색에 걸리는 시간은  최악의 경우 i번째반복시 O(i) 
//이진탐색을 통해 탐색시간을  O(Logi)로 줄일 수 있다. 
//그러나 전체 알고리즘은 삽입에 필요한 시간 때문에 O(n^2)을 가짐. 
    
    public int serach(int[] arr, int left, int right, int x) {
        
        if (right >= left) {
            int mid = left + ((right-left)/ 2);
            
            //찾는 값(x)과 배열의 요소가 일치하면 배열의 인덱스를 반환한다.
            if (arr[mid] == x)
                return mid;
            //찾는 값(x)보다 배열의 요소가 크다면 배열의 오른쪽 절반을 무시한다.
            if (arr[mid] > x)
                return serach(arr, left, mid-1, x);
            //찾는 값(x)보다 배열의 요소가 작다면 배열의 왼쪽 절반을 무시한다.
            return serach(arr, mid+1, right, x);
        }
        //일치하는 값이 없다면 배열의 맨 왼쪽 인덱스 반환
        return left;
    }
 
    
    public void sort(int[] arr) {
        
        int temp,find_Index,j;     //임시변수, 탐색결과가 들어갈 변수 선언
 
        for (int i = 1; i < arr.length; i++) {
            temp = arr[i]; // 임시 변수에 대상 배열 값을 저장한다.
            find_Index= serach(arr, 0, i, temp); 
            //임시변수 값이 들어갈 인덱스를 이진탐색한다. serach() 메소드 참조
                                    
            for (j = i - 1; j >= find_Index; j--) {
                    arr[j+1]=arr[j]; 
            } //선택된 배열부터 임시변수 값이 들어갈 자리까지 오른쪽으로 한칸씩 밀어낸다.
            
            arr[find_Index]=temp; //임시변수에 저장한 값을 이진탐색을 통해 찾은 인덱스에  삽입한다.
        }
    }
cs




버블정렬(Bubble sort)


버블 정렬은 정렬이 이름 처럼 거품이 수면으로 올라오는 것처럼 진행된다고 해서 붙여진 이름 입니다.  

반복적으로 인접한 배열의 크기를 비교해가면서 정렬해나가는 방법으로 매우 쉽게 구현 할 수 있지만 정렬 효율은 좋지 않습니다. 


버블 정렬은 아래와 같은 순서로 진행 됩니다.


1) 배열의 시작부터 인접한 요소 두개를 선택합니다.

2) 요소를 비교해 큰 요소를 뒤로 보냅니다.

3) 모든 배열이 정렬 될 때 까지 위의 과정을 반복합니다.


배열  arr[5]={1, 82, 45, 66, 55}  가지고 버블 정렬을 설명 해보겠습니다. 


182, 45, 66, 55 } arr[0] < arr[1] 이므로 교환 하지 않습니다.

1, 8245, 66, 55 } -> 1, 45 ,82, 66, 55 } arr[1] > arr[2] 이므로 교환 합니다.

1, 4582, 66, 55 } -> 1, 45 ,6682, 55 } arr[2] > arr[3] 이므로 교환 합니다.

1, 456682, 55-> 1, 45665582 } arr[3] > arr[4] 이므로 교환 합니다.


다시 처음으로 돌아 갑니다.

1, 45665582 } arr[0] < arr[1] 이므로 교환 하지 않습니다.

1, 45665582 } arr[1] < arr[2] 이므로 교환 하지 않습니다.

1, 45665582 } -> 1, 45, 55, 6682 } arr[2] > arr[3] 이므로 교환 합니다.

정렬이 완료 되었지만 알고리즘 입장에선 정렬 여부를 알 수 없으므로 계속해서 진행 합니다.

1, 45556682 } arr[3] < arr[4] 이므로 교환 하지 않습니다.


                                ...


이처럼 정렬이 완료 된 후에도 계속 정렬 작업을 해야 하므로 버블정렬의 알고리즘은 항상  의 실행 시간을 가집니다.


다음은 자바로 구현한 버블정렬 입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    // 버블정렬 알고리즘은 인접한 두개의 원소를 비교하여 정렬 한다.
    // 코드가 단순 하므로 쉽게 사용 할 수 있다.
    // 시간 복잡도 O(n^2)
    
    // 배열의 요소를 교환 해주는 메소드.
    public void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
 
    public void bubbleSort(int[] arr) {
 
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1 ; j++) {
                // 인접한 두개의 배열을 비교해 이전 인덱스의 수가 클 경우
                // 큰 수를 뒤로 보낸다.
                if (arr[j] > arr[j + 1]) { 
                    swap(arr, j, j + 1);
                }
            }
 
        }
    }
cs


  버블 정렬 알고리즘은 정렬이 완료 되어도 모든 루프를 수행해야 하지만 내부 루프에서 교환이 발생 하지 않는다면 수행을 중단시킴으로서 성능을 향상 시킬 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    public void bubbleSort(int[] arr) {
 
        // 배열 교환을 감지할 변수
        boolean swapped;
 
        for (int i = 0; i < arr.length - 1; i++) {
            swapped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    //교환이 발생 한다면 true
                    swapped = true;
                }
            }
            //배열 교환이 발생하지 않았다면 주어진 배열은 이미 정렬이 완료 되어 있음.
            //따라서 루프를 탈출한다.
            if (!swapped)
                break;
        }
    }
cs


선택정렬(Selection Sort)


선택정렬은 제자리 정렬 알고리즘의 하나 입니다. 

주어진 배열은 정렬 된 부분과 정렬되지 않는 부분으로 나누어 다음과 같은 방법으로 정렬 합니다. 


1) 정렬 되지 않은 부분에서 최소(또는 최대)의 요소를 찾습니다.

2) 정렬 되지 않은 부분의 첫번째 위치와 위에서 찾은 요소를 교환 합니다.

3) 모든 배열이 정렬 될 때 까지 위의 과정을 반복합니다.


첫번째 루프에선 배열 전체가 정렬 되지 않은 부분 이므로 arr[0...9] 에서 최솟값을 찾아 정렬되지 않은 부분의 첫 요소 arr[0] 와 교환 합니다.

                            최솟값

12

1

32

45

77

11

23

49

 21

 100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]


두번째 루프에선 이미 정렬된 요소 arr[0] 을 제외한 나머지 부분 arr[1...9] 최솟값을 찾아 정렬되지 않은 부분의 첫 요소 arr[1] 와 교환합니다.

                                                                                                                                                                               최솟값

1

12

32

45

77

11

23

49

 21

 100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]


위와 같은 방법으로 정렬되지 않은 부분에서 최솟값을 찾아 정렬되지 않은 부분의 첫 요소와 계속 교환하는 방식으로 모든 배열을 정렬 할 수 있습니다.

                                                                                                                                                                               최솟값

1

11

12

21

23

32

77

49

45

 100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]



다음은 자바로 구현한 선택정렬 입니다.


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
    // 선택정렬 알고리즘은 정렬되지 않은 부분에서 최소(또는 최대) 요소를 찾아
    // 정렬되지 않은 배열의 첫인덱스에 값을 넣어 배열을 정렬한다.
    // 즉, 선택정렬에선 두 개의 서브 어레이를 유지한다.
    // 1) 정렬 된 부분
    // 2) 정렬 되지 않은 부분
    // 시간 복잡도 O(n^2)
 
    // 배열의 요소를 교환 해주는 메소드.
    public void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
 
    void selectionSort(int arr[]) {
    
        int min;
 
        for (int i = 0; i < arr.length - 1; i++) {
            // 정렬 되지 않은 부분의 첫번째의 인덱스 값을 최솟값(또는 최대)으로 설정한다.
            min = i;
            // 정렬 되지 않은 부분의 최소 요소를 찾는다.
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > arr[i]) {
                    min = j;
                }
                // 정렬 되지 않은 부분의 첫인덱스와 최소요소를 교환한다.
                swap(arr, j, i);
            }
        }
    }
cs









이진탐색(Binary search) 알고리즘

이진탐색은 배열을 이분화 하면서 탐색하는 방법입니다.
선형 탐색의 느린 탐색을 보안한 방법으로 배열의 중간 값을 비교해 절반을 제외 시키는 방법으로 탐색을 진행합니다.
때문에 정렬 된 데이터에서만 사용 할 수 있습니다.

그럼 아래의 정렬된 배열에서 78 이라는 값을을 찾아 보도록 하겠습니다. 
        LEFT                                                                                                                                                                                                                  RIGHT

1

12

23

34

45

56

67

78

 89

 100

가장 먼저 해야 하는 일은 배열의 중간 값을 찾는 일 입니다. 중간 값(MID)는 MID=LEFT+(RIGHT-LEFT)/2 로 계산하고 LEFT와 RIGHT는 각각 제외되지 않은 배열의 첫 인덱스와 끝 인덱스 입니다.  따라서 주어진 배열의 중간 값은 0+(9-0)/2 = 4.5 ≒ 5 번 인덱스 입니다.

        LEFT                                                                                                                  MID                                                                                          RIGHT

1

12

23

34

45

56

67

78

 89

 100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]

5번 인덱스의 값 56과 찾으려는 값 78를 비교합니다. 찾는값이 중간값보다 크므로(78>56) 배열의 왼쪽 절반을 무시합니다. 제외되지 않은 배열에서 LEFT와 RIGHT 그리고 MID 값을 찾습니다. 6+(9-6)/2= 7.5 ≒ 8 번 인덱스 입니다.
                                                                                                                                                         LEFT                                          MID                  RIGHT

1

12

23

34

45

56

67

78

 89

 100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]


8번 인덱스의 값 89와 찾으려는 값 78을 비교합니다. 찾는 값이 중간값보다 작으므로(78<89) 배열의 오른쪽 절반을 무시합니다. 다시한번 제외되지 않은 배열에서  LEFT와 RIGHT , MID 값을 찾습니다. 6+(7-6)/2 - 6.5 
≒ 7 번 인덱스 입니다.

                                                                                                                                                         LEFT            MID&RIGHT

1

12

23

34

45

56

67

78

 89

 100

              [0]                            [1]                            [2]                            [3]                            [4]                            [5]                            [6]                            [7]                            [8]                            [9]

7번 인덱스의 값 78은 찾으려는 값 78과 일치하므로 7번 인덱스에서 원하는 값을 찾을 수 있습니다. 3번의 탐색으로 원하는 값을 찾을 수 있었습니다. 동일한 배열에서 선형탐색이 8번의 탐색을 필요로 하는 것에 비하면 매우 좋은 성능을 가짐을 알 수 있습니다. 또한 자료의 수가 매우 커지면 그 차이는 더욱 커집니다.

다음은 재귀함수로 구현한 이진탐색입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    // 이진 탐색을 위해서는 배열이 정렬 되어있어야 한다.
    // arr [] 배열의 중간 값(mid)과 찾는값 (x)를 비교해 배열의 절반을 무시하는 방식으로 진행한다. 
    // 찾는 값이 존재하면  위치한 배열의 인덱스를 반환한다. 만약 찾는 값이 없다면 -1을 반환한다.
    // 시간 복잡도 O(Logn)
        
    public int search(int[] arr, int left, int right, int x) {
        
        if (right >= left) {
            int mid = left + ((right-left)/ 2);
            
            //찾는 값(x)과 배열의 요소가 일치하면 배열의 인덱스를 반환한다.
            if (arr[mid] == x)
                return mid;
            //찾는 값(x)보다 배열의 요소가 크다면 배열의 오른쪽 절반을 무시한다.
            if (arr[mid] > x)
                return search(arr, left, mid-1, x);
            //찾는 값(x)보다 배열의 요소가 작다면 배열의 왼쪽 절반을 무시한다.
            return search(arr, mid+1, right, x);
        }
        //일치하는 값 없음.
        return -1;
    }
 
cs


'알고리즘/자료구조 > Searching' 카테고리의 다른 글

선형탐색(Linear search) 알고리즘  (0) 2016.02.29

선형탐색(Linear Search) 알고리즘

선형 탐색이란 일렬로 된 자료를 처음부터 마지막까지 순서대로 탐색하는 방법입니다. 
가장 간단하고 직접적인 방법이며 정렬을 필요로 하지는 않지만 최악의 경우 배열 전체를 탐색해야 하므로 탐색 속도가 매우 느립니다. 
때문에 자료의 수가 적은 경우나 탐색이 빈번하지 않을경우에 적용 할 수 있습니다.

선형 탐색은 다음과 같이 구현 할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    // 선형탐색의 경우 정렬의 여부는 중요하지 않다.
    // arr [] 배열의 처음부터 끝까지의 원소 값과 찾으려는 값(x)을 비교해 
    // 찾으려는 값이 위치한 배열의 인덱스를 반환한다. 만약 찾으려는 값이 없다면 -1을 반환한다.
    // 시간복잡도 O(n)
    
        
    int search(int[] arr, int x) {
        int size = arr.length;
        for (int i = 0; i < size; i++) {
            //배열을 순차적으로 탐색해 찾는 값(x)과 일치하는지 확인한다.
            if (arr[i] == x)
                return i;
        }
        //일치하는 값 없음.
        return -1;
    }
cs



'알고리즘/자료구조 > Searching' 카테고리의 다른 글

이진탐색(Binary search) 알고리즘  (0) 2016.03.01

+ Recent posts