정렬 알고리즘

31 May 2021

layout: post title: “[알고리즘] 정렬 알고리즘” description: “ “ date: 2021-05-31 tags: [알고리즘] comments: true share: true —

정렬 알고리즘 🧮

원소들을 번호순이나 사전순서와 같이 일정한 순서대로 열거하는 정렬 알고리즘에 대해 알아보자 ❗

정렬 알고리즘에는 가장 기본적이고 간단하지만, 속도는 조금 느린 버블정렬, 삽입정렬, 선택정렬과

복잡하지만 조금 머지소트, 퀵소트, 힙소트가 있다.

1. Bubble Sort

버블 정렬은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터가 제일 뒤로 가도록 정렬하는 알고리즘이다.

KakaoTalk_20210104_125455840

n-1번 실행 시 제일 큰 숫자인 37이 뒤로 가게 되고, 그 다음엔 29가 그 다음엔 14가 뒤로 가게 될 것이다.

실행시간은 최악의 경우 (n-1) + (n-2) + … + 2 + 1 = O(n^2) 이 될 것이다.

이것을 코드화 하면 아래와 같다.

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size-1; i++) {
        for (int j = 0; j < size-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

2. Insertion Sort

삽입정렬은 현재 원소와 앞의 원소의 크기를 비교해 알맞은 위치에 현재 원소를 삽입하는 정렬 알고리즘이다.

삽입정렬은 앞의 원소와 비교하기 때문에 두 번째 원소부터 시작한다.

최악의 경우 실행시간은 Bubble Sort와 같은 O(n^2) 이다.

코드화 하면 아래와 같다.

void insertionSort (int[] arr, int size) {
    for (int i = 1; i < size; i++) {
        for (int j = i; j > 0; j--) {
            if (arr[j-1] > arr[j]) {
                int tmp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

3. Selection Sort

선택정렬은 각 loop마다 최대 원소를 찾아 최대 원소와 맨 오른쪽 원소를 교환한다.

그리고 맨 오른쪽 원소를 제외한 후 다시 loop를 돌린다.

하나의 원소만 남을 때까지 위 loop를 반복하는 것이다.

실행시간은 최악의 경우 마찬가지로 O(n^2) 이다.

코드화 하면 아래와 같다.

void selectionSort(int[] arr, int size) {
    for (int i = size-1; i > 0; i--) {
        int max = i;
        for (int j = 0; j < i; j++) {
            if (arr[max] < arr[j]) {
                max = j;
            }
        }
        int tmp = arr[max];
        arr[max] = arr[i];
        arr[i] = tmp;
    }
}

4. Merge Sort

합병정렬은 데이터가 저장된 배열을 반으로 나눈 후 각각을 순환적으로 정렬한다.

이 정렬된 두 개의 배열을 합쳐 전체를 정렬하는 알고리즘이다.

마지막으로 정렬된 두 개의 배열을 하나로 합칠 때, 원 배열과 크기가 같은 추가배열을 하나 선언해

두 개의 배열을 각각 i와 j로 돌며 서로 비교해 더 작은 값을 추가배열에 넣는다.

시간 복잡도는 O(nlog2n) -> 밑이 2

코드와 하면 아래와 같다.

void mergeSort(int arr[], int p, int q) {
    if (p < q) {
        int mid = (p+q)/2;
        mergeSort(arr, p, mid);
        mergeSort(arr, mid+1, q);
        merge(arr, p, mid, q);
    }
}

void merge(int arr[], int p, int mid, int q) {
    int sorted[] = new int[arr.length];
    int i = p;
    int j = mid + 1;
    int k = p;
    
    while (i <= mid && j <= q) {
        if (arr[i] <= arr[j]) {
            sorted[k++] = arr[i++];
        }
        else {
            sorted[k++] = arr[j++];
        }
    }
    
    while (i <= mid) {
        sorted[k++] = arr[i++];
    }
    
    while (j <= q) {
        sorted[k++] = arr[i++];
    }
    
    for (int x = p; x <= q; x++) {
        arr[x] = sorted[x];
    }
}

5. Quick Sort

퀵 정렬은 pivot을 하나 정하고, 이 수를 기준으로 왼쪽에는 작은 수 오른쪽에는 큰 수가 오도록 재배치한다.

그 후 pivot의 왼쪽과 오른쪽을 각각 순환적으로 정렬하는 알고리즘이다.

맨 처음에 i = left / j = right로 시작을 해서 pivot보다 arr[j]가 크면 j–를, pivot이 arr[i] 보다 크거나 같으면 i++를 해준다.

즉, i는 pivot보다 큰 수를 찾는 과정이고 j는 pivot보다 작은 수를 찾는 과정이다.

알맞는 수를 찾았다면 arr[i]와 arr[j]를 바꾼다.

이 과정에서 i 와 j가 겹쳐졌다면 while문을 탈출하고 pivot과 arr[i] (혹은 arr[j])를 바꿔준다.

pivot을 기준으로 왼쪽 / 오른쪽 부분에서 또 이 과정을 반복하면 된다.

시간복잡도는 최악의 경우 O(n^2), 최선의 경우에는 O(nlogn)

코드화 하면 아래와 같다.

void quickSort(int[] arr, int l, int r) {
    if (l >= r) {
        return ;
    }
    
    int pivot = partition(arr, l, r);
    quickSort(arr, l, pivot - 1);
    quickSort(arr, pivot + 1, r);
}

static int partition(int[] arr, int l, int r) {
    int pivot = arr[l];
    int i = l;
    int j = r;
    
    while (i < j) {
        while (pivot < arr[j]) {
            j--;
        }
        while (i < j && pivot >= arr[i]) {
            i++;
        }
        
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }
    
    arr[l] = arr[i];
    arr[i] = pivot;
    
    return i;
}

6. Heap Sort

힙 정렬은 이진 힙 자료구조를 사용해 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 알고리즘이다.

최대 힙 트리: 부모는 자식보다 크거나 같다

최소 힙 트리: 부모는 자식보다 작거나 같다

힙 정렬 과정의 일부를 그려보았다.

힙의 부분트리를 검사해 부모의 키 값이 자식의 키 값보다 커지도록 해주면 된다.

코드화 하면 아래와 같다.

void heapSort(int[] arr, int size) {
	for (int i = size/2 - 1; i >= 0; i--) {
		heapify(array, size, i);
	}
	for (int i = size-1; i >= 0; i--) {
		swap(arr, i, 0);
		heapify(arr, i-1, 0);
	}
}

void heapify(int[] arr, int size, int parent) {
    int p = parent;
    int l = parent * 2 + 1;
    int r = parent * 2 + 2;
    
    if (l < size && array[p] < array[l]) {
        p = l;
    }
    
    if (r < size && array[p] < array[r]) {
        p = r;
    }
    
    if (parent != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}
//swap 메소드는 생략

✔ compareTo 메소드: 2개의 문자열을 비교해 int 값을 반환하는 메소드

a.compareTo(b) 의 형식으로 사용

a == b 면 0을 반환
a > b 면 양수 반환
a < b 면 음수 반환