정렬 알고리즘 2

 안정 정렬

비교한 값이 같을 때 서로 바뀌지 않는 정렬법을 안정 정렬이라고 한다

병합 정렬(Merge Sort)

• 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 봄
• 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다

int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9};
int tmparr[10];

void sort(int, int);
void merge(int, int);

void sort(int start, int end)
{
    if(end > start)
    {
        sort(start, (start + end) / 2);
        sort((start + end) / 2 + 1, end);
    }
    merge(start, end);
}

void merge(int start, int end) //여기가 진짜다.
{
    int i = start, j = (start + end) / 2 + 1;
    int count = start;
    while(i <= (start + end) / 2 && j <= end)
    {
        if(arr[i] > arr[j])
            tmparr[count++] = arr[j++];
        else
            tmparr[count++] = arr[i++];
    }
    while(i <= (start + end) / 2)
        tmparr[count++] = arr[i++];
    while(j <= end)
        tmparr[count++] = arr[j++];
    for(i = start; i <= end; i++)
        arr[i] = tmparr[i];
}

퀵 정렬

// 초기값 left=0 / right=arr.size-1
public static void quickSort(int[] arr, int left, int right){
        int i, j, pivot, tmp;

        if (left < right) {
            i = left;
            j = right;
            pivot = arr[left];
            //분할 과정
            while (i < j) {
                while (arr[j] > pivot) j--;
                while (i < j && arr[i] <= pivot) i++;

                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
            arr[left] = arr[i];
            arr[i] = pivot;
            //정렬 과정
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
}