반응형
안녕하세요 기린입니다 :)
오늘은 지난 시간에 이어서 버블 정렬에 대해 알아볼텐데요
자 버블정렬이란 일련의 숫자들을 오름차순으로 정렬하는것 인데요
다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
1 10 5 8 7 6 4 3 2 9
버블정렬 또한 선택정렬과 같이 몹시 직관적인 해결 방법입니다
바로 가까이에 있는 두 숫자끼리 비교해서 더 작은 숫자를 앞으로 보내주는 것을 반복 하는 겁니다
다시 말해 버블정렬이란 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법인데요
정렬 알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘입니다
#include <stdio.h>
int main(void) {
int i, j, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i = 0; i < 10; i++) {
for(j = 0; j < 9 - i; j++) {
if(array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
for(i = 0; i < 10; i++) {
printf("%d ", array[i]);
}
return 0;
}
소스 코드를 보시면 단순히 반복적으로 두 숫자를 비교하여 앞으로 보냅니다. 이 과정에서 각 싸이클마다 가장 큰 값이 맨 뒤로 보내지게 됩니다. 컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 느린 안 좋은 알고리즘이라고 할 수 있습니다. 시간 복잡도는 선택 정렬과 동일합니다.
버블 정렬의 시간 복잡도는 O(N^2) 입니다.
이해가 되시나요 ??
다음 시간에는 삽입 정렬에 대해 알아보겠습니다
자 그럼 즐거운 코딩하세요 !
문의: ralla0405@gmail.com
반응형