정렬 알고리즘(Sorting)

정렬 알고리즘 정의

정렬은 이름,학번,키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다.
정렬 알고리즘은 다양하게 존재하며 이에대해 설명하려 한다. 어떤 정렬 알고리즘을 선택하냐에 따라 처리속도가 천차만별이다.
처리속도 O(N²) 와 O(Nlog_n) 인 알고리즘을 알아보려 한다.

정렬 알고리즘 종류

버블 정렬(Bubble Sort)

버블 정렬은 인접한 인덱스값과 비교하여 정한 기준 값을 뒤로 넘겨 정렬하는 방식이다. 버블정렬은 반복문 안에 반복문을 사용함으로서 O(N²) 시간복잡도가 요구된다. 오름차순으로 정렬시 제일 큰 수는 맨뒤에 정렬되게 된다. 이미 정렬된 큰 수는 비교할 필요가 없으므로 배열 크기에 정렬된 횟수만큼 차감하면서 반복문 작성을 하면 된다.

버블 정렬

public int[] bubble(int[] array) {
    int temp = 0;

    for (int i = 0; i < array.length; i++) {
        for (int j = 1; j < array.length - i; j++) {
            if (array[j] < array[j-1]) {
                temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
            }
        }
        printArray(array);
    }

    return array;
}

printArray() 메소드는 정렬 처리 과정을 보기 위한 메서드다.

public void printArray(int[] array) {
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < array.length; i++) {
        sb.append(String.format("[%d]", array[i]));
    }

    System.out.println(sb.toString());
}

결과:
버블 정렬 결과

선택 정렬(Selection Sort)
- 선택 정렬의 경우 이름에 맞게 해당 위치에 들어갈 값을 찾아 정렬하는것을 말한다. 오름차순 정렬을 예로 들면 배열 인덱스 0 자리에 해당하는 값을 찾아 인덱스 0 이후 인덱스 값들과 전부 비교한다. 인덱스 0 보다 작은값을 발견시 해당 인덱스와 값을 바꿔주고 정렬을 끝까지 진행한다. 선택 정렬은 배열 전체 조회 반복문과 선택 배열과 이후 배열을 비교하는 반복문이 필요함으로 시간복잡도는 O(N²)이다.
```
public int[] selection(int[] array) {
    int temp = 0;

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

    return array;
}
```
  결과:
삽입 정렬(Insertion Sort)
- 삽입 정렬은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 ‘삽입한는’ 작업을 반복하여 정렬하는 알고리즘이다. 선택 정렬과 비슷하게 보일 수 있지만 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다르다.
  시작 인덱스는 1부터 시작하여 이전 인덱스와 값을 비교하여 정렬한다. 다음 인덱스로 넘어가면서 해당 인덱스가 들어갈 자리를 찾아 삽입한다. 코드로 작성시 삽입 정렬은 전체 배열 반복문과 해당 반복문 안에 이전 인덱스 조회 반복문이 필요하므로 시간복잡도는 O(N²)이다.
```
public int[] insertion(int[] array) {
    int key = 0;
    int temp = 0;

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

        for (int j = i - 1; j >= 0; j--) {
            if (array[key] < array[j]) {
                temp = array[key];
                array[key] = array[j];
                array[j] = temp;

                key = j;
            }
        }
        printArray(array);
    }

    return array;
}
```
  결과:

합병 정렬(Merge Sort)

합병 정렬은 데이터 집합을 둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬한 다음 부분 집합들을 다시 정렬된 형태로 합치는 방식으로 정렬을 하는 분할 정복형 알고리즘이다. 보통 합병 정렬, 병합 정렬, 합치기 정렬 등 으로 불린다. 해당 정렬은 재귀호출 형식으로 구현할 수 있다. 배열을 두개남을때 까지 나눈후 배열이 두개가 남았을경우 해당 두개의 배열을 비교하여 정렬하며, 정렬된 배열은 반환 한다. 이렇게 쪼개어 반환된 배열끼리 다시 합쳐 최종적으로 다시 원래의 배열의 크기로 반환된다.
분할 과정은 logN 만큼 일어나며 각 분할별로 합병하기에 시간복잡도는 O(NlogN) 이다.

합병 정렬

public int[] merge(int[] array) {
    if (array.length == 1) {
        return array;
    } else if (array.length == 2) {
        if (array[0] > array[1]) {
            int temp = array[0];
            array[0] = array[1];
            array[1] = temp;
        }

        return array;
    } else {
        int[] leftArray = Arrays.copyOfRange(array, 0, array.length / 2);
        int[] rightArray = Arrays.copyOfRange(array, array.length / 2, array.length);

        leftArray = merge(leftArray);
        rightArray = merge(rightArray);

        int[] mergeArray = new int[leftArray.length + rightArray.length];
        int index = 0; // mergeArray index
        int i = 0; // leftArray index
        int j = 0; // rightArray index

        while (index < mergeArray.length) {
            if (i < leftArray.length && j < rightArray.length) {
                if (leftArray[i] < rightArray[j]) {
                    mergeArray[index] = leftArray[i];
                    i++;
                } else {
                    mergeArray[index] = rightArray[j];
                    j++;
                }
            } else if (i < leftArray.length) {
                mergeArray[index] = leftArray[i];
                i++;
            } else if (j < rightArray.length) {
                mergeArray[index] = rightArray[j];
                j++;
            }

            index++;
        }

        System.out.print("Left Array = ");
        printArray(leftArray);
        System.out.print("Right Array = ");
        printArray(rightArray);
        System.out.print("Merge Array = ");
        printArray(mergeArray);

        return mergeArray;
    }
}

결과:
합병 정렬 결과

퀵 정렬(Quick Sort)

퀵 정렬에서는 데이터 집합 내에서 한 피벗값을 고른 다음 그걸 기준으로 집합을 두개의 부분집합으로 나눈다. 한쪽 부분집합에는 피벗 값보다 작은 것만, 다른 부분집합에는 큰 것만 넣는다. 더 이상 쪼갤 부분집합이 없을 때까지 각각의 부분집합에 대해 피벗.쪼개기 작업을 재귀적으로 적용한다. 그렇게 하고 나면 최종적으로 정렬된 데이터 집합이 만들어 진다.
퀵 정렬은 분할과 동시에 정렬하는 알고리즘으로 합병 정렬보다 20% 빠르다 보면 된다. 다만 최악의 경우 합병 정렬보다 느릴 수 있는데 이 경우는 흔치 않으며 최악의 경우라고 얘기하자면 이미 정렬된 알고리즘에 퀵정렬 시도하는것이 최악의 경우라고 할 수 있다. 그래서 최악의 경우를 피하기 위해 피벗을 배열 가운데 값을 선택하여 퀵정렬을 한다.

퀵 정렬

// quick method usage: quick(array, 0, array.length - 1);
public int[] quick(int[] array, int left, int right) {
    if (left >= right) {
        return array;
    }

    int pivot = (left + right) / 2;
    int start = left;
    int end = right;
    int temp = 0;

    while (pivot > start || pivot < end) {
        while (array[pivot] > array[start]) start++;
        while (array[pivot] < array[end]) end--;

        if (pivot != start && pivot != end) {
            temp = array[start];
            array[start] = array[end];
            array[end] = temp;
        } else if (pivot == start) {
            temp = array[end];
            array[end] = array[start];
            array[start] = temp;

            pivot = end;
        } else if (pivot == end) {
            temp = array[end];
            array[end] = array[start];
            array[start] = temp;

            pivot = start;
        }
    }

    int[] leftQuick = quick(array, left, pivot - 1);
    int[] rightQuick = quick(leftQuick, pivot + 1, right);

    return rightQuick;
}

결과:
퀵 정렬 결과

해당 소스코드는 아래 주소에서 확인할 수 있다.
https://github.com/jun7343/data-structure/blob/master/src/main/algorithm/Sorting.java

참조

프로그래밍 면접 이렇게 준비한다.
Wikimedia
화투의 개발 블로그

Date: July 12, 2020

Tags: Algorithm