[Interview] 면접 관련 정리13

버블 정렬

서로 인접한 두 원소를 비교하여 정렬하는 알고리즘.
0번 인덱스부터 n-1번 인덱스까지 n번까지의 모든 인덱스를 비교하며 정렬한다.
시간 복잡도는 O(n2)이다.

for(int i = 0; i < arr.length - 1; i++) {
    for(int j = 0; j < arr.length-i-1; j++) {
        if(arr[j] > arr[j+1]) {
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
}

선택 정렬

선택 정렬은 가장 작은 값을 찾아서 앞으로 보내면서 정렬하는 알고리즘이다.
시간 복잡도는 O(n2)이다.

int index;
for(int i = 0; i < arr.length; i++) {
    int min = Integer.MAX_VALUE;
    for(int j = i; j < arr.length; j++) {
        if(min > arr[j]) {
            min = arr[j];
            index = j; // 가장 작은 값의 index
        }
    }

    int tmp = arr[i];
    arr[i] = arr[index];
    arr[index] = tmp;
}

삽입 정렬

삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 알고리즘으로, 필요한 순간에만 위치를 변경한다.
평균 시간 복잡도는 O(n2)이며, 가장 좋을 때는 O(n)이다.

for(int i = 0; i < arr.length-1; i++) {
    int j = i;
    while(arr[j] > arr[j+1]) {
        int tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
        j--;
    }
}

정렬이 어느정도 되어있다면 속도가 굉장히 빠르다.

퀵 정렬

대표적인 분할 정복 알고리즘으로 pivot값을 설정하고, pivot보다 큰 값과 작은 값으로 분할하여 정렬한다.
시간 복잡도는 O(nlogn)이며 리스트가 계속해서 불균등하게 나눠지는 경우 시간 복잡도가 O(n2)까지 나빠질 수 있다.

// start value : lo = 0, hi = arr.length - 1
void pivot_sort(int[] arr, int lo, int hi) {
    
    if(lo >= hi) { // 원소가 1개일 때
        return;
    }

    int pivot = partition(arr, lo, hi);
    pivot_sort(arr, lo, pivot - 1);
    pivot_sort(arr, pivot + 1, hi);
}

void int partition(int[] arr, int left, int right) {
    
    int lo = left;
    int hi = right;
    int pivot = a[left];

    while(lo < hi) {
        while(a[hi] > pivot && lo < hi) {
            hi--;
        }

        while(a[lo] <= pivot && lo < hi) {
            lo++;
        }

        swap(a, lo, hi); // 교환할 두 요소를 찾으면 교환
    }
    swap(a, left, lo); // hi, lo가 겹치면 pivot값과 교환

    return lo;
}

void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

병합 정렬(merge sort)

merge sort는 주어진 배열을 크기가 1인 배열로 분할하고, 합병하면서 정렬을 진행하는 분할/정복 알고리즘이다.
merge sort는 퀵 정렬과 다르게 피벗값이 없고, 항상 반으로 나누는데, 이 특징이 단계의 크기가 logN이 되도록 만들어준다.
시간 복잡도 : O(nlogn)

위 사진의 예시는 이미 쪼갠 상태라고 가정하고 시작한다.

static int arr[8];

void merge(int a[], int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;

    while(i <= mid && j <= right) {
        if(a[i] <= a[j]) {
            arr[k] = a[i];
            i++;
        }else {
            arr[k] = a[j];
            j++;
        }
        k++;
    }

    // 남은 데이터 삽입
    // i or j 둘 중 하나가 먼저 다 들어간 상황
    if(i > mid) {
        for(int t = j; t <= right; t++) {
            arr[k] = a[t];
            k++;
        }
    }else {
        for(int t = i; t <= mid; t++) {
            arr[k] = a[t];
            k++;
        }
    }

    // 정렬된 배열 삽입
    for(int t = left; t <= right; t++) {
        a[t] = arr[t];
    }
}

병합 정렬은 기존의 데이터를 담을 추가적인 배열 공간이 필요하기 때문에 메모리 활용이 비효율적이다.
이런 메모리 문제를 해결한 것이 힙 정렬이다.