코드업(codeup) 3004 : 데이터 재정렬 C언어

▶문제 : 데이터 재정렬 (codeup.kr)

데이터 재정렬

 

▶코드 작성

#include <stdio.h>
#include <stdlib.h>

void quicksort(int* arr, int left, int right)//퀵정렬
{
    int L = left, R = right;
    int temp;
    int pivot = arr[(L + R) / 2];

    while (L <= R)
    {
        while (arr[L] < pivot) L++;
        while (arr[R] > pivot) R--;
        if (L <= R)
        {
            if (L != R)
            {
                temp = arr[L];
                arr[L] = arr[R];
                arr[R] = temp;
            }
            L++;
            R--;
        }
    }
    if (left < R) quicksort(arr, left, R);
    if (right > L) quicksort(arr, L, right);
}

void printNum(int* arr, int L, int R, int* num)
{
    int m = (L + R) / 2;
    if (L <= R)
    {
        if (*num > arr[m]) printNum(arr, m + 1, R, num);//오름차순배열 중앙값보다 클때
        else if (*num < arr[m]) printNum(arr, L, m - 1, num);//오름차순배열 중앙값보다 작을때
        else *num = m;//중앙값과 num( temp[i] )이 같을때
        //오름차순 arr배열의 자리 num( <- temp[i] ) 에 저장
    }
}

int main()
{
    int* data, * temp;
    int n, i, m;

    scanf("%d", &n);

    data = (int*)malloc(sizeof(int) * n);
    temp = (int*)malloc(sizeof(int) * n);

    for (i = 0; i < n; i++)
    {
        scanf("%d", &m);
        data[i] = m;
        temp[i] = m;
    }

    quicksort(data, 0, n - 1);//퀵정렬

    for (i = 0; i < n; i++)
    {
        printNum(data, 0, n - 1, &temp[i]);//temp[i]의 자리를 오름차순배열 data에서 찾아 temp[i]에 대입
        printf("%d ", temp[i]);
    }

    free(data);
    free(temp);

    return 0;
}

 

▶해석

 

두 개의 배열(data, temp)에 같은 값을 저장하고 퀵 정렬을 하여 한 배열(data)을 오름차순으로 정렬하고 나머지 배열(temp)을 이용하여 data배열에서의 자리를 찾아 temp [i]에 대입하여 출력