[자료구조] 정렬 (Sort)

정렬(Sort)

 - 2개 이상의 자료를 작은 것부터 큰 순서(오름차순, Ascending)로 정렬 또는 큰 것부터 작은 것 순서(내림차순, Descending)로 재배열하는 것.

 - 키(key) : 자료를 정렬하는 데 사용하는 기준 값

---

정렬 방법의 분류

 - 실행 방법에 따른 분류

    ㄴ 비교식 정렬(Comparative Sort)

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

    ㄴ 분산식 정렬(Distribute Sort)

         : 키 값을 기준으로 자료를 여러 개의 부분 집합으로 분해, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식

 - 정렬 장소에 따른 분류

    ㄴ 내부 정렬(Internal Sort)

        : 정렬할 자료를 메인 메모리에 올려 정렬

        - 장) 정렬 속도 빠름 / 단) 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한

        ① 교환 방식 : 키를 비교하고 교환하여 정렬 (ex. 선택 정렬, 버블 정렬, 퀵 정렬)

            +) 선택 정렬(Selection Sort)

            +) 버블 정렬(Bubble Sort)

            +) 퀵 정렬 (Quick Sort)

        ② 삽입 방식 : 키를 비교하고 삽입하여 정렬 (ex. 삽입 정렬, 셸 정렬)

            +) 삽입 정렬 (Insert Sort)

        ③ 병합 방식 : 키를 비교하고 병합하여 정렬 (ex. 2-way병합, n-way 병합)

            +) 병합 정렬 (Merge Sort)

        ④ 분배 방식 : 키를 구성하는 값을 여러 개의 부분 집합에 분배하여 정렬 (ex. 기수 정렬)

        ⑤ 선택 방식 : 이진트리를 사용하여 정렬 (ex. 힙 정렬, 트리 정렬)

    ㄴ 외부 정렬(External Sort)

        : 정렬할 자료를 보조 기억장치에서 정렬

        - 장) 대용량 자료 정렬 가능 / 단) 속도 느림

        ① 병합 방식 : 파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 정렬 (ex. 2-way 병합, n-way 병합)