[알고리즘] Sorting Algorithm(1)

정렬 알고리즘

 

 정렬 알고리즘은 n개의 input이 주어졌을 때, 이것들을 특정한 기준을 정해(오름차순, 내림차순) 정렬하여 출력하는 알고리즘이다. 효율적인 정렬은 데이터의 정규화를 통해 정렬된 상태에서 사용 가능한 다른 알고리즘을 수행하기 위해 필요하다. 이러한 정렬 알고리즘은 여러 종류가 있으며, 그 방법에 따라 다양한 수행시간을 가진다. 대부분 O(nlgn)과 O(n^2) 사이의 시간복잡도를 가지지만, input이 특수한 성질을 만족하는 경우에는 O(n) sorting도 가능하다.

 

1. Selection Sort

 

범위 내의 최소/최대값을 선택해서 한쪽으로 열외시키는 것 반복

 

 

 선택정렬은 배열을 한쪽 방향부터 정렬하는 제자리 정렬 알고리즘이다. 제자리 정렬 알고리즘이란 input에 필요한 메모리 외에 추가적인 메모리를 크게 필요로 하지 않는 알고리즘을 말한다. 

//pseudo code
selectionSort {
	for(n:last...2) {
    	A[1...last] 중 가장 큰 값을 가지는 A[k]를 찾는다;
        A[k]와 A[n]을 교환한다
    }
}

 

    public int[] selectionSort(int[] arr) {
        int largest;
        int tmp;
        for(int i=arr.length-1; i>=0; i--) {
            largest=0;
            for(int j=0; j<=i; j++) {
                if (arr[j] > arr[largest])
                    largest=j;
            }
            swap(arr, i, largest);
        }
        return arr;
    }
        
    private void swap(int[] arr, int i, int j) {
    	int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

제일 큰 index부터 찾아 배열의 맨 뒤부터 정렬하는 알고리즘이다. 한 번의 loop를 수행하고 나면 가장 큰 원소가 배열의 지정한 범위 맨 뒤에 놓이며, 그 다음 loop에서는 그 원소를 제외한 나머지 중에서 가장 큰 원소를 찾는다. 유사하게 작은 index부터 찾아 배열의 맨 앞부터 정렬 할 수도 있다. 

배열의 구조에 상관없이 전체 원소에 대해서 두번의 반복문을 가지고 비교를 시행하므로 O(n^2)의 시간복잡도를 가진다.

 

 

2-1. Bubble Sort

 

좌우를 비교해가면서 순서가 올바르지 않다면 swap

 

 

 버블정렬은 서로 인접한 두 원소를 비교해가면서 정렬해나가는 제자리 정렬 알고리즘이다. 

//pseudo code
bubbleSort {
	for(n:last...2) {
    	for(i:i...last-1) {
        	arr[i]>arr[i+1]이라면 교환
    }
}

 

    public int[] bubbleSort(int[] arr) {
        int tmp;
        for(int i=arr.length-1; i>=0; i--) {
            for(int j=0; j<i; j++) {
                if(arr[j]>arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
        return arr;
    }

 버블 정렬은 인접한 index끼리 서로 비교하고 교환하는 과정을 반복한다. 한 번의 loop가 끝나면 가장 큰 원소는 뒤로 이동하게 되고, 다음 loop에서는 그 원소를 제외한 나머지 원소들 사이에 비교/교환을 반복한다. 

버블정렬도 배열의 구조에 상관없이 모든 원소를 비교/교환하기 위해 두개의 loop를 필요로 하므로 O(n^2)의 시간복잡도를 갖는다.

 

 

2-2. Exchange Sort

교환정렬은 선택된 인덱스와 나머지 인덱스를 비교하여 자신보다 작은 경우 계속 교환하여 가장 작거나 큰 인덱스를 위치시키는 방법이다. 버블정렬과 비교하면 고정된 인덱스를 정해서 큰 loop내에서는 해당 원소랑만 교환이 이루어지므로 차이점을 가진다. 

 

//pseudo code
exchangeSort {
	for(n:last...2) {
    	for(i:i...last-1) {
        	arr[i]>arr[n]이라면 교환
    }
}

 

    public int[] exchangeSort(int[] arr) {
        int tmp;
        for(int i=arr.length-1; i>=0; i--) {
            for(int j=0; j<i; j++) {
                if(arr[i]<arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
        return arr;
    }

버블정렬과 비슷하게 배열의 정렬 상태에 상관없이 모든 원소를 비교/교환해야 하므로 O(n^2)의 시간복잡도를 가진다.

 

 

 

2-3. BubbleSort - 최적화

그런데 버블정렬의 경우 선택정렬과 교환정렬과는 다르게, 배열에서 인접한 모든 원소들간의 관계를 비교한다. 달리 생각해보면 인접한 모든 원소들 사이에 교환이 이루어지지 않았다면, 배열이 이미 내림차순 또는 오름차순으로 정렬되어있다는 말이므로 즉시 정렬을 종료해도 된다는 말이다.

그래서 교환여부를 판단할 수 있는 변수를 두어 큰 루프 내에서 교환이 이루어지지 않았다면 바로 정렬을 종료할 수 있게 만들어보았다.

    public int[] bubbleSort(int[] arr) {
        int tmp;
        int cnt=0;
        boolean isSwapped;
        for(int i=arr.length-1; i>=0; i--) {
            isSwapped = false;
            for(int j=0; j<i; j++) {
                if(arr[j]>arr[j+1]) {
                    isSwapped = true;
                    swap(arr, j, j+1);
                }
            }
            if(!isSwapped) {
                System.out.println(cnt+"번째 loop에 종료되었습니다.");
                return arr;
            }
            cnt++;
        }
        return arr;
    }

 

//main함수 일부   
        
        int[] arr = {2,3,1,4,5,6,7,8,9,10};

        arr = sort.bubbleSort(arr);

        for(int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");

 

이렇게 개선하면 이미 정렬이 되어있는 코드일 경우 Best-case의 경우 O(N), Worst-case의 경우 O(n^2)의 시간복잡도를 가질 것이다.

 

3. Insertion Sort

 

하나씩 골라서 정렬된 범위 내의 적절한 위치로 삽입

 

 

 삽입 정렬이란, 배열의 input을 이미 정렬된 부분과 비교하여 자신의 위치를 찾아서 삽입하는 알고리즘이다. index가 자신의 자리를 찾았다면, input이 리스트가 아닌 배열형태로 저장되었으므로, 뒤에 위치한 원소들을 한 칸씩 뒤로 이동시키는 작업을 해주어야 한다. 또한, 비교대상이 존재해야 하므로, 배열의 첫번째 원소를 놔두고 두번째 원소부터 비교/삽입과정이 진행된다. 

//pseudo code
insertionSort {
	for(i:2...n)
    	arr[1...i]의 적당한 자리에 arr[i] 삽입
        //배열 인덱스에 삽입하는것은 구현이 복잡해지므로 swap을 활용
}

 

    public int[] insertionSort(int[] arr) {
        int k;
        int index;
        for(int i=1; i<arr.length; i++){
            index = i;
            k = arr[i];
            //i-1번째부터 0번째 인덱스까지 k와 대소비교후 arr[i]이 들어갈 자리만들기 (k보다 큰 인덱스들을 오른쪽으로 이동시킴)
            for(int j=i-1; j>=0 && arr[j]>=k; j--) {
                arr[j+1] = arr[j];
                index = j;
            }
            arr[index] = k;
        }
        return arr;
    }

조건문을 포함하는 대신 for문의 반복조건에 조건을 달아서 arr[i]가 들어갈 자리가 만들어지도록 코드가 구성됨.

삽입정렬도 두번의 loop를 실행하고 안쪽에서도 배열의 재정렬이 이루어지므로 O(n^2)의 복잡도를 갖는다. 하지만 배열이 이미 정렬되어있는 경우, 두번째 for문이 arr[j]>=k라는 조건에 막혀 실행되지 않으므로 best-case에는 O(n)의 시간복잡도를 갖는다고 말할 수 있다.