정렬 (Sort)
순서 없이 배열된 자료를 작은 것부터 큰 것 순서인 오름차순이나 큰 것부터 작은 것 순서인 내림차순으로 재배열하는 것
키(key): 자료를 정렬하는데 사용하는 기준이 되는 특정 값
정렬 방식의 분류
내부 정렬 (internal sort)
정렬할 자료를 메인 메모리에 올려서 정렬하는 방식
정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨
내부 정렬의 분류
외부 정렬 (external sort)
정렬할 자료를 보조 기억장치에서 정렬하는 방식
대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬 가능
외부 정렬 방식
병합 방식: 파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬항 ㅕ병합하는 정렬 방식 (2-way 병합, n-way 병합)
선택 정렬 (selection sort)
전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬
수행 방법
전체 원소 중에서 가장 작은 원소를 찾아 첫 번째 원소와 자리를 교환
두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환
세 번째로 작은 원소를 찾아 선택하여 세 번째 원소와 자리를 교환
이 과정을 반복하면서 정렬을 완성
메모리 사용공간: n개의 원소에 대하여 n개의 메모리 사용
비교횟수
1단계: 첫 번째 원소를 기준으로 n개의 원소 비교
2단계: 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교
3단계: 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교
i단계: i 번째 원소를 기준으로 n-i개의 원소 비교
버블 정렬 (bubble sort)
인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블 정렬이라고 함.
메모리 사용공간: n개의 원소에 대하여 n개의 메모리 사용
연산 시간
최선의 경우: 자료가 이미 정렬되어 있는 경우
비교횟수: i번째 원소를 (n-i)번 비교하므로, n(n-1)/2 번
자리교환 횟수: 자리교환이 발생하지 않음
최악의 경우: 자료가 역순으로 정렬되어있는 경우
비교횟수: i번째 원소를 (n-i)번 비교하므로, n(n-1)/2 번
자리교환횟수: i번째 원소를 (n-i)번 교환하므로, n(n-1)/2 번
최선의 경우와 최악의 경우에 대한 평균 시간 복잡도를 빅-오 표기법으로 나타내면 O(n^2)이 됨
퀵 정렬 (quick sort)
정렬할 전체 원소에 대해서 정렬을 수행하지 않고 ,기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법
왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킴
기준 값: 피봇(pivot) - 일반적으로 전체 원소 중에서 가운데에 위치한 원소를 선택
퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성
분할(divide)
- 정렬할 자료들을 기준값을 중심으로 두 개로 나눠 부분집합을 만듦
정복(conquer)
- 부분집합 안에서 기준값의 정렬 위치를 정함
퀵 정렬 동작 규칙
1. 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시한다. 단, L은 R과 만나면 더이상 오른쪽으로 이동하지 못하고 멈춘다.
2. 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시한다. 단, R은 L과 만나면 더이상 왼쪽으로 이동하지 못하고 멈춘다.
3-a. 1과 2에서 찾은 L원소와 R원소가 있는 경우, 서로 교환하고 L과 R의 현재 위치에서 1과 2작업을 다시 수행한다.
3-b. 1~2를 수행하면서 L과 R이 같은 원소에서 만나 멈춘 경우, 피봇과 R의 원소를 서로 교환한다. 교환된 자리를 피봇 위치로 확정하고 현재 단계의 퀵 정렬을 끝낸다.
피봇의 확장된 위치를 기준으로 만들어진 새로운 왼쪽 부분집합과 오른쪽 부분집합에 대해서 1~3의 퀵 정렬을 순환적으로 반복 수행하는데, 모든 부분집합의 크기가 1이하가 되면 전체 퀵 정렬을 종료한다.
메모리 사용공간: n개의 원소에 대하여 n개의 메모리 사용
연산 시간
최선의 경우
피봇에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 n/2개씩 2등분이 되는 경우가 반복되어 수행 단계 수가 최소가 되는 경우
최악의 경우
피봇에 의해 원소들을 분할하였을 때 한 개와 n-1개로 한쪽으로 치우쳐 분할되는 경우가 반복되어 수행 단계 수가 최대가 되는 경우
평균 시간 복잡도
같은 시간 복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 더 빨리 실행되어 실행 시간 성능이 좋은 정렬 방법임.
삽입 정렬 (insert sort)
정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법
정렬할 자료를 두 개의 부분집합 S(Sorted Subset)와 U(Unsorted Subset)로 가정
부분집합 S : 정렬된 앞부분의 원소들
부분집합 U : 아직 정렬되지 않은 나머지 원소들
정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입
삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 함. 부분집합 U가 공집합이 되면 삽입 정렬이 완성
메모리 사용공간
n개의 원소에 대하여 n개의 메모리 사용
연산 시간
최선의 경우 : 원소들이 이미 정렬되어있어서 비교횟수가 최소인 경우
− 이미 정렬되어있는 경우에는 바로 앞자리 원소와 한번만 비교
− 전체 비교횟수 = n-1
− 시간 복잡도 : O(n)
최악의 경우 : 모든 원소가 역순으로 되어있어서 비교횟수가 최대인 경우
− 전체 비교횟수 = 1+2+3+ ⋯ +(n-1) = n(n-1)/2
− 시간 복잡도 : O(n^2)
삽입 정렬의 평균 비교횟수 = n(n-1)/4
평균 시간 복잡도 : O(n^2)
셸 정렬 (shell sort)
일정한 간격interval으로 떨어져있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법
전체 원소에 대해서 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 정렬하게 되면 비교연산과 교환연산 감소
셸 정렬의 부분집합
부분집합의 기준이 되는 간격을 매개변수 h에 저장
한 단계가 수행될 때마다 h의 값을 감소시키고 셸 정렬을 순환 호출
− h가 1이 될 때까지 반복
셸 정렬의 성능은 매개변수 h의 값에 따라 달라짐
정렬할 자료의 특성에 따라 매개변수 생성 함수를 사용
일반적으로 사용하는 h의 값은 원소 개수의 1/2을 사용하고 한 단계 수행될 때마다 h의 값을 반으로 감소시키면서 반복 수행
메모리 사용공간
n개의 원소에 대하여 n개의 메모리와 매개변수 h에 대한 저장공간 사용
연산 시간
비교횟수
− 처음 원소의 상태에 상관없이 매개변수 h에 의해 결정일반적인 시간 복잡도 : O(n^1.25)~O(n^1.5)
셸 정렬은 삽입 정렬의 시간 복잡도 O(n^2) 보다 개선된 정렬 방법
병합 정렬 (merge sort)
여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법
부분집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 후에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer) 기법 사용
병합 정렬 방법의 종류
2-way 병합 : 2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법
n-way 병합 : n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법
2-way 병합 정렬 과정
메모리 사용공간
각 단계에서 새로 병합하여 만든 부분집합을 저장할 공간이 추가로 필요
원소 n개에 대해서 (2 x n)개의 메모리 공간 사용
연산 시간
분할 단계 : n개의 원소를 두개로 분할하기 위해서 (log2 n)번의 단계 수행
병합 단계 : 부분집합의 원소를 비교하면서 병합하는 단계에서 최대 n번의
비교 연산 수행전체 병합 정렬의 시간 복잡도 : O(n (log2 n))
기수 정렬 (radix sort)
원소의 키값을 나타내는 기수를 이용한 정렬 방법
정렬할 원소의 키 값에 해당하는 버킷bucket에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하면서 정렬
− 원소의 키를 표현하는 기수만큼의 버킷 사용
− 예) 10진수로 표현된 키 값을 가진 원소들을 정렬할 때에는 0부터 9까지 10개의 버킷 사용
키 값의 자리수 만큼 기수 정렬을 반복
− 키 값의 일의 자리에 대해서 기수 정렬을 수행하고,
− 다음 단계에서는 키 값의 십의 자리에 대해서,
− 그리고 그 다음 단계에서는 백의 자리에 대해서 기수 정렬 수행
한 단계가 끝날 때마다 버킷에 분배된 원소들을 버킷의 순서대로 꺼내서 다음 단계의 기수 정렬을 수행해야 하므로 큐를 사용하여 버킷을 만듦
메모리 사용 공간
원소 n개에 대해서 n개의 메모리 공간 사용
기수 r에 따라 버킷 공간이 추가로 필요
연산 시간
연산 시간은 정렬할 원소의 수 n과 키 값의 자릿수 d와 버킷의 수를 결정하는 기수 r에 따라서 달라진다.
− 정렬할 원소 n개를 r개의 버킷에 분배하는 작업 : (n+r)
− 이 작업을 자릿수 d 만큼 반복
수행할 전체 작업 : d(n+r)
시간 복잡도 : O(d(n+r))
힙 정렬 (heap sort)
힙 자료구조를 이용한 정렬 방법
힙에서는 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환
최대 힙에 대해서 원소의 개수만큼 삭제 연산을 수행하여 내림차순으로 정렬 수행
최소 힙에 대해서 원소의 개수만큼 삭제 연산을 수행하여 오름차순으로 정렬 수행
메모리 사용공간
원소 n개에 대해서 n개의 메모리 공간 사용
크기 n의 힙 저장 공간
연산 시간
힙 재구성 연산 시간
− n개의 노드에 대해서 완전 이진 트리는 (log2(n+1))의 레벨을 가지므로 완전 이진 트리를 힙으로 구성하는 평균시간은 O(log2 n)
− n개의 노드에 대해서 n번의 힙 재구성 작업 수행
평균 시간 복잡도 : O(n(log2 n))
트리 정렬 (tree sort)
이진 탐색 트리를 이용하여 정렬하는 방법
트리 정렬 수행 방법
정렬할 원소들을 이진 탐색 트리로 구성
이진 탐색 트리를 중위 우선 순회 함
− 중위 순회 경로가 오름차순 정렬이 됨
메모리 사용공간
원소 n개에 대해서 n개의 메모리 공간 사용
크기 n의 이진 탐색 트리 저장 공간
연산 시간
노드 한 개에 대한 이진 탐색 트리 구성 시간 : O(log2 n)
n개의 노드에 대한 시간 복잡도 : O(n(log2 n))
Beginner_Developer