수 정렬하기_2750

박상민·2023년 10월 10일

브론즈 정렬

백준

목록 보기

11/36

문제

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

입력

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

출력

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

예제 입력 1

예제 출력 1

문제접근

N개의 수를 오름차순으로 정렬하기 위해선 숫자의 크기를 비교할 수 있어야 한다.
숫자의 크기를 비교하기 전에 입력값을 저장할 배열을 만든 후 배열 속에서 for문을 돌려 숫자끼리의 대소를 비교해 숫자의 위치를 갱신해주면 되는 간단한 문제이다.

이 문제를 풀 수 있는 방법은 크게 두가지로 나뉘어 보았다.

가장 먼저 쉽게풀 수 있는 방법은 python의 sorted 내장함수를 이용하면 된다.

1) sorted 내장 함수

x = int(input())
num_list = [int(input()) for _ in range(x)]
sorted_list = sorted(num_list)
for num in sorted_list:
    print(num)

sorted를 이용하지 않고 푸는 방법은 직접 정렬하는 알고리즘을 구현하는 것이다.
여러 정렬 알고리즘이 있지만 비교적 구현이 간단한 버블정렬을 이용해 풀어보도록 하겠다.

버블정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘으로
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 방식으로 동작한다.

2) 버블정렬

#버블정렬 구현
def bubble_sort(N):
    for i in range(len(N)):
        for j in range(0, len(N) - i - 1):
            if N[j] > N[j + 1]:
                N[j], N[j + 1] = N[j + 1], N[j]
#입력
x = int(input())
num_list = [int(input()) for _ in range(x)]

bubble_sort(num_list)

#출력
for num in num_list:
    print(num)

구현이 단순하기 때문에 작성을 해보았다.
하지만 버블정렬은 시간복잡도가 O(n^2)으로 높은 편에 속한다.

비교 횟수

최상, 평균, 최악 모두 일정

n-1, n-2, … , 2, 1 번 = n(n-1)/2

교환 횟수

입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2

입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
T(n) = O(n^2)