정렬 - 1) 버블 정렬 (bubble sort)

 

📍 버블 정렬: 가장 단순한 정렬 알고리즘 

• 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ..., n-1번째와 n번째 값을 비교한다.
  순서가 맞지 않은 값을 서로 교환하고, 정렬이 될 때까지 반복한다.
• 비효율적인 알고리즘
• 시간복잡도: O(N^2)
  
  • ex) 5, 4, 3, 2, 1이라는 데이터가 존재한다고 가정할 때 
  • 한 바퀴 돌면 4, 3, 2, 1, 5로 정렬됨
  • 두 바퀴 돌면 3, 2, 1, 4, 5로 정렬됨
  • N개의 숫자가 N-1 바퀴 돌아야 함 ( 나머지 한 개는 자연스럽게 정렬되기 때문에 고려하지 않아도 됨)

---

 

💬 python 코드 

• n 개의 원소가 주어졌을 때, 버블 정렬을 이용해 n개의 숫자를 오름차순으로 정렬

n = int(input())
arr = list(map(int, input().split()))

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

print(*arr)

 

 

• 입력

6
5 2 6 1 3 8

 

 

• 출력

1 2 3 5 6 8