정렬 (sort) : 2개 이상의 자료를 오름차순이나 내림차순으로 재배열하는 것
키 (key) : 자료를 정렬하는데 사용하는 기준
선택 정렬 (Selection Sort)
전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식
- 전체 원소 중에서 가장 작은 원소를 찾아서 선택하여 첫 번째 원소와 자리를 교환
- 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환
- 그 다음에는 세 번째로 작은 원소를 찾아서 세 번째 원소와 자리를 교환
- 이 과정을 반복하면서 정렬을 완성
void selectionSort(int a[ ],int n) {
int i, j, min, temp;
for (i=0; i<n-1; i++) {
min = i;
for (j=i+1; j<n; j++) {
if (a[j]<a[min]) min = j;
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}메모리 사용공간 : n
시간 복잡도 : O(n^2)
삽입 정렬 (Insert Sort)
정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법
- 부분집합 S : 정렬된 앞부분의 원소들
- 부분집합 U : 아직 정렬되지 않은 나머지 원소들
- U의 원소를 하나씩 꺼내서 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입
- 이 과정을 반복하면서 정렬을 완성
메모리 사용공간 : n
시간 복잡도 : 최선의 경우 O(n) 최악의 경우 O(n^2)
퀵 정렬 (quick sort)
- 부분 집합으로 분할하기 위해서 L과 R을 사용
- 왼쪽 끝에서 오른쪽으로 움직이면서 크기를 비교하여 피봇 보다 크거나 같 은 원소를 찾아 L로 표시
- 오른쪽 끝에서 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾아 R로 표시
- L이 가리키는 원소와 R이 가리키는 원소를 서로 교환
- L와 R이 만나게 되면 피봇과 L의 원소를 서로 교환하고, 교환한 위치를 피봇 의 위치로 확정
- 피봇의 확정된 위치를 기준으로 만들어진 왼쪽 부분 집합과 오른쪽 부분 집합 에 대해서 퀵 정렬을 순환적으로 반복 수행하는데 부분 집합의 크기가 1 이하 가 되면 퀵 정렬을 종료
quickSort(a[], begin, end)
if (begin < end) then {
p ← partition(a, begin, end);
quickSort(a[], begin, p-1);
quickSort(a[], p+1, end);
}
end quickSort() partiton(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;
if(L=pivot) then pivot ← R
}
}
temp ← a[pivot]; // L의 원소와 피봇 원소 교환
a[pivot] ← a[L];
a[L] ← temp;
return L;
end partition()메모리 사용공간 : n
시간 복잡도 : O(n log2n)
버블 정렬 (bubble sort)
인접한 두 개의 원소를 비교하여 자리를 교환하는 방식
메모리 사용공간 : n
시간 복잡도 : O(n^2)
셀 정렬 (shell sort)
일정한 간격으로 부분집합을 구성하고 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법
히프 정렬 (heap sort)
- 정렬할 원소들을 입력하여 최대 히프 구성
- 히프에 대해서 삭제 연산을 수행하여 얻은 원소를 마지막 자리에 배치
- 나머지 원소에 대해서 다시 최대 히프로 재구성 원소의 개수만큼 반복 수행
'University > Data Structure' 카테고리의 다른 글
| 그래프 (Graph) (0) | 2019.06.16 |
|---|---|
| 트리 (Tree) (0) | 2019.06.15 |
| 자료구조 (Data Structure) (0) | 2019.06.15 |