[🥉1 / 백준 2750 / 파이썬] 수 정렬하기 (버블 정렬)

 

2750번: 수 정렬하기

 

문제

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

입력

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

출력

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

 

예제 입력 5 5 2 3 4 1

예제 출력 1 2 3 4 5

 

풀이

 

버블 정렬은 이웃한 숫자를 비교하여 더 큰 수를 뒤로 보내는 방식의 정렬이다.

 

n개의 숫자가 주어지면 n-1 번의 비교가 이루어지며 수의 배치와 상관없이 일정하게 탐색하기 때문에 최악, 최상, 평균 모두 O(n2) 시간복잡도를 가진다.

 

버블 정렬이 어떻게 이루어지는지 잘 확인하기 위한 코드를 짜봤다.

 

n=int(input())
num = [int(input()) for i in range(n)]

print(num)

for i in range(n-1):
    for j in range(n-1):
        if num[j] > num[j+1]:
            temp = num[j]
            num[j] = num[j+1]
            num[j+1] = temp
            print("Sort", num[j],num[j+1])
    print(num)

[5, 2, 3, 4, 1]

Sort 2 5

Sort 3 5

Sort 4 5

Sort 1 5

[2, 3, 4, 1, 5]

Sort 1 4

[2, 3, 1, 4, 5]

Sort 1 3

[2, 1, 3, 4, 5]

Sort 1 2

[1, 2, 3, 4, 5]

 

위와 같은 출력이 나온다.

목록의 처음부터 끝까지 수를 번갈아서 n-1번 만큼 비교하며 인접한 두 수를 비교하여 교체하는 것을 알 수 있다.

 

아래는 정답 코드이다.

 

import sys
n=int(sys.stdin.readline())
num = [int(sys.stdin.readline()) for i in range(n)]

for i in range(n-1):
    for j in range(n-1):
        if num[j] > num[j+1]:
            temp = num[j]
            num[j] = num[j+1]
            num[j+1] = temp
for i in num:
    print(i)