728x90
반응형
📍 버블 정렬: 가장 단순한 정렬 알고리즘
- 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ..., 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
728x90
'자료구조 및 알고리즘 > 자료구조 및 알고리즘' 카테고리의 다른 글
정렬 - 3) 삽입 정렬 (insertion sort) (0) | 2024.04.08 |
---|---|
정렬 - 2) 선택 정렬 (selection sort) (0) | 2024.04.08 |
Brute Force(완전 탐색) (0) | 2023.07.24 |
DFS와 BFS (0) | 2023.04.07 |
다이나믹 프로그래밍 (Dynamic Programming) (0) | 2023.02.02 |