#3. 합병 정렬, 퀵 정렬

합병 정렬

 

ex) n개의 양의 정수를 입력받아 원소들을 합병정렬하여 오름차순으로 정렬

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void makeList (int* L, int n) {
    for (int i = 0; i < n; i++) {
        scanf("%d", &L[i]);
    }
}

void merge (int* L1, int* L2, int left, int mid, int right) {
    int i ,j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    while (i <= mid && j <= right) {
        if (L1[i] <= L1[j]) 
            L2[k++] = L1[i++];
        else 
            L2[k++] = L1[j++];
    }

    if (i > mid) {
        for (l = j; l <= right; l++) {
            L2[k++] = L1[l];
        }
    }
    else {
        for (l = i; l <= mid; l++) {
            L2[k++] = L1[l];
        }
    }
    
    for (l = left; l <= right; l++) {
        L1[l] = L2[l];
    }
}

void mergeSort (int* L1, int* L2, int left, int right) {
    
    int mid;

    if (left < right) {
        mid = (left + right) / 2;
        mergeSort(L1, L2, left, mid);
        mergeSort(L1, L2, mid + 1, right);
        merge(L1, L2, left, mid, right);
    }
}

void printList (int* L, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", L[i]);
    }
    printf("\n");
}


//배열로 구현
int main () {

    int n;
    scanf("%d", &n);

    int* L1 = (int*)malloc(sizeof(int) * n);
    int* L2 = (int*)malloc(sizeof(int) * n);

    makeList(L1, n);

    mergeSort(L1, L2, 0, n - 1);
    printList(L2, n);
    

    return 0;
}

 

 

 

 

퀵 정렬

 

: 분할통치법에 기초한 정렬 알고리즘

 

divide : 기준원소p(보통 마지막 원소)를 선택하여 L을 3부분으로 분할  

 

LT : p보다 작은 원소들

EQ : p와 같은 원소들

GT : p보다 큰 원소들

 

 

재귀(recur) : LT, GT 정렬

통치(conquer) : LT, EQ, GT 결합

 

 

 

list 분할(partition)

 

1. L로부터 각 원소 e 삭제

2. e를 기준원소인 p와 비교결과에 따라 부list LT,EQ,GT에 삽입

 

 

 

제자리 퀵 정렬

 

 

제자리 분할

 

 

ex) n개의 양의 정수를 입력받아 퀵 정렬로 정렬. pivot의 위치는 random하게 선택

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

void makeList (int* L, int n) {
    for (int i = 0; i < n; i++) {
        scanf("%d", &L[i]);
    }
}

void printList (int* L, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", L[i]);
    }
    printf("\n");
}

int partition (int *L, int left, int right, int p) {
    
    int pivot, tmp, low, high;

    pivot = L[p];
    SWAP(L[p], L[right], tmp);    //pivot위치 변경(오른쪽)

    low = left;
    high = right - 1;

    while (low <= high) {
        while (low <= high && L[low] <= pivot) {
            low++;
        }
        while (high >= low && L[high] >= pivot) {
            high--;
        }
        if (low < high) {
            SWAP(L[low], L[high], tmp);
        }
    }

    //pivot위치 정함
    SWAP(L[low], L[right], tmp);

    return low;
}

void quickSort  (int* L, int left, int right) {
    if (left < right) {
        int p = rand() % (right - left + 1) + left;     //pivot 설정
        int q = partition(L, left, right, p);       //sort후 pivot 위치
        quickSort(L, left, q - 1);
        quickSort(L, q + 1, right);
    }
}

//배열로 구현
int main () {

    int n;
    scanf("%d", &n);

    int* L = (int*)malloc(sizeof(int) * n);

    makeList(L, n);
    // printList(L, n);

    quickSort(L, 0, n-1);
    printList(L, n);


    return 0;
}