Sorting Data Structure

About Sorting

 

정렬의 목적은 데이터 검색을 위해서 이다.

그렇기 때문에 다음시간에 포스팅할 검색과도 깊은 연관이 있다.

정렬은 매우 중요한 작업이다. 정렬이 되어있지 않은 수백만건의 데이터를 상상해보면

끔찍할것이다. 그래도 어찌됐건 정렬을 해야하는데 순차 검색외엔 다른방법이 없다.

하지만 정렬이 되어있다면 매우 빠른 이진 검색을 사용할수 있다.

컴퓨터가 정렬을 수행하는 여러가지 이유중에 하나가 바로 이진 검색이 가능한 데이터로

가공하기 위한 목적도 있다.

정렬을 하기까지 걸리는 시간은 보통 자료수의 제곱에 비례하여 늘어나기때문에 효과적인

정렬방법을 만드는게 중요하지만 스터디에 목적은 정렬을 알아보기 위함이고

내장되어 있는 정렬을 가져다 쓰는것이 더 빠를것이다.

Basical Sorting

기본적으로 이론적인 공부를 하기위해 예시로 많이 사용하는 3가지 Sorting 방법이 있다.

세가지모두 순차적으로 이전 방식보다 나은 방안을 설명하고 있기때문에

3가지 Sorting에 이론적 개념을 같이 묶어서 생각해보면 코드로 표현하기 훨신 수월할것이다.

bubble < selection < insertion

bubble Sort

첫번째와 2번째 원소를 비교하여 정렬하고 다시 2번째와 3번째..

기본 Sorting 3형제중에 막내이며 거의 모든 상황에서 최악의 성능을 보여 주는 정렬이다.

단 이미 정렬된 자료를 정렬 하는것은 1번만 돌면 되기 때문에 최상의 성능을 보여주는데

대부분 정렬 알고리즘은 자료가 정렬되어 있는지 여부를 떠나 그냥 작동하기 때문에

의미가 있다.

    function bubbleSort(ar) {
        let arr = [...ar],
            len = arr.length,
            i,
            j,
            stop,
            temp;

        for (i = 0; i < len; i++) {
            for (j = 0,stop = len - i; j < stop; j++) {
                if (arr[j] > arr[j + 1]) {
                        temp     = arr[j];
                        arr[j]   = arr[j+1];
                        arr[j+1] = temp;
                }
            }
         }
        return arr;
    }

Selection Sort

버블 정렬이 비교하고 바로 값을 바꾸는걸 반복한다면

선택 정렬은 첫번째부터 끝까지 훑어서 가장 작은값을 첫번째에 놓고 두번째부터 끝까지 훑어서 작은값을

두번째에 놓는것을 (n-1)번 반복한다. 어찌 보면 인간이 사용하는 정렬 방식을 가장 많이 닮았다.

​​버블 정렬보다 두 배 정도 빠르다고 한다.

function selectionSort(ar) {
        let arr = [...ar];

        let len = arr.length,
            i,
            j,
            min,
            temp;

        for (i = 0; i < len - 1; i++) {
            min = i;
            for (j = i; j < len; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }

            if (i !== min) {
                    temp     = arr[i];
                    arr[i]   = arr[min];
                    arr[min] = temp;
            }
        }
        return arr;
    }

Insertion Sort

k번째 원소를 1부터 k-1까지와 비교해 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는

방식으로 평균적으로 빠른 편이나 자료구조에 따라선 뒤로 밀어내는데 걸리는 시간이 크며 앞의 예시처럼

작은 게 뒤쪽에 몰려있으면(내림차순의 경우 큰 게 뒤쪽에 몰려있으면) 그야말로 헬게이트다.

다만 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬

알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다. 괜히 '삽입'이란 이름이 붙은 것이

아니다.

function insertionSort(ar) {
    let arr = [...ar],
        len = arr.length,
        i,
        j,
        temp;

    for (i = 1; i < len; i++) {
        j = i;
        temp = arr[i];

        while (j > 0 && arr[j-1] > temp) {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}

그밖에도 병합정렬이나 , 쉘정렬, 퀵정렬등에 정렬 방식이 있는데

이는 따로 포스팅하거나 고급알고리즘 스터디가 끝나면 추가로 포스팅할 예정이다.