[백준 2750번] 수 정렬하기 | 버블정렬(bubble sort) 알고리즘

 

 

 

2750번: 수 정렬하기

문제

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

입력

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

출력

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

 

---

 

 

버블 정렬의 원리

버블 정렬은 인접한 두 원소를 비교해서 오름차순으로 정렬하는 과정을 여러 번 반복하는 정렬 알고리즘이다. 작은 값을 앞으로 밀어서 정렬하는 방식을 사용한다.

 

- 인접한 두 원소를 비교하며 큰 값을 오른쪽으로 이동시킨다.
- 한 번의 반복에서 가장 큰 원소가 마지막으로 정렬된다.

 

 

구현 순서

(1) 첫 번째 원소부터 N - 1번째 원소까지 살펴본다.
(2) 각 원소와 바로 다음 원소를 비교한다.
(3) 다음 원소보다 크다면 원소를 교환한다.
(4) 첫 번째 원소부터 N - 1번째 원소까지 한 번 비교하는 과정을 모든 원소가 정렬될 때까지 반복한다.

 

반응형

for i in range(N - 1):
    for j in range(N - 1 - i):
        if A[j] > A[j + 1]:
            temp = A[j]
            A[j] = A[j + 1]
            A[j + 1] = temp

 

 위 코드에서 첫 번째 for문은 (N - 1)번 반복한다. 버블 정렬의 모든 과정이 완료되는 동안 첫 번째 원소부터 N - 1번째 원소까지 살펴보기 때문이다.

 

 두 번째 for문에서는 (N - 1 - i)번 반복한다. 여기서 i는 첫 번째 for문의 반복 횟수를 나타낸다. 이 이유는 각 반복마다 큰 값이 뒤로 이동하면서 정렬되기 때문에, 이미 정렬된 부분은 비교할 필요가 없으므로 줄어드는 것이다.

 

 if문은 현재 원소(A[j])와 바로 다음 원소(A[j + 1])를 비교해서 현재 원소가 더 크면 두 원소를 교환하는 부분이다. 여기서 모든 원소가 정렬될 때까지 반복을 수행한다. 

 

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

 

 

 

코드 흐름 간단 요약

활용한 버블 정렬 알고리즘으로 인접한 원소의 크기를 비교해가면서 정렬을 수행하고,

이를 (N-1)번 반복하면서 각 반복에서 이미 정렬된 부분을 제외한 나머지 부분을 비교한다.

그리고 정렬이 완료되면 결과를 출력한다.