[Algorithm] Bubble Sort 구현하기
Bubble Sort를 구현해보자
환경
- Python
- C++
Bubble Sort란?
원리
- 인접한 2개의 값을 비교한후 값을 변경하는 과정을 통해서 정렬을 진행하는 알고리즘이다.
- 오름차순의 경우라면 인접한 두 수를 비교했을 때 앞의 수가 더 크다면 그 둘의 값을 바꾸는 방식으로 아래의 사진을 보면 이해가 쉽다.
특징
- 위에 사진처럼 왼쪽에서부터 오른쪽으로 진행하면서 정렬을 진행한다고 했을 때 1번 왼쪽에서 오른쪽까지 갈 때마다 가장 오른쪽에는 가장 큰 값이 위치하게 된다!
- 코드의 구현은 쉬우나 복잡도가
O(n^2)의 성능을 나타낸다.
복잡도
- 시간복잡도:
O(n^2) - 공간복잡도:
O(1)(swap을 위한 변수만 필요합니다.)
구현 코드(Python)
def merge_sort_better(A):
for i in range(len(A) - 2, 0, -1):
for j in range(0, i + 1):
if A[j] > A[j + 1]:
tmp = A[j]
A[j] = A[j + 1]
A[j + 1] = tmp
return A
def merge_sort_normal(A):
for i in range(0, len(A)):
for j in range(0, len(A) - 1):
if A[j] > A[j + 1]:
tmp = A[j]
A[j] = A[j + 1]
A[j + 1] = tmp
return A
import random
A = [random.randint(0, 100) for _ in range(0, 10)]
print(A)
merge_sort_better(A)
print(A)
구현 코드(C, C++)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void bubble_sort_better(int a[], int len) {
for (int i = len - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
if (a[j] > a[j + 1]) {
swap(&a[j], &a[j + 1]);
}
}
}
}
void bubble_sort_normal(int a[], int len) {
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len - 1; ++j) {
if (a[j] > a[j + 1]) {
swap(&a[j], &a[j + 1]);
}
}
}
}
int main() {
int a[5];
int len = sizeof(a) / sizeof(a[0]); // 배열길이
// 랜덤함수를 위한 srand와 seed
srand(time(NULL));
// 벡터 초기화
for (int i = 0; i < len; i++) {
// 1 ~ 50까지의 난수 생성
a[i] = rand() % 50 + 1;
}
// 정렬 전 출력
for (int i = 0; i < len; i++) {
printf("%d ", a[i]);
}
printf("\n");
// 거품정렬
bubble_sort_better(a, len);
// 정렬 후 출력
for (int i = 0; i < len; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}