[알고리즘] 정렬 알고리즘

728x90

1) 버블 정렬

시작	5	3	2	1	4
1회차	3	2	1	4	5
2회차	2	1	3	4	5
3회차	1	2	3	4	5
4회차	1	2	3	4	5

가장 기본적인 정렬 중 하나이다. 인접한 i번째 키와 i+1번째 키를 비교하여 교환한다.
즉 1, 2번째 키를 비교하고, 2,3번째 키를 비교하여 정렬한다.
이러한 방식은 자연스럽게 가장 큰 값을 가장 뒤로 정렬하게 된다.
시간복잡도는 평균과 최악 모두 n^2 으로 같으며, 사용 메모리는 n이다.

public class HelloWorld{

     public static void main(String []args){
         int[] nums = {2, 3, 6, 1, 4, 9, 10};
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
         
         bubbleSort(nums);
         
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
     }
     
     public static void bubbleSort(int[] nums) {
         for(int i=0; i<nums.length; i++) {
             for(int j=0; j<nums.length - i - 1; j++) {
                 //0~7, 0~6, 0~5 ... 0~1
                 if(nums[j] > nums[j+1]) {
                     int tmp = nums[j];
                     nums[j] = nums[j+1];
                     nums[j+1] = tmp;
                 }
             }
         }
     }
}

2) 선택정렬

시작	5	3	2	1	4
1회차	1	3	2	5	4
2회차	1	2	3	5	4
3회차	1	2	3	5	4
4회차	1	2	3	4	5

순차적으로 가장 작은 원소를 찾아 앞에서부터 채워넣는다.
즉, 한 번 실행될 때마다 앞에서부터 한 레코드씩 정렬된다.
버블 정렬이 가장 큰 값을 차례대로 뒤로 보냈다면, 선택정렬은 가장 작은 값을 차례대로 앞으로 보낸다.
시간복잡도는 평균과 최악 모두 n^2 으로 같으며, 사용 메모리는 n이다.

public class HelloWorld{

     public static void main(String []args){
         int[] nums = {2, 3, 6, 1, 4, 9, 10};
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
         
         selectiveSort(nums);
         
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
     }
     
     public static void selectiveSort(int[] nums) {
         for(int i=0; i<nums.length - 1; i++) {
             int min = Integer.MAX_VALUE;
             int minLoc = 0;
             for(int j=i; j<nums.length; j++) {
                 if(min > nums[j]) {
                     min = nums[j];
                     minLoc = j;
                 }
             }
             
             nums[minLoc] = nums[i];
             nums[i] = min;
         }
     }
}

3) 삽입정렬

시작	5	3	2	1	4
1회차	3	5	2	1	4
2회차	2	3	5	1	4
3회차	1	2	3	5	4
4회차	1	2	3	4	5

하나의 배열을 i번째 까지의 배열과, i+1 이후의 배열로 나눈다.
i번째까지의 배열은 반드시 정렬되어 있어야 하며, i+1번째 이후의 배열의 첫 원소를 앞의 배열에 편입시키며 i번째 배열을 정렬해나간다.
즉, 0과 1을 비교하여 0~1로 이루어진 배열을 만들고, 0~1과 2를 비교하여 0~2까지의 배열을 만드는 식으로 정렬한다
시간복잡도는 평균과 최악 모두 n^2 으로 같으며, 사용 메모리는 n이다.

public class HelloWorld{

     public static void main(String []args){
         int[] nums = {2, 3, 6, 1, 4, 9, 10};
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
         
         insertionSort(nums);
         
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
     }
     
     public static void insertionSort(int[] nums) {
         for(int i=1; i<nums.length; i++) {
             int tmp = nums[i];
             for(int j=0; j<i; j++) {
                 if(tmp < nums[j]) {
                     nums[i] = nums[j];
                     nums[j] = tmp;
                     tmp = nums[i];
                 }
             }
         }
     }
}

4) 셸정렬

삽입정렬의 보완버전으로, 삽입정렬은 하나의 레코드의 위치가 수정될 때마다 뒤의 모든 레코드들이 한 칸씩 뒤로 밀려야 했다.
이를 보완하여 한 번에 여러 칸 이동을 시도하는 것이 셸 정렬이다.
간격(step, hop)을 정하고 행렬을 여러 개의 부파일로 나눠 삽입 정렬을 진행한다.
실행 시간은 O(n(log2n)^2), O(n^2)

5) 퀵정렬

분할정복 정렬 방법의 하나이다.
평균 수행시간이 비교에 의한 정렬 방법 중 가장 짧다.
배열의 한 원소를 피봇으로 선정하고, 이를 기준으로 두 개의 배열로 분리한다.
그리고 왼쪽 배열은 피봇보다 작은 값들로 구성하고, 오른쪽 배열은 큰 값들로 구성한다.
이러한 분할로 인한 변동이 없어질 때까지 계속한다.
평균 수행 시간은 O(n log2 n)이나, 정렬이 된 배열에 대해서는 O(n^2)의 복잡도를 보인다.
공간 복잡도는 O(log2 n)
피벗을 결정하는 방법은 랜덤으로 선정하거나 중위법 (왼쪽 끝, 중앙, 혹은 우측 끝을 선정)이 있다.
아래의 경우는 중위법 중 중앙의 것을 피벗으로 선정

public class HelloWorld{

     public static void main(String []args){
         int[] nums = {2, 3, 6, 1, 4, 9, 10};
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
         
         quickSort(nums, 0, nums.length-1);
         
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
     }
     
     public static void quickSort(int[] nums, int start, int end) {
         int left = start;
         int right = end;
         int pivot = nums[(start+end)/2];
         while(left <= right) {
             while(nums[left] < pivot) left++;
             while(nums[right] > pivot) right--;
             
             if(left <= right) {
                 int tmp = nums[left];
                 nums[left] = nums[right];
                 nums[right] = tmp;
                 left++;
                 right--;
             }
         }
         
         //left를 start로 하여 다음 로테이션 실행
         if(start < left-1) quickSort(nums, start, left-1);
         if(left < end) quickSort(nums, left, end);
     }
}

6) 힙정렬

완전 이진트리를 이용한 정렬 방법.
최대힙이란 상위 레벨 노드가 반드시 하위 레벨 노드보다 큰 숫자인 트리를 의미한다.
힙정렬은 힙을 만든 후 이를 통해 정렬하는 방법이다.
평균 수행 시간과 최악의 수행시간 모두 O(n log2 n)이다.
PriorityQueue를 사용하면 쉽게 구현할 수 있다.

import java.util.PriorityQueue;

public class HelloWorld{

     public static void main(String []args){
         int[] nums = {2, 3, 6, 1, 4, 9, 10};
         PriorityQueue<Integer> hp = new PriorityQueue<Integer>();
         
         for(int i=0; i<nums.length; i++) {
             System.out.print(nums[i] + " ");
             hp.add(nums[i]);
         }
         System.out.println();
         
         while(hp.size() != 0) System.out.print(hp.poll() + " ");
         System.out.println();
     }
     
}

PriorityQueue를 사용하지 않은 경우의 코드는 다음과 같다.

public class HelloWorld{

     public static void main(String []args){
         int[] nums = {2, 3, 6, 1, 4, 9, 10};
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
         
         heapSort(nums);
         
         for(int i=0; i<nums.length; i++) System.out.print(nums[i] + " ");
         System.out.println();
     }
 
    public static void heapSort(int[] nums) {
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            heapify(nums, nums.length, i);
        }
     
        for (int i = nums.length - 1; i > 0; i--) {
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            heapify(nums, i, 0);
        }
    }
    
    public static void heapify(int[] nums, int n, int i) {
        int parent = i; //부모노드
        int left = i*2 + 1; //왼쪽자식
        int right = i*2 + 2; //오른쪽 자식
     
        if (left < n && nums[parent] < nums[left]) {
            parent = left;
        }
     
        if (right < n && nums[parent] < nums[right]) {
            parent = right;
        }
     
        if (i != parent) {
            int tmp = nums[parent];
            nums[parent] = nums[i];
            nums[i] = tmp;
            heapify(nums, n, parent);
        }
    }
}

728x90