[Baekjoon/백준]단계별로 풀어보기 12단계: 정렬-1번,2번(C/C++)

백준 단계별로 풀어보기 12단계: 정렬

이번 문제는 학교 과제로 이미 풀었던 문제였다. 2750번은 선택 정렬, 2751번은 합병 정렬을 활용해서 문제를 해결했었다.

https://www.acmicpc.net/step/9

정렬 단계

---

(1) 백준 2750번: 수 정렬하기

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

• 문제설명

   -N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

• 입력과 출력

   -입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

   -출력: 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

• 코드

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )

void selection_sort(int list[], int N) {
    int least, temp;
    for (int i = 0; i < N - 1; i++) {
        least = i;
        for (int j = i + 1; j < N; j++)
            if (list[j] < list[least])
                least = j;
        SWAP(list[i], list[least], temp);
    }
}

int main(int argc, char *argv[]) {
    int list[MAX];
    int N = 0, M = 0;
    
    scanf("%d", &N);
    
    for (int i = 0; i < N; i++) {
        scanf("%d", &M);
        list[i] = M;
    }
    
    selection_sort(list, N);
    for (int i = 0; i < N; i++)
        printf("%d\n", list[i]);
    
    return 0;
}

• 결과

백준 제출 결과

---

(2) 백준 2751번: 수 정렬하기 2

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

• 문제설명

   -N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

• 입력과 출력

   -입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

   -출력: 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

• 코드

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

int *sorted;

void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left; j = mid + 1; k = left;

	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}

	if (i > mid)
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];

	for (l = left; l <= right; l++)
		list[l] = sorted[l];
}

void merge_sort(int list[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
}

int main(int argc, char * argv[]) {
	int N;

	scanf("%d", &N);
	int *list = (int *)malloc(sizeof(int) * N);
	sorted = (int *)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++)
		scanf("%d", &list[i]);

	merge_sort(list, 0, N-1);

	for (int i = 0; i < N; i++)
		printf("%d\n", list[i]);

	free(list);
	free(sorted);
	return 0;
}

• 결과

백준 제출 결과