내부 정렬(internal sort): 컴퓨터 메모리 내부에서 정렬
1). 비교식
교환방식: 키를 비교하고 교환하여 정렬하는 방식(선택 정렬, 버블 정렬, 퀵 정렬)
삽입방식: 키를 비교하고 삽입하여 정렬하는 방식(삽입 정렬, 셸 정렬)
병합방식: 키를 비교하고 병합하여 정렬하는 방식(2-way 병합, n-way 병합)
선택방식: 이진 트리를 사용하여 정렬하는 방식(힙 정렬, 트리 정렬)
외부 정렬(external sort): 메모리의 외부인 보조 기억 장치에서 정렬
파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 방식(2-way 병합, n-way 병합)
전체 원소 중에서 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식
공간 복잡도 n, 시간 복잡도 , 어떤 경우에서나 비교 횟수가 같다.
인접한 원소 두개를 비교하여 자리를 교환하는 방식
공간 복잡도 n, 시간 복잡도
최악의 경우: 역순으로 정렬된 경우
최선의 경우: 순서대로 정렬된 경우
전체 원소에 대해 정렬을 수행하지 않고 기준 값을 중심으로 왼쪽 부분집합과 오른쪽 부분 집합으로 분할한다. 왼쪽 부분집합에는 기준값보다 작은 원소를 이동시키고 오른쪽 부분집합에는 기준 값 보다 큰 원소들을 이동시킨다. 이 때 기준 값을 ‘pivot’ 이라 한다.
피벗은 가운데 위치한 원소 또는 첫째 원소, 마지막 원소로 정할 수 있고 별도의 수식을 사용하여 정하기도 한다.
분할과 정복을 반복 수행하여 퀵정렬을 완성한다.
분할: 정렬할 자료들을 기준값을 중심으로 두 개로 나눠 부분집합을 만든다.
정복: 부분집합 안에서 기준값의 정렬 위치를 정한다.
하나의 배열 안에서 교환이 진행되므로 공간 복잡도: n
평균 시간 복잡도 ()
최선의 경우에 피벗에 의해 왼쪽 부분집합과 오른쪽 부분집합이 반반 나뉘는 경우이다. ()
최악의 경우는 피벗이 극단적으로 한쪽에 치우쳐져 있을 경우
정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식
sorted subset과 unsorted subset로 나뉘어 있다고 가정한다.
공간 복잡도 n
최선의 경우 O(n) 정렬된 경우
최악의 경우: 역순으로 정렬된 경우, 평균
일정한 간격(interval)으로 떨어져 있는 자료들 끼리 부분집합을 구성하고, 각 부분집합에 있는 원소에 대해 삽입정렬을 수행하는 작업을 반복하여 전체원소를 정렬하는 방법
간격을 점점 줄여 1이 되면 삽입 정렬을 수행한다.
임베디드 시스템에 주로 사용. 간격에 따른 그룹별 정렬 방식이 하드웨어로 구현하기 적합하다.
공간 복잡도 O(n)
시간복잡도 , Hibbard의 간격
, 실험적인 결과 간격을 얼마로 설정하나에 따라 달린다.
최악
최선
여러 개의 정렬된 자료집합을 병합하여 하나의 정렬된 집합으로 만드는 정렬 방법
분할: 자료를 두개의 부분 집합으로 분할한다.
정복: 부분집합에 잇는 원소를 정렬한다.
결합: 정렬된 부분집합들을 하나의 집합으로 정렬하여 결합한다.
분할 단계: 전체자료 집합을 한 개의 원소를 가진 부분집합이 될 때 까지 분할한다.
정복, 결합: 부분집합 두 개를 정렬하여 하나로 결합한다. 하나의 집합이 될 때 까지 반복한다.
공간복잡도 2n
시간 복잡도
정렬할 원소의 키값에 해당하는 버킷에 원소를 분배했다가 버킷의 순서대로 원소를 꺼내는 방법을 반복한다. 키 값의 자릿수 만큼 기수 정렬을 반복한다. 10진수는’0~9’ 10개의 버킷 사용
숫자를 부분적으로 비교하는 정렬 방법.
제한적인 범위 내에 있는 숫자에 대해서 각 자릿수 별로 정렬하는 알고리즘. 비교 정렬 알고리즘 보다 빠르다.
힙을 이용해 정렬된 값을 얻는 방법
루트와 마지막 원소의 자리를 바꾸고 힙의 크기를 줄인다.
힙의 크기가 1이 되면 정렬을 멈춘다.
공간: n 개의 메모리, 힙을 저장할 공간, 시간
이진 탐색 트리를 이용한 방법. (중위 순회: 오름차순)
공간: n + 이진탐색 트리를 저장할 공간
시간