200809_TIL

부스트 코딩뉴비챌린지

• 5주차 미션 1, 3번 완료! 저번주 미션 난이도에 비해 이번주는 쉬운 느낌이다.
• 파일 읽기, 쓰기와 관련된 내용은 스스로 복습해봐야겠다.
• 저번주 알고리즘 강의에서 배운 버블 정렬, 선택 정렬, 병합 정렬을 코드로 구현해 보는 연습도 해보았다. 코드는 아래에 기록해 둔다.
• 병합 정렬에서 재귀를 이용하는 게 처음에 이해가 약간 어려웠다. 공부 열심히 하면 나중엔 이런 문제는 고민도 안 하고 척척 풀 수 있게 될까..?
  
  
  

다양한 정렬 알고리즘 구현하기

버블 정렬

#include <stdio.h>

void bubblesort(int n, int* arr);

int main()
{
    int n = 7; // 배열의 크기
    int arr[7] = { 0, 25, 10, 17, 6, 12, 9 };
    bubblesort(n, arr); // 버블 정렬을 해줄 사용자 함수 호출
    return 0;
}

void bubblesort(int n, int* arr) {
    int tmp;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (*(arr + j) > *(arr + j + 1)) {
                tmp = *(arr + j);
                *(arr + j) = *(arr + j + 1);
                *(arr + j + 1) = tmp;
            } // 배열의 j번째 요소가 j+1번째 요소보다 크면
              // 포인터로 배열 요소에 접근하여 두 값의 자리를 바꿈
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", *(arr + i));
    } // 정렬 후 배열을 출력
    printf("\n");
}

선택 정렬

• main 함수 부분이 버블 정렬과 같아서 사용자 정의 함수 부분만 기록해 둔다.

void selectsort(int n, int* arr) {
    int tmp, least;

    for (int i = 0; i < n - 1; i++) {
        least = i;
        for (int j = i+1; j < n; j++) {
            if (*(arr + least) > *(arr + j)) {
                least = j; 
                // 최솟값을 탐색하고 index를 least라는 변수에 저장
            }
        }
        tmp = arr[least];
        arr[least] = arr[i];
        arr[i] = tmp;
        // 최솟값과 i번째 요소의 위치를 바꿈
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", *(arr + i));
    } // 정렬 후 배열을 출력
    printf("\n");
}

병합 정렬 (혹은 합병 정렬)

• 링크텍스트 를 참고하였다.

#include <stdio.h>

void mergesort(int p, int n, int* arr);
void merge(int p, int q, int n, int* arr);

int main()
{
    int n = 7; // 배열의 크기
    int arr[7] = { 0, 25, 10, 17, 6, 12, 9 };
    mergesort(0, n - 1, arr); // 배열을 정렬해줄 사용자 함수 호출
    
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    } // 정렬된 배열 출력
    printf("\n");
    return 0;
}
void mergesort(int p, int r, int* arr) {
    int q = p < r ? (p + r) / 2 : 0;
    // 중간 위치를 계산하여 배열을 분할
    if (q != 0) {
        mergesort(p, q, arr); // 배열의 앞쪽 부분을 정렬-정복
        mergesort(q + 1, r, arr); // 배열의 뒷쪽 부분을 정렬-정복
        merge(p, q, r, arr); // 정렬된 2개의 부분 배열을 병합
    }
}
void merge(int p, int q, int r, int* arr) {
    int* tmp = malloc(sizeof(int) * (r + 1));
    // 원 배열의 크기와 같은 새로운 배열
    int i = p, j = q + 1, k = p;
    // i: 정렬된 앞쪽 부분 배열에 대한 인덱스
    // j: 정렬된 뒷쪽 부분 배열에 대한 인덱스
    // k: 새롭게 정렬될 배열에 대한 인덱스

    while (i <= q && j <= r) {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    } // 분할 정렬된 배열의 합병

    while (i <= q)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];
    // 남아 있는 값들이 있다면 일괄 복사

    for (int a = p; a <= r; a++)
        arr[a] = tmp[a];
    // 임시 배열 tmp를 원 배열 arr로 재복사
    free(tmp); // 동적 할당된 메모리 해제
}