[자료구조 - C언어] 정렬(Sort) - Bubble, Insertion, Selection

Bubble Sort (버블 정렬)

-> 서로 인접한 두 값을 비교하여 정렬하는 알고리즘

오름차순으로 정렬할 때, 두 값을 비교하여 더 작은 값을 앞에 위치시킨다.

1회전 정렬을 끝내면 가장 큰 값이 가장 마지막에 위치하게 된다.

2회전, 3회전 반복될수록 그다음으로 큰 값의 위치가 정해진다. 

 

Ex) 8, 1, 6, 3, 2 정렬하기

#include <stdio.h>
#include <stdlib.h>
#define ASIZE 5

void bubble_print(int* array, int size) {
    for (int n = 0; n < size; n++) {
        printf("%d ", array[n]);
    }
    printf("\n");
}

int main(int argc, char* argv[]) {

    int array[ASIZE] = { 8, 1, 6, 3, 2};
    int temp, swapped, swap_cnt;

    printf("=============================\n");
    printf("start array : ");

    bubble_print(array, ASIZE);
    printf("=============================\n");

    swap_cnt = 0;
    swapped = 1;

    while (swapped == 1) {
        swapped = 0;
        for (int n = 0; n < ASIZE -1; n++) {
            printf("compare : %d, %d\n", array[n], array[n + 1]);

            if (array[n] > array[n + 1]) {
                temp = array[n];
                array[n] = array[n + 1];
                array[n + 1] = temp;

                swapped = 1;
                swap_cnt++;
            }
            printf("compare end: %d, %d\n", array[n], array[n + 1]);
        }

        if (swapped == 0) {
            printf("=============================\n");
            printf("end array : ");
            bubble_print(array, ASIZE);
            printf("=============================\n");
            break;
        }
        printf("=============================\n");
        printf("sorting array : ");
        bubble_print(array, ASIZE);
        printf("=============================\n");
    }
    printf("swap : %d\n", swap_cnt);

    return 0;
}

 

* 코드 설명

1. while문을 사용하여 swap과정을 반복
2. 정렬이 끝나지 않았을 경우 for문에서 swap과정이 계속 일어나고 swapped가 1로 설정됨
3. 정렬이 끝났을 경우 swapped는 0으로 유지되기에 while문 탈출
4. swap_cnt 변수를 통해 swap과정이 몇 번 일어났는지 확인

 

<콘솔창>

버블 정렬

버블 정렬

 

정렬이 끝나고 while문이 탈출 조건을 작성할 때, 'swapped=0'을 어디에 넣어야 할지 한참 헤매다가 겨우 탈출했네요...

while문 시작 부분에 적을 생각을 못하고 계속 for문 밑에 적고 있으니 정렬이 완성될 리가 없겠죠....ㅠㅠ

 

 

Insertion Sort (삽입 정렬)

-> 배열의 앞에서부터 순서대로 값을 비교하여, 자신의 위치를 찾아 값을 넣어 정렬하는 알고리즘

오름차순으로 정렬할 때, 자신의 값보다 큰 값이 앞에 위치할 경우 그 값보다 앞에 자신의 값을 삽입하여 정렬한다.

Bubble Sort와는 반대로 가장 작은 값부터 자신의 위치를 정하게 된다. 

 

Ex) 6, 5, 3, 1, 8, 7, 2, 4 정렬하기 

#include <stdio.h>
#define SIZE 8

void print_array(int* array, int size) {

    for (int n = 0; n < SIZE; n++) {
        printf("%d ", array[n]);
    }
    printf("\n");
}

int main(int argc, char* argv[]) {

    int array[SIZE] = { 6, 5, 3, 1, 8, 7, 2, 4 };
    int temp;

    printf("Start\n");
    printf("=============================\n");
    print_array(array, 8);
    printf("=============================\n");

    for (int current_target = 1; current_target < SIZE; current_target++) {

        int ins_target = current_target - 1;
        temp = array[current_target];

        if (array[ins_target] <= temp)
            continue;

        while (array[current_target] < array[ins_target]) {
            ins_target--;
        }
        ins_target++;

        for (int n = current_target; n > ins_target; n--) {
            array[n] = array[n - 1];
        }
        array[ins_target] = temp;

        printf("current : %d, ins : %d\n", array[current_target], array[ins_target]);

        printf("=============================\n");
        print_array(array, 8);
        printf("=============================\n");
    }
    printf("End\n");
    return 0;
}

 

*코드 설명

1. 배열의 인덱스 1을 반복문의 기준(시작)으로 선언 (기준 = current_target)
2. 기준이 되는 인덱스 값과 그 앞의 값을 비교하여 가장 작은 값을 배열의 앞에 위치 시킴 (삽입할 위치 = ins_target)
3. 기준이 되는 값이 그 앞의 값보다 클 경우 오름차순 정렬 조건을 만족하기에 continue를 사용하여 다음 수행문을 실행하지 않음 (line 27, 28)

 

<콘솔창>

삽입 정렬

 

 

Selection Sort (선택 정렬)

-> 배열의 첫 번째 값을 나머지 값과 차례대로 비교하여 정렬하는 알고리즘

오름차순으로 정렬할 때, 첫 번째 값을 나머지 값과 비교하여 가장 작은 값을 첫 번째 자리에 위치시키고, 

그다음 값도 나머지 값과 비교하여 작은 값이 앞쪽으로 정렬된다. 

 

Ex) 6, 5, 3, 1, 8, 7, 2, 4 정렬하기

#include <stdio.h>
#define SIZE 8

void print_array(int* arr, int size) {

    for (int n = 0; n < size; n++) {
        printf("%d ", arr[n]);
    }
    printf("\n");
}

int fine_min(int* arr, int start, int size) {

    int min = start;

    for (int n = start; n < size; n++) {
        if (arr[min] > arr[n])
            min = n;
    }
    return min;
}

int main(int argc, char* argv[]) {

    int arr[SIZE] = { 6, 5, 3, 1, 8, 7, 2, 4 };
    int index, min_found, temp;

    print_array(arr, SIZE);

    for (index = 0; index < SIZE; index++) {
        min_found = fine_min(arr, index, SIZE);

        temp = arr[index];
        arr[index] = arr[min_found];
        arr[min_found] = temp;

        printf("Min : %d\n", arr[index]);
        print_array(arr, SIZE);
    }
    return 0;
}

 

 

* 코드 설명

1. fine_min 함수를 선언하여 최솟값을 가지는 인덱스를 찾음
2. 찾은 최솟값(arr [min_found])을 현재 배열 자리(arr [index])에 대입함 

 

<콘솔창>

선택 정렬

 

 

감사합니다!