[Do-it! 코딩 테스트-기초편] 015. 수 정렬하기 1

문제

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

2750번: 수 정렬하기

---

접근

데이터 크기: 1,000

시간 제한: 1초

 

나열된 수를 정렬하는 방법은 여러가지가 있다.

가장 직관적이고 쉬운 방법인 버블정렬은 O(N^2)의 시간 복잡도를 갖는다.

문제의 데이터의 크기가 1,000이기 때문에 버블정렬을 사용해도 충분하다.

그리고 파이썬 list에 내장된 메서드 sort()와 비교해보도록 한다.

 

---

코드

버블정렬

N = int(input())
li = [0] * N
temp = 0
for i in range(N):
    li[i] = int(input())

for j in range(N):
    for i in range(1, N - j):
        if li[i] <= li[i - 1]:
            temp = li[i]
            li[i] = li[i - 1]
            li[i - 1] = temp

for i in range(N):
    print(li[i])

sort()

N = int(input())
number = [0]*N
for i in range(N):
    number[i] = int(input())
number.sort()

for i in range(N):
    print(number[i])

---

설명

버블정렬은 인접한 두 요소를 비교하고 swap하는 동작을 반복하여 정렬을 하는 알고리즘이다.

반복문을 중첩하여 사용해야하기 때문에 평균 O(N^2)의 시간 복잡도를 가진다. 시간에 제약이 없다면 쉽게 구현이 가능한 버블정렬을 사용하는 것이 좋다.

 

만약 [4, 2, 5, 7, 1] 인 리스트가 있고 오름차순을 한다고 하자. 맨 처음엔 0번 인덱스와 1번 인덱스를 비교한다. 4 > 2 이기 때문에 swap을 해야한다. 두 값의 위치를 바꾸는 방법중 하나로 temp 변수를 사용하였다. 

 

현재 리스트는 [2, 4, 5, 7, 1] 이다. 다음 루프에서 1번 인덱스와 2번 인덱스를 비교한다. 4 < 5 이기 때문에 swap없이 진행한다.

[2, 4, 5, 7, 1] 2번 인덱스와 3번 인덱스를 비교한다. 5 < 7 이므로 swap 없이 진행한다.

[2, 4, 5, 7, 1] 3번 인덱스와 4번 인덱스를 비교한다. 7 > 1 이므로 swap을 진행한다. 리스트를 한 번 완주하였다. 

현재 리스트는 [2, 4, 5, 1, 7] 이고 한 번의 완주는 무조건 맨 마지막 인덱스에 가장 큰 값을 위치시킨다.

 

그 다음 루프는 정렬이 완료된 마지막 인덱스를 제외하고 진행한다.

[2, 4, 1, 5, 7] -> [2, 1, 4, 5, 7] -> [1, 2, 4, 5, 7] 정렬 끝

 

다음으로 sort() 메서드의 사용이다.

파이썬은 내장함수로 sort(), sorted() reverse() 등을 지원한다.

sort()는 Tim Sort 알고리즘을 사용한다.

Tim Sort 알고리즘은 2002년 Tim Peters라는 엔지니어에 의해 등장했고 Insertion sort와 Merge sort를 결합하여 만든 정렬이다.

Tim Sort 는 O(N logN)의 시간 복잡도를 갖는다. 여러 다른 정렬에 비해 안정적이고 메모리 사용도 적기 때문에 Python, Java, Android, swift 등등 많은 프로그래밍 언어에서 표준 정렬 알고리즘으로 채택되어 사용되고 있다.

 

Python의 sort() 함수 역시 O(N logN)의 시간복잡도를 갖기 때문에 문제를 풀 때 다른 정렬 알고리즘을 사용하는 것 보다 좋은 결과를 얻을 것이다.

 

참고:

https://d2.naver.com/helloworld/0315536

 

---

알고리즘

버블 정렬