[자료구조 알고리즘] 자료구조 효율적인 탐색을 위한 정렬알고리즘#1

[정렬]

- 자료구조 연산 : 삽입 - 삭제 - 탐색(정렬되어있는 상태로)

- 탐색을 위한 정렬 : 탐색을 효율적으로 하기위해서

[버블정렬]

1) 구현하기는 쉽지만 데이터 개수가 늘어남에 따라 연산 횟수도 늘어남

2) N개의 데이터에서 순서대로 2개씩 잡고 오름/내림차순(비교와 이동 연산)에 따라 정렬함

3) 공간복잡도 O(N) : 같은 배열에서 진행하기때문에

4) 시간복잡도 - 워스트 케이스

- 비교했을 때 모두 이동함

- 어쨌든 비교를 데이터 개수만큼 해야하고 비교를 어떻게 하나 : (n-1)번 + (n-2)번 + ...... + 1

- 등차수열의 합 : n(n-1)/2 -> O(N^2)

static void sort(int[] arr){
    int length = arr.length;

    for(int i=0; i<length; i++){
        for(int j=1; j<length; j++){
            /* 연산 : 비교 */
            if(arr[j-1] > arr[j]){
                /* 연산 : 이동 */
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

[선택정렬]

- 구현하기는 쉽지만 데이터 개수가 늘어날 때마다 연산해야하는 횟수가 증가량이..

- 1개 자리에 어떤 값을 넣어야하는데, 그것을 배열 끝까지 돌면서 찾기 : 자리에 맞는 값을 선택해서 정렬시킴

- 시간복잡도 : 비교 연산

(1) 워스트케이스 : 그 자리에 위치할 데이터가 끝에 있는 경우

(2) (n-1) + (n-2) + (n-3) + ..... + 1 : 수열의 합 구하는 공식으로 - O(N^2)

static void sort(int[] arr){
    int length = arr.length;

    for(int i=0; i<length; i++){
        int minIdx = i;

        for(int j=i; j<length; j++){
            /* 연산 : 비교 */
            if(arr[minIdx] > arr[j]){
                minIdx = j;
            }
        }

        /* 연산 : 이동 */
        int swap = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = swap;
    }
}

[삽입정렬]

- 정렬된 것과 정렬되지않은 것을 나눔 : 정렬된 곳에 정렬되지않은 원소를 하나 던져서 위치 정렬

- 시간복잡도

(1) 최악의 경우 : 가장 왼쪽에 위치해야할 떄, 앞에 정렬된 원소와 모두 비교 한번씩 모두 이동

(2) 비교로 : n번째일 때 - (n-1), (n-1) + (n-2) + (n-3) + ...

(3) O(N^2)

static void sort(int[] arr){
    int length = arr.length;

    for(int i=1; i<length; i++){

        int std = arr[i];
        int idx = i;

        for(int j=i-1; j>=0; j--){
            if(std < arr[j]){
                /* 밀어버리기 */
                arr[j+1] = arr[j];
                idx = j;
            } else {
                break;
            }
        }

        arr[idx] = std;
    }
}