구현) 정렬

 

 

선택 정렬 

- 어떤 정해진 위치에 들어갈 원소를 선택하는 정렬 

 

 

- in-place 정렬 중 하나다. 

 

in-place정렬이란 입력 배열 외에 추가적인 메모리가 필요없는 정렬을 의미한다. 

 

공간 복잡도 O(1)

 

 

- 시간복잡도 항상 O(N^2)

  왜냐하면 원소를 선택하기 위해 모든 원소를 검사하기 때문이다. 

 

    static void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
    static void selectionSort() {
        // 최소 원소가 들어갈 위치 
        for(int place = 0 ; place < arr.length-1 ; place++ ) {
            int smallest = place;
            // 최소 원소 찾기
            for(int check = place+1 ; check < arr.length ; check++) {
                if(arr[smallest] > arr[check])
                    smallest = check;
            }
            // place로 최소 원소 이동 
            if(smallest != place) {
                swap(smallest, place);
            }
        }
    }

 

 

 

 

 

버블 정렬

- 인접한 원소끼리 swap되어 뒤 부터 정렬된다.

 

- 버블: 원소 swap이 물에서 공기가 수면으로 올라가는 것같다고 하여 지어진 이름이다. 

 

- in place 정렬 중 하나 => 공간 복잡도 O(1)

 

- 단점 : 제일 뒤로 옮겨갈 원소가 아니어도 swap 되서 필요없는 swap 연산이 발생한다. 

안그래도 N^2인데 swap때문에 다른 알고리즘 보다 더 느리다. 

 

- 시간 복잡도 항상 O(N^2)

 

    static void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
    static void bubbleSort() {
        
        // end는 swap검사할 인덱스의 경계 역할 
        for(int end = arr.length-1 ; end > 0 ; end-- ) {
            // bubble~ 가장 큰 원소가 제일 뒤로 이동된다.  
            for(int i = 0 ; i < end ; i++) {
                if(arr[i] > arr[i+1]) {
                    swap(i, i+1);
                }
            }
        }
    }

 

 

 

 

삽입 정렬 

- 손 안에 카드를 정렬하는 것과 같다. 

  손 안에 이미 정렬된 카드에 새로운 카드를 올바른 위치에 삽입 

 

- in place 정렬 => 공간 복잡도 O(1)

 

- 삽입해야할 원소를 이미 정렬된 원소들 사이에 넣어 정렬된 상태를 유지

 

- 이미 정렬되어 있는 경우, Best O(N) 

   왜냐하면, 삽입한 원소의 현재 위치가 이미 정렬되어 있기 때문이다. 

 

- 평균, 최악 O(N^2)

 

- 다른 in place 정렬인 선택정렬, 버블정렬보다 빠른 편이다. 

 

    static void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
    static void insertionSort() {
        // insert할 원소
        for(int insert = 1 ; insert < arr.length ; insert++) {
            // 원소가 자기 자리를 찾을 때까지 swap 
            for(int i = insert ; i > 0 ; i--) {
                if(arr[i-1] > arr[i]) {
                    swap(i-1, i);
                }else {
                    // 이동 못하면 원소 위치를 찾은 것으로 break
                    break;
                }
            }
        }
    }
 

 

 

+ 선택 정렬, 버블 정렬, 삽입 정렬은 안정 정렬에 속한다. 

 

(구현에 따라 불안정 정렬이라고 하는 글도 있지만.. 안정 정렬이 맞다고 생각함)

swap 조건의 미만/이하 차이때문 

 

안정 정렬이란, 동일한 값들의 순서가 정렬 후에도 순서가 동일한 것을 의미한다. 

 

 

 

 

 

퀵 정렬

분할정복 정렬

1 divide : 임의의 pivot을 기준으로 배열을 pivot보다 작거나 큰 값들로 나눈다. 

 

2 conquer : 부분 배열을 정렬한다. 크기 1까지 나뉘어진 배열은 이미 정렬 상태다.

 

3 partition : 임의의 배열 값 pivot을 기준으로 왼쪽은 pivot보다 작은 값들, 오른쪽은 큰 값들을 둔다.

pivot에 따라 worst, best 시간 복잡도가 달라진다. 

 

 

불안정 정렬

소팅 전의 동일한 값들의 순서가 소팅 후 달라 질 수 있다. 

 

 

시간 복잡도 

평균, 최선 :  O(NlogN)

다른 빠른 알고리즘도 O(NlogN)이지만, 퀵 소트는 좀 더 빠르다. 

왜냐하면, 소팅 과정에서 적어도 원소 하나가(pivot) 정렬되어 이후 정렬할 개수가 줄어들기 때문이다. 

 

최악 : O(N^2)

피봇을 최대/최소로 잡는 경우

 

 

공간 복잡도 

평균, 최선 O(logN)

 

최악 O(N)

분할 시, 한 쪽이 1개인 경우 

 

 

합병 정렬과 차이점! 

퀵 정렬은 divide과정에서 O(N)이며, 병합 과정은 따로 없다. 

 

합병 정렬은 divide 과정이 O(1)이며 합병 과정에서 O(N)시간이 걸린다. 

 

즉 시간이 많이 걸리는 작업이 어디서 진행되냐에 따라 다르다. 

 

 

 

구현 방법 1

 

    static void quickSort2(int start, int end) {
        
        if(end - start <= 1) {
            return;
        }
        
        int pivotIndex = partition2(start, end);
        quickSort(start, pivotIndex-1);
        quickSort(pivotIndex+1, end);
        
    }
    
    static int partition2(int start, int end) {
        
        /*
         *  pivot을 마지막으로 옮겨둔다.
         *  왜냐하면, 함수 마지막에 피봇의 위치를 small_pos를 이용해 리턴해줘야하기 때문이다.
         *  pivot을 end로 잡으면 굳이 swap할 필요는 없다.  
         */
        int pivot = arr[(end+start)/2];
        swap(end, (end+start)/2);
        
        int small_pos = start;
        
        // pivot '이하'만 small영역으로 스왑시킨다. 
        for(int i = start ; i <= end ; i++) {
            if(arr[i] <= pivot) {
                swap(i, small_pos);
                small_pos++;
            }
        }
        
        // small_pos는 small 영역 바로 다음이기 때문에 -1을 리턴 
        return small_pos - 1;
    }
    
    static void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

 

 

 

구현 방법 2

part1과 part2로 나누는 방법 

하지만 이 방법은 구현 방법 1보다 조금 더 걸린다. 왜냐하면 피봇의 위치가 정해지지 않기 때문이다. 

 

    static void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
    static int partition(int start, int end) {
        int pivot = arr[(start + end)/2];
        
        /* 
         *  partition은 part1 과 part2로 나눈다. 
         *  start는 part2의 시작이 되고, end는 part1의 끝이 될때까지 아래 반복문이 반복한다. 
         */
        while(start <= end) {
            while(arr[start] < pivot) start++;
            while(arr[end] > pivot) end--;
            /*
             * start는 pivot과 같거나 크다. 
             * end는 pivot과 같거나 작다. 
             */
            
            if(start <= end) {
                swap(start, end);
                start++;
                end--;
            }
        }
        
        // start와 end가 서로의 범위를 벗어남. 그래서 start는 part2의 시작 포인터가 된다. 
        return start;
    }
    
    static void quickSort(int start, int end) {
        // 원소가 2개 이상일때만. 
        if(start < end) {
            int part2 = partition(start, end);
            quickSort(start, part2-1);
            quickSort(part2, end);
        }
    }

 

 

추가로 K 번째 원소를 찾는 알고리즘에 응용할 수 있다. 

https://modoocode.com/287

모두의 알고리즘 - 2 - 4. k 번째 원소를 찾는 알고리즘 - QuickSelect

 

 

 

 

 

합병 정렬

분할 정복 알고리즘 중 하나 

 

크기 1까지 일단 분할한다. 

그리고 part1과 part2를 합치면서 정렬한다. 

part1과 part2는 이미 각 영역에서 정렬된 상태 

 

divide : 배열을 반으로 나눈다. O(1)

 

conquer : 부분 배열을 이용하여 정렬한다. 크기 1까지 나뉘어진 배열은 이미 정렬 상태다.

 

combine : devide 후 정렬된 두 부분 배열을 합친다. O(N)

 

 

장단점 

장점 : 최악에서도 O(NlogN)으로 동작한다.

단점 : 추가적인 임시 배열이 필요하다. ( in place가 아님 )

또한, 값이 너무 많아지는 경우 swap연산 때문에 시간이 더 걸릴 수 있다.

(대안으로 linkedlist로 줄일 수 있다고 한다. )

 

 

시간 복잡도 

최선, 최악, 평균 : O(nlogn)

 

 

공간 복잡도

merge에서 생성한 tmp 배열 -> O(N)

 

 

 

외부 정렬 방식의 하나다.
외부 정렬이란?
데이터의 크기가 주기억장소보다 클 경우 외부 기억장치(디스크, 테이프 등)을 사용하여 정렬하는 방식이다.

 

 

    static void merge(int[] tmp, int start, int mid, int end) {
        for(int i = start ; i <= end; i++) {
            tmp[i] = arr[i];
        }
        
        int part1 = start;
        int part2 = mid+1;
        int index = start;
        
        while(part1 <= mid && part2 <= end) {
            if(tmp[part1] < tmp[part2]) {
                arr[index] = tmp[part1];
                part1++;
            }else {
                arr[index] = tmp[part2];
                part2++;
            }
            index++;
        }
        
        for(int d = 0 ; part1 + d <= mid ; d++) {
            arr[index] = tmp[part1+d];
            index++;
        }
        
    }
    static void mergeSort(int[] tmp, int start, int end ) {
        if(start >= end)
            return;
        
        int mid = (start + end)/2;
        // 배열을 part1 과 part2로 나누어 정렬시킨다. 
        // part1 범위는 start ~ mid  mid - 1로 해야할지 헷갈렸었다. 
        mergeSort(tmp, start, mid);
 
        // part2 범위는 mid + 1 ~ end
        mergeSort(tmp, mid+1, end);
        merge(tmp, start, mid, end);
        
    }

 

 

 

 

 

힙 정렬

자료구조 heap을 이용한 정렬 

 

 

시간 복잡도

평균, 최선, 최악 O(nlogn)

 

 

공간 복잡도

in place이기 때문에 O(1)

 

 

heap 이란? 

complete binary tree 기반

 

최대, 최소를 쉽게 찾을 수 있는 자료구조 

 

큰 값(또는 작은 값) 일 수록 위에 위치한다. 

 

 

heapify 란?

heap 성질을 만족하도록 하는 연산 

 

parent와 child 관계만 고려하면 된다. 형제끼리는 상관없다. 

 

필요에 따라 현재 노드에서 위 또는 아래로 heapify를 하면 된다. 

 

ex)

아래로 heapify : 아래부터 검사하는 buil heap 생성 시, root 값 제거 시

위로 heapify : heap에 제일 마지막에 새로운 값 추가 시 

 

 

 

과정 

1. 정렬할 배열을 heap 구조로 만든다. 

 배열을 heap에 하나하나 insert해도 되지만, O(nlgn)시간이 걸린다. 

 

( 또한, swap 연산 때문에 데이터가 많아질 경우 시간이 더 오래걸린다. )

 

반면, 배열에서 가장 아래 노드부터 heapify를 하며 올라가며 heap 구조를 만드는 방식이 있다.

 

build heap 시간 복잡도

모든 층에 대해 (현재 높이) x (노드 수)

 

아래에서 부터 heapify를 하면 노드 수는 많지만 높이 낮고, 위로 올라갈 수록 노드 수는 적어진다. 

 

완전 이진 트리 특성을 고려하면, O(n) 시간이 걸린다. 

 

 

 

 

 

2. heap에서 최대/최소를 빼서 배열 뒤로 옮긴다. 

in place 이기 때문에 마지막부터 정렬된다. 

 

또한, size 변수를 둬서 정렬된 곳은 접근하지 못하게 둔다. 

 

 

3. heap은 다시 heapify를 거쳐 heap 자료구조를 유지한다. 

 

 

heap vs binary search tree

heap은 parent에 최대/최소가 있고, bst는 parent 값 기준으로 left, right children이 나뉜다.

 

그래서 heap는 최대 최소 구하는데, bst는 탐색에 강점이 있는 자료구조다. 

 

 

    static void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
    static void heapify(int cur, int size) {
        int p = cur;
        int left = cur * 2 + 1;
        int right = cur * 2 + 2;
        
        if(left < size && arr[left] > arr[p]) {
            p = left;
        }
        
        if(right < size && arr[right] > arr[p]) {
            p = right;
        }
        
        /*
         *  chideren 값 > parent 값
         *  swap 후, 아래 children에서 다시 heapify  
         */
        if(p != cur) {
           swap(p, cur);
            heapify(p, size);
        }
    }
    
    static void heapSort() {
        int size = arr.length;
        
        /*
         *  heap init
         *  가장 마지막 레벨부터 heapify 
         */
        for(int i = size/2 - 1 ; i >= 0 ; i--) {
            heapify(i, size);
        }
        
        /*
         *  root 값을 뒤로 빼고 정렬 정렬 
         */
        while(size > 0) {
            size--;
            swap(0, size);
            heapify(0, size);
        }
    }

 

 

 

 

 

 

참고 

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

https://goodgid.github.io/Data-Structure/#%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/

https://d2.naver.com/helloworld/0315536