알고리즘 요약
버블정렬 (bubble sort)
-앞쪽 부터 인접한 두 값을 비교하면서 정렬 하는 것을 반복해서 정렬.
-시간복잡도: O(n²)
정렬 과정 설명
① ② ③ ④ ⑤ : 위치번호
[3, 2, 5, 4, 1] :숫자열이 있을 경우,
-①3 ②2 비교해서 뒤에 숫자가 작으므로 서로 위치를 변경
[2, 3, 5, 4, 1]
-②3 ③5 비교해서 뒤에 숫자가 크므로 위치 변경없음
[2, 3, 5, 4, 1]
-③5 ④4 비교해서 뒤에 숫자가 작으므로 서로 위치 변경
[2, 3, 4, 5, 1]
-④5 ⑤1 비교해서 뒤에 숫자가 작으므로 서로 위치 변경
[2, 3, 4, 1, 5] : 마지막 비교후에는 마지막위치에 가장 큰 값이 위치한다
-제일 큰 값을 가진 마지막 자리를 제외하고 처음부터 계속 반복하면 정렬이 끝난다.
[1, 2, 3, 4, 5]
def bubble_sort(a): # a는 숫자열
ln = len(a) - 1 # 배열의 마지막 위치값
for i in range(ln, 0, -1): # 배열 마지막값은 최대값이므로 비교 길이를 줄여준다
for j in range(i): # 비교할 마지막 위치까지 루프
if a[j] > a[j + 1]: # 뒤에 값이 더 작으면
a[j], a[j + 1] = a[j + 1], a[j] # 서로 값을 교환
return a # 루프가 끝나면 정렬 끝. 리턴.
print(bubble_sort([5, 2, 3, 4, 1])) # 결과는 [1, 2, 3, 4, 5]
#include <stdio.h>
void bubble_sort(int a[], int len) {
int i, j, tmp;
for (i = len - 1; i >= 0; --i) { // 루프 마다 마지막은 최대값이므로 비교 길이를 줄여준다
for (j = 0; j< i; j++) { // 인덱스 0 부터 주어진 길이까지 값 비교.
if (a[j] > a[j + 1]) { // 뒤에값이 더 작으면 서로 값을 교환. 최종적으로 제일큰 값이 맨뒤로 감.
tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
}
}
}
}
int main() { // 버블정렬 함수 테스트
int i, a[] = {3, 2, 5, 4, 1}, len = sizeof(a) / sizeof(a[0]);
bubble_sort(a, len);
for (i = 0; i < len; i++) printf("%d ", a[i]); // 결과: 1 2 3 4 5
}