1. 문제

---

출처: 백준 2750번 수 정렬하기

2. 풀이

---

시간 복잡도가 $O(n^2)$ 정렬 알고리즘을 활용해 보라고 문제에 설명이 되어있다.

예시로 나와 있는 삽입 정렬과 거품 정렬을 활용해 보았다.

삽입 정렬 (Insertion Sort)

삽입 정렬은 주어진 숫자 리스트를 처음부터 끝까지 훑으면서 숫자 하나씩을 뽑아 정렬해 나가는 알고리즘이다.

숫자를 하나씩 뽑고, 그 숫자를 앞에 있는 숫자들(이미 정렬되어 있는)과 비교하여 적절한 위치에 삽입하는 형태로 정렬을 진행한다.

숫자를 쭉 훑는데 $n$, 그리고 앞의 숫자들과 비교하는데 $n$이 필요하기 때문에 시간 복잡도는 $O(n^2)$이 된다.

거품 정렬 (Bubble Sort)

거품 정렬은 앞뒤 숫자를 비교해나가면서 정렬을 하는 알고리즘이다.

처음부터 끝까지 한 번 하고 나면, 가장 큰 수가 리스트의 끝에 위치하게 된다.

모든 숫자를 오름차순으로 정리하기 위해서는 가장 작은 수가 제일 앞에 위치할 때까지, 이것을 계속해서 반복하면 된다.

큰 수가 가장 끝에 위치하게 만드는데 $n$, 모든 수가 정렬될 때까지 $n$을 반복하기 때문에 시간 복잡도는 $O(n^2)$이 된다.

3. 소스코드

---

삽입 정렬 (Insertion Sort)

case = int(input())
numbers = [int(input()) for _ in range(case)]

for i in range(len(numbers)):
    for j in range(i):
        if numbers[i] < numbers[j]:
            temp = numbers[j:]
            temp.remove(numbers[i])
            numbers = numbers[:j] + [numbers[i]] + temp
            break
print(*numbers, sep="\n")

거품 정렬 (Bubble Sort)

case = int(input())
numbers = [int(input()) for _ in range(case)]

for i in range(len(numbers)-1):
    for j in range(len(numbers)-i-1):
        if numbers[j] > numbers[j+1]:
            numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
print(*numbers, sep="\n")

4. 그 외

---

10단계는 다양한 정렬을 공부해볼 수 있는 단계이다.

일반적으로 코딩할 때에는 내장된 함수를 사용하고 말지만, 정렬을 어떻게 해볼 수 있을까 고민해볼 수 있는 시간들이다.

대학교 1학년 때 들었던, 컴퓨터 관련 수업에서 여러가지 정렬을 배웠던 기억이 새록새록 떠올랐다.