정렬과 레코드
- 순서가 없는 사무들을 순서대로 나열하는 작업으로 오름차순, 내림차순이 있다
- 정렬시켜야 할 대상을 레코드라 칭함
- 필드라는 보다 작은 단위로 구성
- key는 자료 정렬하는데 사용되는 기준이 되는 특정 값이다.
- 레코드를 키의 순서로 재배열 하는 작업
정렬 실행방법
- 비교식 정렬 : 비교할 각 키값을 한 번에 2개 비교 후 교환함으로써 정렬
- 분배식 정렬 : 키 값을 기준으로 하여 자료를 여러개 부분집합으로 분해, 각 부분집합을 정렬함으로써 전체를 정렬
정렬 장소
- 내부정렬 : 컴퓨터 메모리 내부에서 정렬
- 외부정렬 : 메모리의 외부인 보조 기억장치에서 정렬
내부정렬에서 비교식과 분배식
- 정렬할 자료를 메인 메모리에 올려서 정렬, 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리 용량에 따라 제한
비교식 내부 정렬
1) 교환 : 키를 비교하고 교환, 정렬(선택, 버블, 퀵 정렬)
2) 삽입 : 키를 비교하고 삽입, 정렬(삽입, 셸정렬)
3) 병합 : 키를 비교하고 병합하여 정렬(2-way, n-way병합)
4) 선택 : 이진 트리를 사용하여 정렬(히프, 트리정렬)
분배식 내부정렬
1) 분배 : 키를 구성하는 값을 여러개의 부분집합에 분배하여 정렬(기수정렬)
외부정렬에서 병합 방식
- 정렬할 자료를 보조기억장치에서 정렬
- 대용량의 보조기억장치를 사용하기에 내부정렬보다는 속도가 떨어지지만 내부 정렬로 처리할 수 있는 대용량의 자료에 대한 정렬이 가능
- 파일을 부분 파일로 분리하고 각각 내부정렬 방법으로 정렬하여 병합(2-way, n-way 병합)
※ 모든 경우에 대해 최적인 정렬 알고리즘은 없다. 레코드의 수의 양, 크기, key의 특성(정수, 실수, 문자), 메모리 내부/외부를 고려하여 적합한 정렬 방법을 사용하여야 한다.
- 단순하지만 비효율인 정렬 방법 : 삽입, 선택, 버블, 셸정렬
- 복잡하지만 효율적인 정렬 방법 : 병합, 기수정렬
알고리즘의 성질
- 안정성 : 데이터에 같은 키 값이 여러개 있을 때 정렬후에도 이들의 상대적인 위치가 바뀌지 않는 성질
- 제자리 정렬 : 입력 배열이외에 추가적인 배열을 사용하지 않는 정렬
선택정렬
- 전체 원소들 중애서 기준 위치에 맞는 원소를 선택하여 자리를 교환
1) 전체 원소중 가장 작은 원소를 찾아 첫번째 원소와 자리교환
2) 두번째로 가장 작은 원소 찾아 두번째 원소와 자리교환
3) 이과정 반복 정렬
- 교환을 이용하면 제자리 정렬이지만 새로운 배열에 작은 순으로 정렬하는 방법이라면 제자지 정렬이 아니다
- 시간복잡도는 O(n^2)
- 알고리즘은 매우 간단하지만 효율적인 알고리즘은 아니다
- 안전성을 만족하지 않지만 제자리 정렬이다.
- 자리 이동횟수가 미리 결정되며 메모리 사용 공간은 N개의 원소에 대하여 n개의 메모리를 사용
삽입정렬
- 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치 찾아 삽입
- 정렬할 자료를 2개의 부분집합으로 나누는데 부분집합 s를 정렬된 앞부분의 원소들, 부분집합 u를 아직 정렬되지 않는 나머지 원소들로 두고 정렬되지 않는 부분집합 u의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 s의 마지막 원소부터 비교하면서 위치 찾아 삽입
- 삽입정렬를 반복하면서 부분집합 s의 원소를 하나씩 늘리고 부분집합 u의 원소는 하나씩 감소
- 부분집합 u가 공집합이 되면 삽입정렬 완성
- 복잡도는 입력의 구성에 영향을 받음
- 최선의 입력 O(n)
- 최악의 입력 O(n^2) : 역순일때
- 많은 레코드의 이동을 포함, 레코드의 크기가 클수록 불리
- 안전성을 만족하면서 제자리 정렬
- 레코드가 대부분 이미 정렬되어있을 때 효과적이기에 셸 정렬에서 활용
버블정렬
- 인접한 두개의 원소를 비교하여 순서대로 되어있지 않으면 자리를 서로 교환
- 비교-교환 과정을 리스트의 왼쪽 끝에서 오른쪽 끝까지 반복 or 리스트의 오른쪽 끝에서 왼쪽 끝까지 반
- 끝으로 이동한 레코드를 제외한 왼쪽리스트에 대하여 스캔 과정 반복
- 입력에 구성에 따라 정렬된 리스트, 즉 최선의 경우라면 O(n)
- 역순 정렬 리스트, 최악의 경우라면 O(n^2)
- 안정성을 만족하며 제자리 정렬이다.
- 많은 레코드의 이동을 포함하기에 레코드 크기가 클수록 불리하며 입력 자료가 어느 정도 정렬되어 있다면 효과적으로 사용이 가능하다.
- 메모리 사용공간은 n개의 원소에 대해 n개의 메모리 사용
병합정렬
- 각각 정렬된 두 개의 부분 배열 병합하여 하나의 정렬된 배열을 만듬
- 분할, 정복 전략 사용
1) 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할
2) 정복 : 부분 배열을 정렬, 부분 배열의 크기가 충분히 작지 않으면 순환호출를 이용해서 다시 분할 정복 기법 적용
3) 병합 : 정렬된 부분 배열을 하나의 배열에 병합
- 2-way : 2개의 정렬된 자료의 집합 결합, 하나의 집합으로 만듬
- n-way : n개의 정렬된 자료의 집합을 결합, 하나의 집합으로 만듬
- 하나의 배열이 모두 끝날 때까지 반복하여 마지막으로 남은 배열의 요소를 새로운 배열로 복사-> 병합 완료
- 크기가 n인 리스트를 균등 분배 하기에 log(n)개의 패스(비교-교환)
- 각 패스에서 레코드 n를 비교 -> n번 비교, 이동횟수는 각 패스에서 2n번 이동하기에 전체 시간 복잡도는 2n*log(n)
이므로 O(nlog2^n)
- 효율적이고 입력의 구성과 상관없이 동일한 시간에 정렬
- 안정성을 만족하나 제자리 정렬이 아니다
- 각 단계에서 새로 병합하여 만든 부분 집합을 저장할 공간이 추가로 필요하고 원소 n개에 대해 2xn개의 메모리 공간 사용
퀵정렬
- 정렬할 전체 원소에 대해서 정렬을 수행하지 않고 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할정복
- 왼쪽 부분 집합에는 기준 값보다 작은 원소를 이동, 오른쪽 부분 집합에는 기준 값보다 큰 원소를 이동
- 기준 값을 피벗이라 칭하며 일반적으로 전체 원소중에서 가운데에 위치한 원소 선택
분할) 정렬할 자료들을 기준값을 중심으로 2개로 나눈 부분 집합
정복) 부분집합 안에서 기준 값의 정렬 위치 정함
- 평균적으로 가장 빠른 정렬 방법이지만 안정성을 만족하지는 않음
- 리스트를 2개의 부분리스트로 비균등분할
- 각각의 부분리스트를 다시 퀵정렬(순환호출)
- 최선의 분할(이진트리) : O(nlogn)
- 최악의 분할(경사트리, 정렬된 리스트) : O(n^2)
- 불필요한 데이터 이동을 줄이고 먼거리 데이터를 교환하며 한 번 결정된 피벗들이 추후 연산에서 제외 -> 효율적인 알고리즘
- n개의 원소에 대하여 n개의 메모리 공간 필요
기수정렬
- 요소 비교하지 않고 정렬하는 독특한 기법
- 비교 기반 정렬의 이론적인 시간 복잡도 하한선 돌파
- 10개의 버킷을 사용(0~9)
- 정렬할 원소의 키 값을 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법 반복하여 정렬
- 키 값의 자리수만큼 기수정렬 반복(키 값의 일의 자리 대해 기수정렬 -> 키 값의 십의 자리에 대해 기수정렬...)
- 버킷에 분배된 원소들을 버킷의 순서대로 꺼내서 다음 단계의 기수 정렬을 수행해야 하므로 큐를 사용하여 버킷을 만듬
- 다른 방법은 리코드를 비교하여 정렬을 수행했지만 기수정렬을 레코드를 비교하지 않고 정렬을 수행하기에 비교에 의한 정렬의 하한인 O(nlogn)보다 좋을 수 있다.
- 정렬할 수 있는 레코드의 타입 한정(실수, 한글, 한자 정렬 불가)
- 레코드의 키들이 동일한 길이를 가지는 숫자나 단순 문자여야 하지만 비교 기반의 정렬 방법들은 모든 종류의 키 형태에 적용이 가능하다.
- 원소 n개에 대해서 n개의 메모르 공간을 사용하지만 기수 r에 따라 버킷 공간 추가로 필요함
- n개의 레코드, d개의 자릿수로 이루어진 키를 기수 정렬하게 되면 메인 루프는 자릿수 d번 반복, 큐에 n개 레코드 입력이 수행되기 때문에 시간복잡도 O(dn)이고 대부분 d는 10 이하이기에 거의 선형시간이다.
힙정렬
- 힙트리를 이용한 정렬 방법
- 히프에서는 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제후 반환한다.
- 최대 히프에 대해 원소의 개수만큼 삭제 연산을 수행하고 내림차순 또는 오름차순으로 정렬을 수행한다.
1) 정렬해야할 n개의 요소를 최대 힙에 삽입
2) 한 번에 하나씩 요소를 힙에서 삭제 후 저장
3) 삭제되는 요소들은 값의 증가되는 순서( 최소 힙의 경우)
- 원소 n개에 대해서 n개의 메모리 공간을 사용하고 크기 n의 힙 저장 공간이 필요하다.
- n개의 노드에 대해서 완전이진트리는 log2^(n+1)의 레벨을 가지므로 완전이진트리를 힙으로 구성하는 평균 시간은
O(log2^n)이고 n개의 노드에 대해서 n 번의 힙 재구성 작업을 수행해야 하므로 평균 시간 복잡도는 O(nlog2^n)
- 전체의 정렬이 아니라 가장 큰 값 몇 개만 필요할 때 특히 유용하다.
사진 출처:
쉽게 배우는 C 자료구조 | 생능출판사
코딩을 조금이라도 해 보았다면 프로그래밍이 자료(data)를 주로 다루는 것임을 알 수 있을 것이다. 우리가 프로그램을 개발할 때 가장 먼저 해야 할 일은 처리할 자료를 컴퓨터가 잘 다룰 수 있
www.booksr.co.kr
