250x250
Notice
Recent Posts
Recent Comments
- Today
- Total
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- await
- double quote
- wil
- TailwindCSS
- flutter
- mongoose
- nginx
- MYSQL
- jsonwebtoken
- single quote
- JavaScript
- sequelize
- css
- TypeScript
- async
- til
- Express
- Find
- certbot
- https
- clipBehavior
- findByIdAndDelete
- Node.js
- moment
- AWS
- atlas
- mongodb
- RDS
- EC2
- Nodejs
Link
Archives
기억 휘발 방지소
버블정렬 (Bubble Sort) 본문
728x90
반응형
📌 버블정렬 (Bubble Sort)
버블 정렬은 뒤에서부터 앞으로 정렬하는 특징을 갖고 있다.
가장 큰 수가 맨 뒤로 가고 그 다음 큰 수가 그 앞에 위치하게 된다.
시간복잡도는 O(n^2)이다.
👉 과정
[3, 2, 4, 5, 1]
3과 2 swap
가장 앞에 수와 그 다음 수를 비교해서 앞에 있는 수가 더 크면 두 수를 swap한다.
[2, 3, 4, 5, 1]
3과 4를 비교하는데 3이 더 작기 때문에 swap 없이 넘어간다.
[2, 3, 4, 5, 1]
4와 5도 마찬가지로 4가 5보다 더 작기 때문에 swap 없이 넘어간다.
[2, 3, 4, 5, 1]
5와 1 swap
5가 1보다 크기 때문에 5와 1을 swap
[2, 3, 4, 1, 5]
가장 큰 수인 5는 자리가 정해졌기 때문에 이 다음부터는 5 바로 전까지만 위에 과정을 반복해 비교한다.
[2, 3, 4, 1, 5]
4와 1 swap
[2, 3, 1, 4, 5]
3과 1 swap
[2, 1, 3, 4, 5]
2와 1 swap
[1, 2, 3, 4, 5]
정렬 끝
👉 구현
def bubble_sort(arr):
for i in range(len(arr) - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
728x90
반응형
'Algorithm' 카테고리의 다른 글
유클리드 알고리즘 (Euclidean Algorithm) (0) | 2022.09.07 |
---|---|
삽입정렬 (Insertion Sort) (0) | 2022.07.25 |
선택정렬 (Selection Sort) (0) | 2022.07.25 |
진수변환 (0) | 2022.07.23 |
약수 구하기 (0) | 2022.07.22 |