개발일지0813
자료구조 - 정렬(1) 본문
정렬의 종류
정렬이란 무작위로 나열된 자료를 특정 기준을 가지고 순차적으로 재배열하는 것을 의미한다. 이때 key라는 것이 존재하는데, 키는 자료를 정렬하는데 사용하는 기준이 되는 특정 값이 된다.
정렬은 정렬 장소에 따라 크게 내부정렬과 외부정렬로 나눌수가 있다.
외부정렬의 경우 메모리의 외부인 보조기억장치에서 정렬을 하는것이 특징이다. 보조기억장치에서 정렬을 하기 때문에 내부정렬보다 비교적 속도는 떨어지지만 대용량의 자료를 정렬하는 것이 가능하다. 대표적인 예로는 병합 방식을 이용한 정렬이 있다.
내부 정렬의 경우 메인 메모리에 올려서 빠르게, 비교적 적은 양의 데이터를 정렬하는 것이 특징입니다. 대표적인 예로는 앞으로 다룰 선택정렬, 버블정렬, 퀵 정렬, 삽입 정렬, 셸 정렬, 병합정렬, 히프 정렬, 트리 정렬, 기수 정렬이 있습니다.
선택정렬
정의
전체 원소들 중에서 기준 위치에 맞는 원소를 선택하며 자리를 교환하는 방식이다.
수행방법
수행 방법으로는 다음과 같다.
1. 전체 원소중에서 가장 작은 원소를 찾아 첫번째 원소와 자리 교환
2. 두번째로 작은 원소 찾아 선택하여 두번째 원소와 자리 교환
3. 이 과정을 반복하면서 정렬 완성
의사코드
의사코드는 아래와 같다.
selectionSort(a[], n)
for( i<-1; i<n; i<-i+1) do {
a[i], ... , a[n-1] 중에서 가장 작은 원소 a[k]를 선택해 a[i]와 교환
}
end selectionSort()
성능
메모리 사용공간은 n개의 원소에 대하여 n개의메모리를 사용한다.
시간 복잡도는 O(n^2)가 된다.
버블정렬
정의
인접한 두개의 우너소를 비교하여 자리를 교환하는 방식의 정렬
수행방법
수행 방법으로는 다음과 같다.
1. 첫번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
2. 이를 마지막 원소 하나만 남을 때 까지 반복한다
의사코드
의사코드는 아래와 같다.
bubbleSort(a[], n)
for( i<=n-1; i>=0; i<= i-1) do {
for(j<=0; j<i; j<=j+1) do {
if(a[j] > a[j+1]) then {
temp <- a[j];
a[j] <- a[j+1];
a[j+1] <- temp;
}
}
}
end bubbleSort()
성능
메모리 사용공간은 n개의 원소에 대하여 n개의메모리를 사용한다.
시간 복잡도는 O(n^2)가 된다.
퀵정렬
정의
정렬할 전체 원소에 대해서 정렬을 수행하지 않고 , 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할 하여 정렬하는 방법. 이때 기준 값을 pivot피봇이라 부른다. 피봇은 일반적으로 전체 원소 중에서가운데에 위치한 원소를 선택한다.
수행방법
수행 방법은 크게 두가지로 나뉘어진다.
- 분할 : 정렬 할 자료들을 기준값을 중심으로 두개로 나누어 부분집합을 만듦.
- 정복: 부분 집합 안에서 기준값의 정렬 위치를 정함
1. 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇보다 크거나 같은 원소를 찾아 L로 표시한다. 단, L은 R과만나면 더 이상 오른쪽으로 이동하지 못하고 멈춘다.
2. 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 표기한다. 단, R은 L과 만나면 더 이상 왼쪽으로 이동하지 못하고 멈춘다.
3. -a 1과 2에서 찾은 L원소과 R원소가 있는 경우, 서로 교환 하고 L 과 R의 현재 위치에서 1 과 2 작업을 다시 수행한다.
3. -b 1~2를 수행하면서 L과 R이 같은 원소에서 만나 멈춘 경우, 피봇과 R의 원소를 서로 교환한다. 교환된 자리를 피봇 위치로 확정하고 현재 단계의 퀵정렬을 끝낸다.
4. 피봇의 확정된 위치를 기준으로 만들어진 새로운 왼쪽 부분집합과 오른쪽 부분집합에 대해 1~3의 퀵 정렬을 순환적으로 반복수행하는데, 모든 부분집합의 크기가 1이하가 되면 전체 퀵 정렬을 종료한다
의사코드
의사코드는 아래와 같다.
quickSort(a[], begin, end)
if(m < n){
p<-partition(a, begin, end);
quickSort(a[], begin, p-1);
quickSort(a[], p+1, end);
}
end quickSort()
partition(a[], begin, end)
pivot <-(begin + end) /2;
L <- begin;
R <-end;
while(L < R) do{
while(a[L] <a[pivot] and L<R) do L++;
while (a[R] >= a[pivot] and L<R) do R--;
if(L<R) then { //L의 원소와 R의 원소 교환
temp <- a[L];
a[L] <- a[R];
a[R] <- temp;
}
}
temp <- a[pivot];
a[pivot] <- a[R];
a[R] <- temp;
return R;
end partition()
성능
메모리 사용공간은 n개의 원소에 대하여 n개의메모리를 사용한다.
시간 복잡도는 O(nlogn)가 된다.
* 오늘 강의 들으며 지적 받았는데 worst case 시간 복잡도는 O(nlogn) 이 아니라 O(N^2)이라하네요
삽입정렬
정의
정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법
수행방법
정렬할 자료를 두개의 부분 집합 S (sorted subset) 와 U (unsorted subset)로 가정
- 부분집합 S: 정렬된 앞부분의 원소들
- 부분집합 U: 아직 정렬 되지 않은 나머지 원소들
1. 정렬되지 않은 부분 집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분 집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입
2. 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 함. 부분집합 U가 공집합이 되면 삽입정렬이 완성
의사코드
의사코드는 아래와 같다.
insertionSort(a[], n)
for(i <- 1; i<n; i <- i + 1) do {
temp <- a[i];
j <- i;
if(a[j - 1] > temp) then move <- true; // 삽입자리를 만들기 위해 이동할 원소 표시
else move <- false;
while (move and j>0) do {
a[j] <- a[j - 1];
j <- j - 1;
}
a[j] <- temp;
}
end insertionSort()
성능
메모리 사용공간은 n개의 원소에 대하여 n개의메모리를 사용한다.
시간 복잡도는 O(n^2)가 된다.
셸정렬
정의
일정한 간격(인터벌)으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법
--> 전체 원소에 대해서 삽입 정렬을 수행하는 것 보다 부분집합으로 나누어 정렬하게 되면 비교연산과 교환 연산 감소
수행방법
셸 정렬의 부분집합
- 부분집합의 기준이 되는 간격을 매개 변수 h에 저장
- 한단계가 수행 될 때 마다 h의 값을 감소 시키고 셸 정렬을 순환 호출( until h becomes 1)
셸 정렬의 성능은 매개변수 h의 값에 따라 달라짐
- 정렬할 자료의 특성에 따라 매개변수 생성 함수를 사용
- 일반적으로 사용하는 h의 값은 원소 개수의 1/2을 가용하고 한 단계 수행 될 때 마다 h의 값을 반으로 감소시키면서 반복 수행
의사코드
의사코드는 아래와 같다.
shellSort(a[], n)
interval <- n;
while(interval >=1) do {
interval <- interval/2;
for(i <- 0; i<interval; i<- i+1) do {
intervalSort(a[], i, n, interval);
}
}
end shellSort()
intervalSort(a[], begin, end, interval)
for(i <- begin + interval; i<= end; i <- i + interval) do {
item <- a[i];
for(j <- i - interval; j>=begin and item < a[j]; j <- j - interval) do
a[j+interval] <- a[j];
a[j + interval] <- item;
}
end intervalSort()
성능
메모리 사용공간은 n개의 원소에 대하여 n개의 메모리와 매개변수 h를 사용한다.
시간 복잡도는 매개변수 h의 값에 따라 결정 되며 일반적으로 O(n^1.25)가 된다.
* 해당 글은 임상준교수님의 자료구조 강의노트를 참고하여 작성되었습니다