Data Structure - Sorting ( Bubble, Selection Sort )

Bubble Sort

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.
  • 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 방법입니다.
• 선택 정렬과 기본 개념이 유사합니다.

 

• 버블 정렬의 기본적인 과정을 서술하겠습니다.
  • 버블 정렬은 첫 번쨰 자료와 두 번째 자료를, 두 번쨰 자료와 세번째 자료를, 세 번째와 네 번째를, ...이런 식으로 (마지막 - 1)번쨰 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬합니다.
  • 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다.

바로 코드로 보여드리겠습니다.

/bubble_sort.c

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

#define ARR_SIZE 100

#define HEAP_FULL(n) (n == ARR_SIZE - 1)
#define HEAP_EMPTY(n) (!n)

int sorted[ARR_SIZE];

typedef struct
{
    int key;
} element;

element heap[ARR_SIZE];

void push(element item, int *n)
{
    int i;
    // 만약 힙이 꽉 차있다면
    if (HEAP_FULL(*n))
    {
        fprintf(stderr, "The heap is full. \n");
        exit(EXIT_FAILURE);
    }
    i = ++(*n);
    while ((i != 1) && (item.key > heap[i / 2].key))
    {
        heap[i] = heap[i / 2];
        i /= 2;
    }
    heap[i] = item;
}

element pop(int *n)
{
    int parent, child;
    element item, temp;
    if (HEAP_EMPTY(*n))
    {
        fprintf(stderr, "The heap is empty. \n");
        exit(EXIT_FAILURE);
    }
    item = heap[1];
    temp = heap[(*n)--];
    parent = 1;
    child = 2;
    while (child <= *n)
    {
        if ((child < *n) && (heap[child].key < heap[child + 1].key))
            child++;

        if (temp.key >= heap[child].key)
            break;

        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return item;
}

void heap_sort(int a[], int n)
{
    int count = 0, i;
    element newElement = {0};

    // 우선 int 배열의 값을 하나씩 heap에 집어 넣어주어야 한다.
    for (int i = 0; i < n; i++)
    {
        newElement.key = a[i];
        push(newElement, &count);
    }

    for (i = (n - 1); i >= 0; i--)
    {
        a[i] = pop(&count).key;
    }
}

int seqSearch(int a[], int k, int n)
{
    int i;
    for (i = 1; i < n && a[i] != k; i++)
        ;

    if (i >= n)
        return -1;
    return i;
}

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void insertionSort(int a[], int n)
{
    /* sort a[0:n - 1] into nondecreasing order( 오름 차순 ) */
    int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = a[i];
        // 현재 정렬된 배열은 i - 1까지 이므로 i - 1번째부터 역순으로 조사합니다.
        for (j = i - 1; j >= 0 && a[j] > key; j--)
            a[j + 1] = a[j];
        a[j + 1] = key;
    }
}

int partition(int list[], int left, int right)
{
    int pivot;
    int low, high;

    low = left;
    high = right + 1;
    pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택 ( 임의의 값을 피벗으로 선택 )

    /* low와 high가 교차할 때까지 반복 (low < high) */
    do
    {
        /* list[low]가 피벗보다 작으면 계속 low를 증가 시켜줘야 한다. */
        do
        {
            low++;
        } while (list[low] < pivot && low <= right); // low가 만약에 right이 된다면 멈처 주어야 합니다.

        do
        {
            high--;
        } while (list[high] > pivot && high >= left);

        // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high]와 교환
        if (low < high)
            swap(list + low, list + high);
    } while (low < high);

    // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]을 교환해줘야 한다.
    swap(list + left, list + high);

    // 피벗의 위치인 high를 반환해주어야 합니다.
    return high;
}

void quick_sort(int list[], int left, int right)
{
    /* 정렬할 범위가 2개 이상의 데이터가렴( 리스트의 크기가 0이나 1이 아니라면) */
    if (left < right)
    {
        // partition함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 - 분할(Divide)
        int q = partition(list, left, right);
        // 피벗을 제외한 2개의 부분 리스트를 대상으로 순환 호출
        quick_sort(list, left, q - 1);  // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        quick_sort(list, q + 1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
    }
    else
    {
        return;
    }
}

void merge(int list[], int left, int mid, int right)
{
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    /* 분할 정렬된 list의 합병 */
    while (i <= mid && j <= right)
    {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }

    // 남아 있는 값들을 일괄 복사
    if (i > mid)
        for (l = j; j <= right; j++)
            sorted[k++] = list[j];
    else
        for (l = i; i <= mid; i++)
            sorted[k++] = list[l];

    for (l = left; l <= right; l++)
        list[l] = sorted[l];
}

void merge_sort(int list[], int left, int right)
{
    int mid;

    // 원소가 1개가 아닌 경우
    if (left < right)
    {
        mid = (left + right) / 2;         // 중간 위치를 계산하여 리스트를 균등 분할 - 분할(Divide)
        merge_sort(list, left, mid);      // 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        merge_sort(list, mid + 1, right); // 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
        merge(list, left, mid, right);    // 정렬된 2개의 부분 배열을 합병하는 과정 - 결합(Combine)
    }
    else
    {
        // 원소가 1개라면 그냥 return시켜 주면 된다.
        return;
    }
}

void bubble_sort(int list[], int n)
{
    int i, j, temp;

    for (i = 0; i < n; i++)
        for (j = 0; j < n - 1 - i; j++)
            if (list[j] > list[j + 1])
                swap(list + j, list + j + 1);
}

void printArr(int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    putchar('\n');
}

int main(void)
{
    int sortArr[ARR_SIZE] = {0};
    int count = 0;

    FILE *fp_read = fopen("sort.txt", "r");
    while ((fscanf(fp_read, "%d", sortArr + count) != EOF))
    {
        count++;
    }

    printf("original array: ");
    printArr(sortArr, count);

    // printf("[ 4 ] is in index %d\n", seqSearch(sortArr, 4, count));

    int sortArr_2[ARR_SIZE];
    memcpy(sortArr_2, sortArr, sizeof(int) * ARR_SIZE);
    printf("insertion sort:\t");
    insertionSort(sortArr_2, count);
    printArr(sortArr_2, count);

    int sortArr_3[ARR_SIZE];
    memcpy(sortArr_3, sortArr, sizeof(int) * ARR_SIZE);
    printf("quiuck sort:\t");
    quick_sort(sortArr_3, 0, count - 1);
    printArr(sortArr_3, count);

    int sortArr_4[ARR_SIZE];
    memcpy(sortArr_4, sortArr, sizeof(int) * ARR_SIZE);
    printf("merge sort:\t");
    merge_sort(sortArr_4, 0, count - 1);
    printArr(sortArr_4, count);

    int sortArr_5[ARR_SIZE];
    memcpy(sortArr_5, sortArr, sizeof(int) * ARR_SIZE);
    printf("heap sort:\t");
    heap_sort(sortArr_5, count);
    printArr(sortArr_5, count);

    int sortArr_6[ARR_SIZE];
    memcpy(sortArr_6, sortArr, sizeof(int) * ARR_SIZE);
    printf("bubble sort:\t");
    bubble_sort(sortArr_6, count);
    printArr(sortArr_6, count);

    return 0;
}

// original array: 3 2 4 1 9 8 
// insertion sort: 1 2 3 4 8 9 
// quiuck sort:    1 2 3 4 8 9 
// merge sort:     1 2 3 4 8 9 
// heap sort:      1 2 3 4 8 9 
// bubble sort:    1 2 3 4 8 9

• 버블 정렬 알고리즈의 특징은 매우 간단합니다.
• 장점
  • 구현이 매우 간단합니다.
• 단점
  • 순서에 맞지 않은 요소를 인접한 요소와 교환합니다.
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 합니다.
  • 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어납니다
• 일반적으로 자료의 교환작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰지 않습니다.

 

• 비교 횟수
  • 최상, 평균 최악 모두 일정
  • n - 1, n - 2, ... , 2, 1번 = n(n - 1)/2
• 교환 횟수
  • 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동이 필요하므로 3n(n - 1)/2
  • 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동은 발생하지 않습니다.
• T(n) = O(n^2)

---

선택 정렬

• 선택 정렬은 첫 번쨰 자료를 두 번쨰 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행합니다.
• 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교합니다. 마찬가지로 3회전에서는 세 번쨰 자료를 정렬합니다.

/selection_sort.c

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

#define ARR_SIZE 100

#define HEAP_FULL(n) (n == ARR_SIZE - 1)
#define HEAP_EMPTY(n) (!n)

int sorted[ARR_SIZE];

typedef struct
{
    int key;
} element;

element heap[ARR_SIZE];

void push(element item, int *n)
{
    int i;
    // 만약 힙이 꽉 차있다면
    if (HEAP_FULL(*n))
    {
        fprintf(stderr, "The heap is full. \n");
        exit(EXIT_FAILURE);
    }
    i = ++(*n);
    while ((i != 1) && (item.key > heap[i / 2].key))
    {
        heap[i] = heap[i / 2];
        i /= 2;
    }
    heap[i] = item;
}

element pop(int *n)
{
    int parent, child;
    element item, temp;
    if (HEAP_EMPTY(*n))
    {
        fprintf(stderr, "The heap is empty. \n");
        exit(EXIT_FAILURE);
    }
    item = heap[1];
    temp = heap[(*n)--];
    parent = 1;
    child = 2;
    while (child <= *n)
    {
        if ((child < *n) && (heap[child].key < heap[child + 1].key))
            child++;

        if (temp.key >= heap[child].key)
            break;

        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return item;
}

void heap_sort(int a[], int n)
{
    int count = 0, i;
    element newElement = {0};

    // 우선 int 배열의 값을 하나씩 heap에 집어 넣어주어야 한다.
    for (int i = 0; i < n; i++)
    {
        newElement.key = a[i];
        push(newElement, &count);
    }

    for (i = (n - 1); i >= 0; i--)
    {
        a[i] = pop(&count).key;
    }
}

int seqSearch(int a[], int k, int n)
{
    int i;
    for (i = 1; i < n && a[i] != k; i++)
        ;

    if (i >= n)
        return -1;
    return i;
}

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void insertionSort(int a[], int n)
{
    /* sort a[0:n - 1] into nondecreasing order( 오름 차순 ) */
    int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = a[i];
        // 현재 정렬된 배열은 i - 1까지 이므로 i - 1번째부터 역순으로 조사합니다.
        for (j = i - 1; j >= 0 && a[j] > key; j--)
            a[j + 1] = a[j];
        a[j + 1] = key;
    }
}

int partition(int list[], int left, int right)
{
    int pivot;
    int low, high;

    low = left;
    high = right + 1;
    pivot = list[left]; // 정렬할 리스트의 가장 왼쪽 데이터를 피벗으로 선택 ( 임의의 값을 피벗으로 선택 )

    /* low와 high가 교차할 때까지 반복 (low < high) */
    do
    {
        /* list[low]가 피벗보다 작으면 계속 low를 증가 시켜줘야 한다. */
        do
        {
            low++;
        } while (list[low] < pivot && low <= right); // low가 만약에 right이 된다면 멈처 주어야 합니다.

        do
        {
            high--;
        } while (list[high] > pivot && high >= left);

        // 만약 low와 high가 교차하지 않았으면 list[low]를 list[high]와 교환
        if (low < high)
            swap(list + low, list + high);
    } while (low < high);

    // low와 high가 교차했으면 반복문을 빠져나와 list[left]와 list[high]을 교환해줘야 한다.
    swap(list + left, list + high);

    // 피벗의 위치인 high를 반환해주어야 합니다.
    return high;
}

void quick_sort(int list[], int left, int right)
{
    /* 정렬할 범위가 2개 이상의 데이터가렴( 리스트의 크기가 0이나 1이 아니라면) */
    if (left < right)
    {
        // partition함수를 호출하여 피벗을 기준으로 리스트를 비균등 분할 - 분할(Divide)
        int q = partition(list, left, right);
        // 피벗을 제외한 2개의 부분 리스트를 대상으로 순환 호출
        quick_sort(list, left, q - 1);  // (left ~ 피벗 바로 앞) 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        quick_sort(list, q + 1, right); // (피벗 바로 뒤 ~ right) 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
    }
    else
    {
        return;
    }
}

void merge(int list[], int left, int mid, int right)
{
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    /* 분할 정렬된 list의 합병 */
    while (i <= mid && j <= right)
    {
        if (list[i] <= list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }

    // 남아 있는 값들을 일괄 복사
    if (i > mid)
        for (l = j; j <= right; j++)
            sorted[k++] = list[j];
    else
        for (l = i; i <= mid; i++)
            sorted[k++] = list[l];

    for (l = left; l <= right; l++)
        list[l] = sorted[l];
}

void merge_sort(int list[], int left, int right)
{
    int mid;

    // 원소가 1개가 아닌 경우
    if (left < right)
    {
        mid = (left + right) / 2;         // 중간 위치를 계산하여 리스트를 균등 분할 - 분할(Divide)
        merge_sort(list, left, mid);      // 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        merge_sort(list, mid + 1, right); // 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
        merge(list, left, mid, right);    // 정렬된 2개의 부분 배열을 합병하는 과정 - 결합(Combine)
    }
    else
    {
        // 원소가 1개라면 그냥 return시켜 주면 된다.
        return;
    }
}

void bubble_sort(int list[], int n)
{
    int i, j, temp;

    for (i = 0; i < n; i++)
        for (j = 0; j < n - 1 - i; j++)
            if (list[j] > list[j + 1])
                swap(list + j, list + j + 1);
}

void selection_sort(int list[], int n)
{
    int i, j, least;

    // 마지막 숫자는 자동으로 정렬되기 때문에 (개수 - 1)만큼 반복합니다.
    for (i = 0; i < n - 1; i++)
    {
        least = i;

        // 최솟값을 탐색합니다.
        for (j = i + 1; j < n; j++)
            if (list[j] < list[least])
                least = j;

        // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
        if (i != least)
            swap(list + least, list + i);
    }
}

void printArr(int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    putchar('\n');
}

int main(void)
{
    int sortArr[ARR_SIZE] = {0};
    int count = 0;

    FILE *fp_read = fopen("sort.txt", "r");
    while ((fscanf(fp_read, "%d", sortArr + count) != EOF))
    {
        count++;
    }

    printf("original array: ");
    printArr(sortArr, count);

    // printf("[ 4 ] is in index %d\n", seqSearch(sortArr, 4, count));

    int sortArr_2[ARR_SIZE];
    memcpy(sortArr_2, sortArr, sizeof(int) * ARR_SIZE);
    printf("insertion sort:\t");
    insertionSort(sortArr_2, count);
    printArr(sortArr_2, count);

    int sortArr_3[ARR_SIZE];
    memcpy(sortArr_3, sortArr, sizeof(int) * ARR_SIZE);
    printf("quiuck sort:\t");
    quick_sort(sortArr_3, 0, count - 1);
    printArr(sortArr_3, count);

    int sortArr_4[ARR_SIZE];
    memcpy(sortArr_4, sortArr, sizeof(int) * ARR_SIZE);
    printf("merge sort:\t");
    merge_sort(sortArr_4, 0, count - 1);
    printArr(sortArr_4, count);

    int sortArr_5[ARR_SIZE];
    memcpy(sortArr_5, sortArr, sizeof(int) * ARR_SIZE);
    printf("heap sort:\t");
    heap_sort(sortArr_5, count);
    printArr(sortArr_5, count);

    int sortArr_6[ARR_SIZE];
    memcpy(sortArr_6, sortArr, sizeof(int) * ARR_SIZE);
    printf("bubble sort:\t");
    bubble_sort(sortArr_6, count);
    printArr(sortArr_6, count);

    int sortArr_7[ARR_SIZE];
    memcpy(sortArr_7, sortArr, sizeof(int) * ARR_SIZE);
    printf("selection sort:\t");
    selection_sort(sortArr_7, count);
    printArr(sortArr_7, count);

    return 0;
}

// original array: 3 2 4 1 9 8 
// insertion sort: 1 2 3 4 8 9 
// quiuck sort:    1 2 3 4 8 9 
// merge sort:     1 2 3 4 8 9 
// heap sort:      1 2 3 4 8 9 
// bubble sort:    1 2 3 4 8 9 
// selection sort: 1 2 3 4 8 9

• 선택 정렬의 특징에 대해 살펴보겠습니다.
• 장점
  • 자료의 이동 횟수가 미리 결정됩니다.
• 단점
  • 안정성을 만족하지 않습니다.
  • 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있습니다.

 

• 비교횟수
  • 두 개의 for루프의 실행 횟수
  • 외부 루프: (n - 1)번
  • 내부 루프(최솟값 찾지): n - 1, n - 2, ... , 2, 1번
• 교환 횟수
  • 외부 루프의 실행 횟수와 동일, 즉 상수 시간 작업
  • 한 번 교환하기 위하여 3번의 이동(SWAP)이 필요하므로 3(n - 1)번
• T(n) = n(n - 1)/2