정렬 알고리즘

 

삽입정렬 

배열의 요소들을 순차적으로 확인하여 그 보다 앞에 있는 요소들과 비교해서 알맞은 위치에 삽입해서 배열을 정렬한다.

작은 데이터셋이나 거의 정렬된 데이터셋에 활용한다. 

 

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[6] = {55, 31, 28, 9, 1, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    printf("after: \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

i	key	j	values
1	31	0	{31, 55, 28, 9, 1, 10}
2	28	1	{28, 31, 55, 9, 1, 10}
3	9	2	{9, 28, 31, 55 1, 10}
4	1	3	{1, 9, 28, 31, 55, 10}
5	10	4	{1, 9, 10, 28, 31, 55}

 

 

선택정렬 

주어진 배열에서 최소값(최대값)을 찾아서 현재 인덱스와 교환하는 방식 

처음부터 끝까지 반복을 하면서 한바퀴에 한번 씩 최소값을 찾아서 교환 

#include <stdio.h>

// 선택정렬 함수
void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // 배열의 각 요소를 순차적으로 정렬
    for (i = 0; i < n-1; i++) {
        // 남아있는 부분 배열에서 최소값을 찾음
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // 최소값을 현재 위치와 교환
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;

        // 현재 배열 상태 출력
        printf("Iteration %d: ", i+1);
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}

int main() {
    // 초기 배열 선언 및 초기화
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 정렬 전 배열 상태 출력
    printf("최초 배열: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    // 선택정렬 함수 호출
    selectionSort(arr, n);

    // 정렬 후 배열 상태 출력
    printf("\n정렬 이후: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

 

i / arr[i]	j	min_idx / arr[min_idx]	values
0 / 64	1~4	4 / 11	{11, 25, 12, 22, 64 }
1 / 25	1~4	2 / 12	{11, 12, 25, 22, 64 }
2 / 12	1~4	3 / 22	{11, 12, 22, 25 , 64 }
3 / 22	1~4	1 / 25	{11, 12, 22, 25 , 64 }

 

버블정렬 

주어진 배열에서  인접한 두 값을 비교해 교환하는 방식   

 

#include <stdio.h>

// 버블정렬 함수
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++) {
        // 마지막 i개의 요소는 이미 정렬된 상태
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 인접한 두 요소를 교환
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }

        // 현재 배열 상태 출력
        printf("반복 %d회차: ", i+1);
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}

int main() {
    // 초기 배열 선언 및 초기화
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 정렬 전 배열 상태 출력
    printf("초기 배열 상태: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    // 버블정렬 함수 호출
    bubbleSort(arr, n);

    // 정렬 후 배열 상태 출력
    printf("\n정렬된 배열 상태: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

i (0 ~ 4)	j (0 ~ 4-i-j-1까지)	arr[j]  / arr[j+1]	values
0	0	64 / 25	{25, 64, 12, 22, 11}
	1	64 / 12	{25, 12, 64, 22, 11}
	2	64 / 22	{25, 12, 22, 64, 11}
	3	64  / 11	{25, 12, 22, 11, 64}
1	0	25 / 12	{12, 25, 22, 11, 64}
	1	25 / 22	{12, 22, 25, 11, 64}
	2	25 / 11	{12, 22, 11, 25, 64}
	3	25 / 64	{12, 22, 11, 25, 64}
2	0	12 / 22	{12, 22, 11, 25, 64}
	1	22 / 11	{12, 11, 22, 25, 64}
	2	22 / 25	{12, 11, 22, 25, 64}
	3	25 / 64	{12, 11, 22, 25, 64}
3	0	12 / 11	{11, 12, 22, 25, 64}
	1	12 / 22	{11, 12, 22, 25, 64}
	2	22 / 25	{11, 12, 22, 25, 64}
	3	25 / 64	{11, 12, 22, 25, 64}

 

 

합병정렬 (Merge sort)

 

비교 기반의 정렬 알고리즘으로, 배열을 반으로 나누고 재귀적으로 정렬

그 다음 2개의 정렬된 부분 배열을 병합하는 식으로 전체 배열을 정렬한다.

각각 분할하고 그 부분을 정복한다고 해서 분할 정복(divide and conquer) 방법론이라고도 함

 

#include <stdio.h>

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0, k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m); //첫번째 mergeSort메서드라 명명
        mergeSort(arr, m + 1, r); //두번째 mergeSort메서드라 명명
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[6] = {55, 31, 28, 9, 1, 10};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, arr_size - 1);

    printf("정렬 후: \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

 

l < r == true
0번 메서드 = l : 0 /r : 5 / m : 2
l < r == true
1번 메서드 = l : 0 /r : 2 / m : 1
l < r == true
1번 메서드 = l : 0 /r : 1 / m : 0
l < r == false
l < r == false

merge메서드 전 = l : 0 /r : 1 / m : 0
merge메서드 후: 31 55 28 9 1 10 

l < r == false

merge메서드 전 = l : 0 /r : 2 / m : 1
merge메서드 후: 28 31 55 9 1 10 

l < r == true
2번 메서드 = l : 3 /r : 5 / m : 4
l < r == true
1번 메서드 = l : 3 /r : 4 / m : 3

l < r == false
l < r == false

merge메서드 전 = l : 3 /r : 4 / m : 3
merge메서드 후: 28 31 55 1 9 10 

l < r == false

merge메서드 전 = l : 3 /r : 5 / m : 4
merge메서드 후: 28 31 55 1 9 10 

merge메서드 전 = l : 0 /r : 5 / m : 2
merge메서드 후: 1 9 10 28 31 55 

정렬 후: 1 9 10 28 31 55

 

https://rosweet-ai.tistory.com/52