[2주차 TIL] KnockOn Bootcamp Pre.Rev : 정렬 알고리즘

정렬 알고리즘

버블 정렬

1. 배열의 처음부터 시작하여 인접한 두 요소를 비교
2. 두 요소가 정렬이 안되어 있다면, 서로 교환
3. 배열의 끝까지 한번 비교와 교환과정을 수행하면 가장 큰 값이 배열의 끝에 위치
4. 이 과정을 배열의 크기만큼 반복하여 정렬을 완성

선택정렬

1. 배열의 첫번째 요소를 기준으로 나머지 요소들과 비교하여 가장 작은 값을 찾음
2. 가장 값이 작은 것과 첫번째 요소를 교환
3. 첫번째 요소를 제외한 나머지 배열에 대해 위 과정을 반복
4. 정렬이 완료될 때까지 이를 반복

삽입정렬

1. 배열에서 두번째 요소부터 시작하여, 현재 요소를 기준으로 앞쪽에 있는 정렬된 부분과 비교
2. 현재 요소가 정렬된 부분의 요소들보다 작다면, 알맞은 위치에 삽입
3. 이 과정을 배열의 끝까지 반복하여 정렬을 완성

정리

구분	설명	장점
버블정렬	최악 : O(n^2) 최선 : O(n)	구현이 간단, 직관적
선택정렬	최악, 최선, 평균O(n^2)	교환 횟수가 적음
삽입정렬	최악 : O(n^2) 최선 : O(n)	정렬된 데이터에 빠름. 적은 데이터에 적합

실습

이번 실습 간에는 정렬 알고리즘을 구현할 것이다.

버블 정렬

// Bubble Sort
#include <stdio.h>
#include <stdlib.h>

int main() {
    int arr[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
    int temp;

    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }


    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

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


    return 0;
}

선택정렬

// select Sort
#include <stdio.h>
#include <stdlib.h>

int main() {
    int arr[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
    int idx = 0;
    int temp = 0;

    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }


    for (int i = 0; i < 10; i++) {
        int tmp = arr[i]; 

        for (int j = i+1; j < 10; j++) {
            if (tmp > arr[j]) {
                idx = j;
                tmp = arr[j];
            }
        }
        if (tmp == arr[i]) {
            continue;
        }
        temp = arr[idx];
        arr[idx] = arr[i];
        arr[i] = temp;

    }

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


    return 0;
}

삽입정렬

// insert Sort
#include <stdio.h>
#include <stdlib.h>

int main() {
    int arr[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
    int temp;
    int idx = 0;

    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }

    for (int i = 1; i <= 9; i++) {
        for (idx = 0; idx <= i; idx++) {
            if (arr[i] < arr[idx]) {
                temp = arr[idx];
                arr[idx] = arr[i];
                arr[i] = temp;
            }
        }
    }

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


    return 0;
}

끝.