Portfolio

Sort 알고리즘들에 대해서 알아보자.

Sort 알고리즘: 자료들을 일정한 기준에 의해서 정렬하는 알고리즘이다.

Sort 알고리즘에는 Selection Sort, Bubble Sort, Quick Sort, Insertion Sort, Shell Sort, Merge Sort, Heap Sort, Radix Sort 등이 있다.

실행 방법에 따른 분류

비교식 정렬(comparative sort)와 분산식 정렬(distribute sort)가 있다.

비교식 정렬은 비교하고자 하는 각 키값들을 한 번에 두 개씩 비교하여 교환하는 방식이다.

분산식 정렬은 키값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법이다.

정렬 장소에 따른 분류

내부 정렬(internal sort)와 외부 정렬(external sort)가 있다.

내부 정렬은 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식이고 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라서 제한된다.

교환방식(selection, bubble, quick) , 삽입 방식(Insertion, shell), 병합 방식(2-way, n-way) 분배 방식(Radix), 선택 방식(Heap, tree)등이 있다.

외부 정렬은 정렬할 자료를 보조기억장치에서 정렬하는 방식이고 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬이 가능하다.

알고리즘 성능

일반적으로 Quick Sort가 제일 빠르다고 알려져 있다. 최악의 경우 n^2의 시간복잡도가 발생하는데 이는 피봇값이 최소값, 최대값으로 잡히게 되는 경우이다. 이를 피하기 위해서 피봇을 랜덤으로 잡거나 Media-of-tree Partitioning이라는 기법을 사용한다. 평균적으로 가장 좋은 성능을 낸다.

이미 정렬되어 있는 자료의 경우에는 Insert Sort가 제일 빠르다. 이미 정렬 되어 있는 경우 바로 앞자리 원소와 한 번만 비교하면 되기 때문이다.

시간 복잡도 별로 분류

O(n^2): Bubble Sort, Selection Sort, Insertion Sort, Shell sort, Quick SOrt

O(N log n): Heap Sort, Merge Sort

O(kn): Radix Sort(k는 자리수, 자리수가 적은 4바이트 정수에서나 제대로된 성능을 낼 수 있다는 제약이 있다)

Bubble sort

인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.

첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 정렬된다.


public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        final int length = arr.length;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length - i; j++) {
                if (j + 1 < length && arr[j] > arr[j + 1]) {
                    arr[j] = arr[j] + arr[j + 1];
                    arr[j + 1] = arr[j] - arr[j + 1];
                    arr[j] = arr[j] - arr[j + 1];
                }
            }
        }
    }
  
}

Selection Sort

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식이다.

전체 원소 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 바꾼다.

그 다음 두 번쨰로 작은 원소를 찾아서 선택하여 두 번째 원소와 자리를 교환한다.

그 다음에는 세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환한다.

반복


public class SelectionSort {

    public static void selectionSort(int[] arr) {
        final int length = arr.length;
        for (int i = 0; i < length; i++) {
            int min = i;

            for (int j = i + 1; j < length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }

            if (min == i) {
                continue;
            }

            arr[min] = arr[min] + arr[i];
            arr[i] = arr[min] - arr[i];
            arr[min] = arr[min] - arr[i];
        }
    }
  
}

Insertion Sort

정렬 되어 있는 부분집합에 정렬할 새로운 원소의 위치를 삽입하는 방법이다.

정렬할 자료를 두 개의 부분집합 S와 U로 가정한다.

부분집합S: 정렬된 앞 부분의 원소들

부분집합U: 아직 정렬되지 않은 나머지 원소들

정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.

삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 된다.

부분집합 U가 공집합이 되면 정렬이 완성된다.

Shell Sort

일정한 간격으로 떨어져있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법이다. 전체 원소에 대해서 삽입 정렬을 수행하는 것보다 부분 집합으로 나누어 정렬하게 되면 비교 연산과 교환 연산이 감소할 수 있다.

부분집합의 기준이 되는 변수 interval 저장.

한 단계가 수행될 때마다 interval의 값을 감소시키고 쉘 정렬을 순환 호출한다

interval이 1이 될 때까지 반복한다.

쉘 정렬의 성능은 interval의 값에 따라 달라진다. 정렬할 자료의 특성에 따라 interval 생성 함수를 사용하고 일반적으로 사용하는 interval의 값은 원소 개수의 1/2을 사용하고 한 단계 수행될 때마다 interval의 값을 반으로 감소시키면서 반복 수행한다.


public class ShellSort {

    public static void shellSort(int[] arr) {
        final int length = arr.length;
        int interval = length / 2;

        while (interval >= 1) {
            for (int i = 0; i < length; i++) {
                intervalSort(arr, i, length - 1, interval);
            }

            interval /= 2;
        }
    }

    private static void intervalSort(int[] arr, int begin, int end, int interval) {
        for (int i = begin + interval; i <= end; i += interval) {
            final int key = arr[i];
            int position = i;

            while (position >= interval && key < arr[position - interval]) {
                arr[position] = arr[position - interval];
                position -= interval;
            }

            arr[position] = key;
        }
    }
}

Quick sort

정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다.

왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.

기준 값 : 피봇 (pivot), 일반적으로 전체 원소 중에서 가운데에 위치한 원소를 선택한다.

분할(divide) : 정렬할 자료들을 기준 값을 중심으로 2개의 부분 집합으로 분할한다.

정복(conquer) : 부분집합의 원소들 중에서 기준 값보다 작은 원소들은 왼쪽 부분집합으로, 기준 값보다 큰 원소들은 오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 1이하로 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다.


public class QuickSort {

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length -1);
    }

    private static void quickSort(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }

        int middle = begin + (end - begin) / 2;
        int pivot = arr[middle];
        int left = begin;
        int right = end;

        while (left <= right) {
            while (arr[left] < pivot) {
                left++;
            }

            while (arr[right] > pivot) {
                right--;
            }

            if (left <= right) {
                arr[left] = arr[left] + arr[right];
                arr[right] = arr[left] - arr[right];
                arr[left] = arr[left] - arr[right];

                left++;
                right--;
            }
        }

        if (begin < right) {
            quickSort(arr, begin, right);
        }

        if (end > left) {
            quickSort(arr, left, end);
        }
    }
}

자바스크립트 sort는 문자의 유니코드 코드 포인트 값에 따라 정렬된다.

원래의 배열이 정렬된다.

map을 사용해서 sort를 진행할 수 도 있다.


var mapped = list.map(function(el, i) {
  return { index: i, value: el.toLowerCase() };
})d