정렬

카운팅 정렬

Counting Sort(계수 정렬)은 숫자들의 대소 비교를 하지 않고 나오는 횟수를 가지고 정렬을 하는 알고리즘 방법이다.
숫자가 몇 개 나오는지 센 다음 정렬을 한다. 그래서 시간 복잡도는 O(n)이 나오게 된다. 이번에 카운팅 정렬이라는 것을 처음 보았다. 퀵 정렬, 힙 정렬들의 시간 복잡도는 일반적으로 O(nlogn)으로 정렬 중에 이보다 더 작아질 수 없다고 배웠는데 O(n) 정렬이 있었던 것이다. 

• index를 가지고 정렬을 함
• 배열의 값은 count의 index로 사용됨. 
• count의 값은 배열의 값이 몇 번 나왔는지 횟수를 의미.
• count 배열의 값을 누적합으로 변환시킴(이유는 아래에서)
• count 배열의 값 - 1은 res 배열에서 index를 나타내고, 
• count 배열의 index는 res 배열의 값을 뜻한다. 
• 시간 복잡도 : O(n)

 

---

 

카운팅 정렬에서 누적합을 구하는 이유

결과론적으로 얘기하면 안정 정렬을 구현하기 위해서이다.

카운팅 정렬을 공부하면서 굳이 누적합을 구하는 이유가 너무 궁금해서 구글링을 해도 이해가 가질 않아 오카방을 이용해 궁금증을 해소했다. 만약 누적합을 하지 않고 단지 count배열에 index값으로 숫자를, 해당 index값으로 숫자의 개수를 입력한 다음, 해당 index값이 0이 될 때까지 출력하면 된다고 생각했다. 하지만 그렇게 하면 Stable sort를 하지 못하기 때문이다.

stable sort(안정 정렬)이란 정렬 전에 데이터의 순서가 정렬 후에도 유지되는 것을 말한다. 그래서 누적합을 이용하면 같은 숫자라도 누적합이 더 큰 숫자가 뒤에 있다는 뜻이 되므로, 이러한 원리를 통해 누적합을 구하는 것 같다.

 

 

---

 

카운팅 정렬 조건

주어진 수가 0과 양의 정수이어야 한다.

 --> 왜냐? 배열의 index를 이용해야하는데 index값은 0과 양의 정수만 가능하기 때문

 

 

---

 

코드

class CountingSort {
    static int[] arr = {2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2};
    public static void main(String[] args) {
        int count[] = new int[10];
        int res[] = new int[arr.length];
 
        //count의 index는 arr의 값이 되고
        //count의 value는 arr의 각 값들의 횟수가 됨
        for(int i = 0; i < arr.length; i++){
            count[arr[i]]++;
        }
 
        //안정 정렬을 위해 count의 누적합을 계산함.
        for(int i = 1; i < count.length; i++){
            count[i] += count[i-1];
        }
 
        //res배열의 value는 count의 index가 되고
        //res배열의 index는 count의 value-1이 됨
        //안정성 보장을 위해 array의 마지막 index부터 탐색
        for(int i = arr.length - 1; i >= 0; i--){
            int value = arr[i];
            count[value]--;
           res[count[value]] = value;
        }
 
        for(int index : res)
            System.out.print(index + " ");
    }
}

 

카운팅 정렬 참고 사이트 : st-lab.tistory.com/104

---

 

버블 정렬

• 순차 탐색을 하면서 i번째와 i+1번째의 값을 비교함
• i번째가 크다면 둘의 자리를 바꿈
• 탐색을 n번 하게 되는데, 탐색이 끝날 때마다 제일 뒤에 있는 index는 탐색하지 않아도 됨
• 시간 복잡도 : 최선, 최악 모두 O(n^2)
• 안정 정렬

 

---

 

코드

class BubbleSort {
    public static void main(String[] args) {
        int [] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
 
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr.length - i - 1; j++){//위 j부분이 제일 뒤에 있는 index 탐색 X
                if(arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for(int index : arr)
            System.out.print(index + " ");
    }
}
 

---

 

선택 정렬

• 순차 탐색을 하면서 가장 작은 값을 가진 index를 구함
• 시작한 index와 가장 작은 값을 가진 index를 swap함
• 시간 복잡도 : 최선, 최악 모두 O(n^2)
• 불안정 정렬

 

---

 

코드

class SelectionSort {
    public static void main(String[] args) {
        int [] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
 
        for(int i = 0; i < arr.length-1; i++){
            int min_index = i; //시작하는 index를 기준으로 한다.
 
            for(int j = i+1; j < arr.length; j++){
                if(arr[min_index] > arr[j]){
                    min_index = j; //원소 중에 가장 작은 값을 가진 index를 구함
                }
            }
            //시작한 index와 가장 작은 값을 가진 index를 swap함
            int temp = arr[min_index];
            arr[min_index] = arr[i];
            arr[i] = temp;
        }
        for(int index : arr)
            System.out.print(index + " ");
    }
}
 

---

 

삽입 정렬

• 기준 index를 설정하여, 그 이전 index들과의 값을 비교함
• 이전 index가 기준 index보다 크게 되면 이전 index를 뒤로 옮김
• 그래서 삽입 정렬은 기준 index 왼쪽은 모두 정렬돼있음
• while문이 끝나면( 이 말은 이전 값보다 기준 값이 크다면) 비교를 하기 위해 j--을 했기 때문에 pos값을 넣으려면 j+1을 해주어서 넣어야 함.
• 시간 복잡도
  • 최선 : 정렬되어 있는 경우 가장 빠르다.
    • n-1번의 비교 2번의 이동 --> 2(n-1) --> O(n)
  • 최악 : 역으로 정렬된 경우. O(n^2)
• 안정 정렬

 

---

 

코드

class InsertionSort {
    public static void main(String[] args) {
        int [] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
 
        //Insertion Sort는 기준 왼쪽 값들은 모두 정렬되있음
        for(int i = 1; i < arr.length; i++){
            //pos는 시작점을 의미함. 즉, 기준
            int pos = arr[i];
 
            //j는 pos 이전의 값들을 비교하기 위한 변수
            int j = i - 1;
 
            while(j >= 0 && arr[j] > pos){
                //기준점에서 앞의 것들이랑 비교하다가 앞이 크면 뒤로 옮김
                arr[j+1] = arr[j];
                //옮기고 난 후 그 앞을 비교해야하므로 j--을 함
                j--;
            }
 
            //항상 값을 비교할 때는 j--를 하므로 결국 while문이 끝나면 그 다음 index에 pos값을 넣어줘야함.
            arr[j+1] = pos;
        }
        for(int index : arr)
            System.out.print(index + " ");
    }
}

 

 

---

 

병합 정렬

• 분할하고, 정복을 하는 단계임
• 배열을 두개로 나눠서 따로 정렬을 한 뒤에, 두 배열을 합침
  • 배열을 최대한 작게 쪼개고 난 후, 정렬을 하고 합침.
• 기본적으로 분할 정복 알고리즘 기반
• 비교 정렬이며, 정렬의 대상이 되는 공간 이 다른 공간이 필요해서 제자리 정렬이 아님.
• 안정 정렬
• 시간 복잡도 : 최선, 최악 모두 O(nlogn)
  • 분할할 때, 최대 깊이가 log(n)이고, n번 실행하니 nlogn임.

 

---

 

코드

class MergeSort {
    static int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    static int[] result;
 
    public static void main(String[] args) {
        result = new int[arr.length];
 
        mergesort(0, arr.length - 1);
        for (int index : result) {
            System.out.print(index + " ");
        }
    }
 
    public static void mergesort(int start, int end) {
        //여기서 start == end로 해도 된다.
        //왜냐하면 재귀함수를 모두 손으로 써보게 되면 start > end인 경우는 없고
        // 모두 start == end에서 끝나게 된다.
        //처음에 왜 start >= end가 아니라 start == end로 했는지 궁금했었음 그래서 해결됨
        
        if (start >= end) return;
        int mid = (start + end) / 2;
        mergesort(start, mid);
        mergesort(mid + 1, end);
 
        int left = start; // 왼쪽 리스트의 시작점
        int right = mid + 1; // 오른쪽 리스트의 시작점
        int idx = left;
 
        //왼쪽 시작점이 mid보다 작거나 같고,
        //오른쪽 시작점이 end보다 작거나 같을 때 실행
        while (left <= mid && right <= end) {
 
            //왼쪽과 오른쪽 리스트의 값을 각각 비교하여 작은 것 부터 넣음
            if (arr[left] <= arr[right]) {
                result[idx++] = arr[left++];
            } else {
                result[idx++] = arr[right++];
            }
 
        }
 
        //만약에 왼쪽 리스트를 이미 다 쓸 경우에는
        //오른쪽 리스트가 end를 넘지 않는 선에서 다 넣음
        //왜냐하면 각각의 리스트는 이미 정렬되어 있기 때문
        if (left > mid) {
            while (right <= end) {
                result[idx++] = arr[right++];
            }
        } else {
            while (left <= mid) {
                result[idx++] = arr[left++];
            }
        }
 
        for (int i = start; i <= end; i++) {
            arr[i] = result[i];
        }
 
    }
}

---

 

병합 정렬 재귀 함수 직접 손으로 작성

 

 

---

 

퀵 정렬

• 병합 정렬은  리스트를 절반으로 나눠서 분할 정복
• 그러나 퀵 정렬은 pivot의 값에 따라 분할 정복
  • pivot의 값보다 작은 값, 큰 값으로 나눔(그래서 병합과 다르게 비균등)
• 불안정정렬
• 병합 정렬과 다르게 제자리 정렬임
• 자바 api를 보면, Arrays에서 사용하는 sort는 퀵 정렬을 사용함.
• 시간 복잡도 : pivot의 선택에 따라 달라짐
  • 최선 : O(nlogn)
  • 최악 : O(n^2) --> pivot 값을 기준으로 분할하는 중에, 값들이 한 편으로 치우치게 될 때

 

---

 

코드

class QuickSort {
    static int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
 
    public static void main(String[] args) {
        quickSort(0, arr.length-1);
 
        for(int index : arr)
            System.out.print(index + " ");
    }
    
    public static void quickSort(int start, int end) {
        if (start >= end) return;
 
        int left = start;
        int right = end;
        int pivot = arr[(start + end) / 2];
 
        while (left <= right) {
            //pivot의 왼쪽에 있으면서 pivot보다 큰 수를
            //찾기 위해서 사용
            //아래 pivot보다 오른쪽에 있지만 작은 수와 자리를
            //바꾸기 위해서임
            while (arr[left] < pivot) {
                left++;
            }
 
            //pivot의 오른쪽에는 pivot보다 커야함
            //그래서 pivot보다 작은 수를 찾기 위함임
            //pivot보다 작은 수를 찾으면 그대로 멈춤.
            //왜냐하면 pivot보다 왼쪽에 있는데 큰 수와 자리를 바꾸려고
            while (arr[right] > pivot) {
                right--;
            }
 
            //pivot의 왼쪽 배열에서 pivot보다 큰 값
            //pivot의 오른쪽 배열에서 pivot보다 작은 값
            //둘의 자리를 바꿔준다는 것임.
            if (left <= right) {
                swap(left, right);
                left++;
                right--;
            }
        }
 
        //pivot보다 작은 부분을 재귀
        if (start < right) quickSort(start, right);
 
        //pivot보다 큰 부분을 재귀
        if(end > left) quickSort(left, end);
    }
 
    public static void swap(int x, int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}
 

---

 

힙 정렬 : https://st-lab.tistory.com/225?category=892973