[Baekjoon 2750] 수 정렬하기 (python - 버블정렬)

문제 공유: https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

[문제설명]

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

 

[제한사항]

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

 

[입출력 예]

예제 입력	예제 출력
5 5 2 3 4 1	1 2 3 4 5

 

[입출력 예 설명]

첫번째 5는 5개의 숫자를 입력한다는 의미이다.

그 후의 입력되는 숫자들은 정렬해야되는 숫자들

 

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

 

---

[풀이 설명]

sort_list = []
for n in range(int(input())):
    sort_list.append(int(input()))

for m in range(len(sort_list)-1):
    for j in range(len(sort_list)-(m+1)):
        if sort_list[j] > sort_list[j+1]:
            temp = sort_list[j]
            sort_list[j]= sort_list[j+1]
            sort_list[j+1]=temp
for p in sort_list:
    print(p)

정렬하는 방법은 몹시 다양하고 많다. (선택, 삽입, 퀵, 합병, 버블, 힙 등)

이 중에서 어떠한 라이브러리 없이 python에서 기본으로 제공하는 라이브러리만 이용해서 버블정렬로 해보았다.

(  sys 라이브러리만 사용해도 이렇게 코드가 줄어든다. )

import sys
a = sys.stdin.readlines()
a = list(map(int, a))
for i in sorted(a[1:]):
    print(i)

 

버블정렬이란, 두 인접한 원소를 검사하여 정렬하는 방법이다.

시간복잡도가 O(n²)으로 오래걸리지만, 방법이 굉장히 간단하다.

 

 

변수 소개부터 하면 이러하다.

sort_list : 리스트에 담고 리스트에서 정렬할 것이라서 사용된 리스트 변수이다.

temp : 정렬할 값들을 이동할 때 이용되는 변수

 

풀이는 이렇게 된다.

1. 첫번째 for문으로 정렬할 숫자들을 입력받아 list에 넣는다.

 

2. 두번째 for문으로 리스트 길이의 -1 만큼 반복을 시킨다. 

-1 을 한 이유는 리스트의 마지막 변수는 비교를 할 필요 없기 때문 (버블정렬로 마지막에는 알아서 큰 값이 간다.)

 

3. 세번째 for문으로 버블정렬을 시킨다.

m+1을 한 이유는 버블정렬은 1개의 사이클이 돌면 제일 큰 값은 맨 뒤로 간다. (오름차순이기에)

그래서 진행될수록 뒤쪽에 있는 값들은 이미 정렬이 된 상태라서 또 비교를 하면서 정렬을 할 필요가 없다.

m은 0부터 시작되어 +1을 해서 한개씩 제외시켰다.

 

4. if문으로 비교하면서 자리를 서로 뒤바꾼다.

 

5. 네번째 for문으로 정렬된 리스트값 출력

 

---

ex_ 맨 앞에 설명했던 예제로 설명해보자면, 맨 처음에 입력된 값은 5 2 3 4 1 이다. 

사이클이 돌면 제일 큰 값을 뒤로 간다.

1) [0]인덱스 [1]인덱스 비교 (5 >2)

- 오름차순이기 때문에 앞 인덱스의 값이 더 커서 서로 자리를 바꾼다. 

(내림차순은 부등호만 변경하면 된다.)

 

2) [1] , [2] 비교 (5>3)

- 이것 또한 앞 인덱스의 값이 더 커서 서로 자리를 바꾼다.

 

3) [2], [3] 비교 (5>4) 

- 마찬가지이다.

 

4) [3], [4] 비교 (5>1)

 

이렇게 한 사이클이 돌면 

밑에 표처럼 2 3 4 1 5라는 결과가 리스트에 저장이 된다.

제일 큰 값이 제일 뒤로 간 것을 볼 수 있다.

 

이런 식으로 계속 반복하면 5사이클 만에 오름차순 정렬이 완료된다.

Cycle	[0] 인덱스	[1] 인덱스	[2] 인덱스	[3] 인덱스	[4] 인덱스
1	5	2	3	4	1
2	2	3	4	1	5
3	2	3	1	4	5
4	2	1	3	4	5
5	1	2	3	4	5