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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
 
void Swap(int arr[], int idx1, int idx2)
{
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}    
 
int MedianOfThree(int arr[], int left, int right)
{
    int samples[3] = {left, (left+right)/2, right};
 
    if(arr[samples[0]] > arr[samples[1]])
        Swap(samples, 0, 1);
 
    if(arr[samples[1]] > arr[samples[2]])
        Swap(samples, 1, 2);
 
    if(arr[samples[0]] > arr[samples[1]])
        Swap(samples, 0, 1);
 
    return samples[1];
}
 
int Partition(int arr[], int left, int right)
{
    int pIdx = MedianOfThree(arr, left, right);   // 피벗을 선택!
    int pivot = arr[pIdx];
 
    int low = left+1;
    int high = right;
 
    Swap(arr, left, pIdx);    // 피벗을 가장 왼쪽으로 이동
 
    printf("피벗: %d \n", pivot);
 
    while(low <= high)    // 교차되지 않을 때까지 반복
    {    
        while(pivot >= arr[low] && low <= right)
            low++;
 
        while(pivot <= arr[high] && high >= (left+1))
            high--;
 
        if(low <= high)    // 교차되지 않은 상태라면 Swap 실행
            Swap(arr, low, high);    // low와 high가 가리키는 대상 교환
    }
 
    Swap(arr, left, high);    // 피벗과 high가 가리키는 대상 교환
    return high;    // 옮겨진 피벗의 위치 정보 반환
}
 
void QuickSort(int arr[], int left, int right)
{
    if(left < right)
    {
        int pivot = Partition(arr, left, right);    // 둘로 나눠서 
        QuickSort(arr, left, pivot-1);    // 왼쪽 영역을 정렬
        QuickSort(arr, pivot+1, right);    // 오른쪽 영역을 정렬
    }
}
 
int main(void)
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
 
    int len = sizeof(arr) / sizeof(int);
    int i;
 
    QuickSort(arr, 0, sizeof(arr)/sizeof(int)-1);
 
    for(i=0; i<len; i++)
        printf("%d ", arr[i]);
 
    printf("\n");
    return 0;
}
cs


저작자표시
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
void Merge(long long int *arr, int left, int middle, int right)
{
    int i;
    int l_idx = left;
    int r_idx = middle + 1;
    int idx = left;
    int *temp_arr = (int *)malloc(sizeof(int) * (right + 1));
 
    while ((l_idx <= middle) && (r_idx <= right))
    {
        if (arr[l_idx] > arr[r_idx]) temp_arr[idx++] = arr[r_idx++];
        else temp_arr[idx++] = arr[l_idx++];
    }
 
    while (l_idx <= middle) temp_arr[idx++] = arr[l_idx++];
    while (r_idx <= right) temp_arr[idx++] = arr[r_idx++];
 
    for (i = left; i <= right; i++)
        arr[i] = temp_arr[i];
 
    free(temp_arr);
}
 
void MergeSort(long long int *arr, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        MergeSort(arr, left, middle);
        MergeSort(arr, middle + 1, right);
        Merge(arr, left, middle, right);
    }
}
cs


저작자표시

-128 ~ 127

-1 ~ 254

0 ~ 255




0000 0001 = 1

1111 1111 = -1


0000 0010 = 2

1111 1110 = -2




0111 1111 = 127

1000 0001 = -127

1000 0000 = -128

저작자표시

+ Recent posts

티스토리툴바