- quick sort
 




- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현

- 합병 정렬과 달리 비균등하게 분할

- 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택하고 피벗을 기준으로 분할

- 속도가 빠르고 추가 메모리 공간을 필요로 하지 않음, 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 등에 기인

- 시간 복잡도 분석
 : 재귀 호출의 깊이는 
 : 각각의 패스에서 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어짐, 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시
 : 총 시간 복잡도는 

- 단점으로
 : 정렬된 리스트에 대해서는 오히려 수행시간이  되버리는 불균형 분할 발생 -> 단순히 왼쪽 데이터를 피벗으로 사용하지 않고 리스트 내의 몇개의 데이터 중에서 크기순으로 중간 값(median)을 피벗으로 선택하여 극복 (왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기순으로 중간값을 선택하는 방법(median of three)


- CODE

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include < iostream>
using namespace std;
 
int arr[1000001];
 
int partition(int *a, int low, int high) {
    int pivotIndex = low + (high - low) / 2;
    int pivotValue = arr[pivotIndex];
    swap(arr[pivotIndex], arr[high]);
    int pos = low;
    for (int i = low; i < high; i++) {
        if (a[i] < pivotValue) {
            swap(a[i], a[pos]);
            pos++;
        }
    }
    swap(arr[pos], arr[high]);
     
    return pos;
}
 
void quicksort(int *a, int low, int high){
    if (low < high) {
        int pivot = partition(a, low, high);
        quicksort(a, low, pivot - 1);
        quicksort(a, pivot + 1, high);
    }
}
 
int main()
{
    int n;
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    quicksort(arr, 0, n - 1);
 
    for (int i = 0; i < n; i++) {
        cout << arr[i] << "\n";
    }
 
    return 0;
}


'Algorithm' 카테고리의 다른 글

알고리즘 - 기수 정렬  (0) 2015.11.12
알고리즘 - 힙 정렬  (0) 2015.11.12
알고리즘 - 합병 정렬  (0) 2015.11.12
알고리즘 - 셸 정렬  (0) 2015.11.12
알고리즘 - 버블 정렬  (0) 2015.11.12

- merge sort




- 분할 정복(divide and conquer) 방법, 보통 재귀를 이용하여 구현

- 분할(divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  정복(conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법 적용
  결합(combine): 정렬된 부분 배열들을 하나의 배열에 합병

- 시간복잡도 분석
 : 배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산이 수행되지 않는다. 재귀 호출의 깊이는 
 : 합병단계에서 비교 연산 최대 n번, 임시 배열에 복사했다가 다시 가져와야하는 이동 연산 n 번으로 총 2n번 레코드의 이동 발생
 : 총 시간 복잡도는 

- 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일 (데이터의 분포에 영향을 덜 받는 안정적인 정렬 방법)

- 단점으로
  : 임시 배열이 필요함
  : 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래 -> 연결리스트로 극복


- CODE

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
using namespace std;
 
int arr[1000001];
int save[1000001];
 
void merge_sort(int* a, int start, int end) {
    if (start == end) {
        return;
    }
    else if (start + 1 == end) {
        if (a[start] > a[end]) {
            swap(a[start], a[end]);
        }
        return;
    }
 
    // divide
    int mid = (start + end) / 2;
    merge_sort(a, start, mid);
    merge_sort(a, mid + 1, end);
    int left = start;
    int right = mid + 1;
    int k = 0;
 
    // conquer
    while (left <= mid && right <= end) {
        if (a[left] <= a[right]) {
            save[k++] = a[left++];
        }
        else {
            save[k++] = a[right++];
        }
    }
    while (left <= mid) {
        save[k++] = a[left++];
    }
    while (right <= end) {
        save[k++] = a[right++];
    }
 
    // combine
    for (int i = start; i <= end; i++) {
        a[i] = save[i - start];
    }
}
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    merge_sort(arr, 0, n - 1);
 
    for (int i = 0; i < n; i++)
        cout << arr[i] << "\n";
 
    return 0;
}


'Algorithm' 카테고리의 다른 글

알고리즘 - 힙 정렬  (0) 2015.11.12
알고리즘 - 퀵 정렬  (0) 2015.11.12
알고리즘 - 셸 정렬  (0) 2015.11.12
알고리즘 - 버블 정렬  (0) 2015.11.12
알고리즘 - 삽입 정렬  (0) 2015.11.12

- shell sort

- 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것을 착안한 방법

- 셸 정렬은 삽입 정렬의 보다 빠르다.

- 전체의 리스트를 한 번에 정렬하지 않고, 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬

- gap만큼 떨어진 요소들을 삽입 정렬하고, gap을 반씩 줄여가면서 1까지 반복

- 최악의 경우의 시간복잡도 지만 평균적인 경우는 로 삽입 정렬보다 빠르다

출처: http://wonjayk.tistory.com/220


'Algorithm' 카테고리의 다른 글

알고리즘 - 퀵 정렬  (0) 2015.11.12
알고리즘 - 합병 정렬  (0) 2015.11.12
알고리즘 - 버블 정렬  (0) 2015.11.12
알고리즘 - 삽입 정렬  (0) 2015.11.12
알고리즘 - 선택 정렬  (0) 2015.11.12

+ Recent posts

티스토리툴바