백준 2751번: 수 정렬하기 2

2751번: 수 정렬하기 2

기존에 사용했던 버블정렬 코드 (2750번)
#include <stdio.h>
#include <stdlib.h>

void compare(int * a, int * b)
{
    int tmp;
    if (*a > *b)
    {
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

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

int main(void)
{
    int N, i, j, isSorted;

    scanf("%d", &N);

    int * nums = malloc(N*sizeof(int));
    for (i=0; i<N; i++)
        scanf("%d", &nums[i]);

    for (i=0; i<N; i++)
    {
        isSorted = 1;
        for (j=0; j<N-1; j++)
        {
            if (nums[j] > nums[j+1])
            {
                isSorted = 0;
                compare(&nums[j], &nums[j+1]);
            }
        }
        if (isSorted)
            break;
    }

    printArray(nums, N);

    return 0;
}
종만북 조금 읽다가 본 재귀함수 사용해서 풀어봄 (시간초과)
#include <stdio.h>
#include <stdlib.h>

void compare(int * a, int * b)
{
    int tmp;
    if (*a > *b)
    {
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

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

void mySort(int arr[], int start_index, int len)
{
    int f, isSorted;

    if (len > 10)
    {
        mySort(arr, 0, (len/2)-1);
        mySort(arr, (len/2), len);
    }

    for (f=start_index; f<len-1; f++)
    {
        if (arr[f] > arr[f+1])
        {
            isSorted = 0;
            compare(&arr[f], &arr[f+1]);
        }
    }

    if (isSorted)
        return;
    else
        mySort(arr, start_index, len);
}

int main(void)
{
    int N, i, j, isSorted;

    scanf("%d", &N);

    int * nums = malloc(N*sizeof(int));
    for (i=0; i<N; i++)
        scanf("%d", &nums[i]);

    for (i=0; i<N; i++)
    {
        isSorted = 1;
        mySort(nums, 0, N);
        if (isSorted)
            break;
    }

    printArray(nums, N);

    return 0;
}

위키에서 정렬 알고리즘들 읽어보고 있는데
그림으로는 이해하겠는데 원리는 모르겠는…
아무튼 오늘은 퀵정렬 도전해봅니다
물론 코드복붙은 자존심 상하니깐 안할꺼고

대략적으로 이해한 거는

  1. 배열에서 pivot 값을 하나 잡는다
  2. pivot 값을 기준으로 작은 값들과 큰 값들로 나눈다
  3. 값들이 모여있는 각 부분마다 1, 2를 반복한다

아까처럼 재귀함수 잘 쓰면 될 것 같은데
암튼 어렵네요

1 Like

다짜셨네여 ㅎㅎ

1 Like

백준의 부족한 예제 입력으로 인해 직접 만든 예제:
(백준은 각 줄마다 숫자가 입력되어 있긴 한데
그냥 귀찮아서 둘째 줄에 공백 구분으로 넣었습니다)

예제 1

입력

7
3 4 1 5 2 0 7

출력

0 1 2 3 4 5 7
예제 2(아직 해결 X)

입력

30
900 451 378 980 814 833 -990 510 -95 -350 900 969 455 548 87 -240 384 -714 857 193 917 888 -849 528 32 342 -535 380 124 -804

출력

아직...
예제 3(아직 해결 X)

입력
myfile.txt (72.2 KB) (N = 10000)
출력
아직...

모루겟소요 (= 해결X)
#include <stdio.h>
#include <stdlib.h>

void changeNum(int * a, int * b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void printArray(int arr[], int len)
{
    for (int f=0; f<len; f++)
        printf("%d ", arr[f]);
}

void mySort(int arr[], int start_index, int len)
{
    int f, isSorted = 1;

    if ((len-start_index) > 6)
    {
        mySort(arr, 0, (len/2)-1);
        mySort(arr, (len/2), len);
    }

    for (f=start_index; f<len-1; f++)
    {
        if (arr[f] > arr[f+1])
        {
            changeNum(&arr[f], &arr[f+1]);
            isSorted == 0;
        }
    }

    if (isSorted == 0)
        mySort(arr, start_index, len);
}

int main(void)
{
    int N, i;

    scanf("%d", &N);

    int * nums = malloc(N*sizeof(int));
    for (i=0; i<N; i++)
        scanf("%d", &nums[i]);

    mySort(nums, 0, N);

    printArray(nums, N);

    return 0;
}

기껏 바꾼다는 부분도
mySort 함수에서

    if ((len-start_index) > 6)

이부분만 깨작거리고 있는데
이상하게 8 아래로 내려가면 잘 안되더라고요

15
8 9 1 2 10 0 3 6 5 4 9 7 12 15 13

이거 같은 예제도 8이나 10 등으로 하면 잘 되던데
그 이하로 구간을 줄여버리면 잘 작동하지 않네요…
그렇다고 8 이상으로 계속 두자니
재귀를 사용한 버블 정렬이 되는 느낌이라…
:thinking:

이따 저녁에 마저 해봐야겠네유

Haskell

import Data.List ( sort )

main :: IO ()
main = getContents >>= mapM_ print . sort . map parse . tail . lines
    where
        parse = read :: String -> Int