백준 | 2750 : 수 정렬하기 (Python/파이썬)

문제

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

 

입력

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

 

출력

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

 

 

 

풀이

 

버블 정렬 : 두 인접한 데이터의 크기를 비교해 정렬하는 방법

                 간단하게 구현할 수 있지만, 시간 복잡도는 O(n²)

 

1. 변수 n(수의 개수), a(n개의 수 - 리스트) 선언

리스트 a를 a=[]로 선언한 후, 반복문을 통해 값을 변경하도록 코드를 작성해 실패했다.

애초에 존재하지 않는 인덱스의 값을 변경하려고 했기 때문이다.

a=[0]*n 으로 간단히 변경해주었다.

 

2. 정렬을 위한 이중 반복문 작성

n개의 수가 있다고 하였을 때, n-1개의 수만 정렬작업을 해주면 전체를 정렬할 수 있다.

서로 인접한 두 수를 비교할 때, 이미 정렬된 데이터는 제외하고 비교하면 되므로 n-1-i번 비교를 하면 된다.

n = int(input())
a =[0]*n
for i in range(n) :
    a[i] = int(input())
    

for i in range(n-1) :
    for j in range(n-1-i) :
        if a[j]>a[j+1] :
            t = a[j]
            a[j] = a[j+1]
            a[j+1] = t


for i in a :
    print(i)