문제3_정렬알고리즘(버블,선택,삽입 O(N^2) 병합,퀵,힙 O(logN) ,계수 정렬 O(log(N+K))

• 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
• 라이브러리 정렬 O(NlogN)
• 버블: O(N^2), 선택 : O(N^2), 삽입 : O(N^2), 퀵 : O(NlogN), 계수 : O(N+K)
• 버블 선택 삽입 퀵 예시 [7,5,9,0,3,1,6,2,4,8]
• 병합 정렬 예시[5, 3, 2, 1, 6, 8, 7, 4]
• 계수 정렬 [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]

1.버블정렬 O(N^2)

: 가장 쉽고 직관적인 정렬로,

첫번째 자료와 두번째 자료를 두번째 자료와 세번째 자료를 ... 이런식으로 n-1번째와 n번째 자료를 비교 교환하면서 자료를 정렬하는 방식

• 동작 : 제일 끝에 가장 큰 수를 놓는 방식으로
•  
• package Basic_Algorithm; public class Test03_1_bubblesort { public static void main(String[] args) { //인접한 데이터를 비교하면서 제일끝에 가장 큰 수를 넣는 방법 O(N^2) // {7,5,9,0,3,1,6,2,4,8} //정렬되지 않은 배열 num_arr int[] num_arr={7,5,9,0,3,1,6,2,4,8}; int temp; for (int i = 0; i < num_arr.length; i++) { for (int j = 1; j < num_arr.length-i; j++) { if(num_arr[j-1]>num_arr[j]){ temp=num_arr[j-1]; num_arr[j-1]=num_arr[j]; num_arr[j]=temp; } } } for (int num:num_arr){ System.out.print(num+"\t"); } } }

2. 선택정렬 O(N^2) 

: 데이터가 무작위로 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 (매번 가장 작은 데이터를 선택한다)
: 반복문 돌 때 마다 그 때의 최소의 값을 선택하여 바꿔준다는 과정에서 선택정렬이라고 한다

package Basic_Algorithm;

public class Test03_2_selectsort {
    public static void main(String[] args) {
        //정렬되지 않은 배열 num_arr
        int[] num_arr={7,5,9,0,3,1,6,2,4,8};
        //가장 작은 값을 제일 앞으로 놓으면서 정렬 O(N^2)
        int min_num;
        int min_idx;
        int temp;
        for (int i = 0; i < num_arr.length; i++) {
            min_idx=i;
            for (int j = i; j <num_arr.length ; j++) {
                if(num_arr[min_idx]>num_arr[j]){
                    min_idx=j;
                }
            }
            //제일 작은 수를 앞으로 이동
            if(min_idx!=i){
                temp=num_arr[i];
                num_arr[i]=num_arr[min_idx];
                num_arr[min_idx]=temp;
            }
        }

        for (int num:num_arr){
            System.out.print(num+"\t");
        }
    }
}

3.삽입정렬 O(N^2)

: 처리되지 않은 데이터를 하나씩 골라서 적절한 위치에 삽입 만약 주어진 리스트가 거의 정렬이 되어있는 상태라면 O(N)의 시간복잡도를 가질 수 있다

package Basic_Algorithm;

public class Test03_3_insertionsort {
    public static void main(String[] args) {
        //정렬되지 않은 배열 num_arr
        int[] num_arr={7,5,9,0,3,1,6,2,4,8};
        //처리되지 않은 것을 처리하면서 정렬 O(N^2)
        int temp;
        for (int i = 1; i < num_arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if(num_arr[j-1]>num_arr[j]){
                    temp=num_arr[j-1];
                    num_arr[j-1]=num_arr[j];
                    num_arr[j]=temp;
                }else break;
            }
        }
        for (int num:num_arr){
            System.out.print(num+"\t");
        }
    }
}

4.병합정렬 O(NlogN)

 

5.퀵정렬 O(NlogN)

: 기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸어주는 방법 보통 첫번째 데이터를 pivot으로 설정할 것이다.

• 동작

1. Pivot 선택(보통 시작 index로 설정할 수 있다)
2. 왼쪽에서 부터 pivot 보다 큰 데이터 선택
3. 오른쪽에서 부터 pivot 보다 작은 데이터 선택
4. 이전 두 과정에서 왼쪽의 큰 데이터와 오른쪽의 작은 데이터의 위치를 change
5. 2,3,4번 과정을 계속 진행
6. 만약 왼쪽 index가 오른쪽 index보다 커졌을 경우, 왼쪽 index에 있는 값과 pivot 값을 change

-> 이렇게되면 바뀐 pivot값의 위치를 기준으로 왼쪽은 pivot값보다 작은 값들만 모이고 오른쪽은 pivot값들 보다 큰 값들로 이루어진다

1. pivot 왼쪽에 있는 값들, 오른쪽에 있는 값들을 pivot을 제외하고 퀵정렬을 한다
2. 퀵정렬을 할 원소가 1개가 되는 순간 퀵정렬을 종료한다

6.힙정렬 O(logN) : 우선순위 큐

index 0은 사용하지 않고 1~n까지

부모 index는 childindex/2

부모인덱스랑 비교하여 부모인덱스가 크면 max힙(반대의 경우 min힙)

7.계수정렬 O(N+K)

: 데이터갯수 N, 데이터 중 최댓값 K 일때

: 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘 (데이터의 크기 범위가 제한되어 정수형태로 표현할 수 있을 때 사용 가능, 데이터의 범위가 한정적이면서 정렬할 데이터가 많을 때 계수 정렬을 이용)