버블 정렬 (Bubble-Sort) - with Python

💡문제 설명

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

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

입력

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

출력

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

💡요구사항 분석

정렬되지 않은 배열이 있다고 가정합니다. (오름차순 정렬)

[5, 4, 3, 1, 2]

알고리즘 배열에 첫번째 원소와 두번째 원소와 대소를 비교하여 두 수를 교환합니다.

[4, 5, 3, 1, 2]

두번째 원소와 세번째 원소 크기를 비교한 후 조건에 부합한다면 교환합니다.

[4, 3, 5, 1, 2 ]

세번째 원소와 네번째 원소를 비교합니다 조건에 따라 교환합니다.

[4, 3, 1, 5, 2]

네번째 원소와 마지막 원소를 비교한 후 조건에 따라 교환합니다.

[4, 3, 1, 2, 5]

이 과정을 반복을 해주면 정렬이 완료됩니다.

맨마지막 원소는 정렬이 된 수이기 때문에 예외처리가 필요합니다.

예제

💡코드풀이

1. import

import sys 

• 빠른 입출력을 위해 sys 라이브러리를 사용합니다.

2. N 입력받기

n = int(sys.stdin.readline())

• 배열의 크기를 입력받습니다.

3. 배열 선언

arr = [] 

• 정답을 저장할 배열을 선언해 줍니다.

4. 배열 입력받기

for i in range(n):
		arr.append(int(sys.stdin.readline()))

• N 번의 반복문을 수행하면서 배열에 값을 넣어줍니다.

5. 이중 반복문 수행

for i in range(n):
    for j in range(n - i - 1):

• 처음 반복문을 N번 수행해줍니다.
• 두번째 반복문은 정렬 후 뒷자리 인덱스에 대한 예외처리입니다.

6. 두 수 비교 후 조건에 부합하면 교환하기

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

• arr[j] > arr[j + 1] 의 조건이 부합하면 두 수를 교환하는 로직입니다.

7. 정답출력

for i in arr:
    print(i) 

전체 코드

import sys

n = int(sys.stdin.readline())

arr = []

for i in range(n):
    arr.append(int(sys.stdin.readline()))

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

for i in arr:
    print(i)

💡버블정렬에 대해

• 버블 정렬은 시간복잡도가 O(n2) 으로 매우 느립니다.
• 하지만 코드가 단순하기 때문에 자주 사용되는 알고리즘입니다.