|
Bubble Sort 버블 정렬이란? |
Bubble Sort는 대표적인 정렬 알고리즘 중 하나입니다.
그것은 가장 쉬운 정렬 중 하나입니다.
속도 면에서 우월하지는 않지만, 코드가 간편해 널리 쓰이고 있습니다.
Bubble Sort의 알고리즘
버블 정렬에 n개의 자료가 있을 때,
1번째와 2번째를 비교하고
(n-1)번째와 n번째를 비교하고...
그리고 처음으로 돌아가 비교하기 시작하는 방식으로 정렬합니다.
단순 비교 방식이기에 최악의 경우에는 n(n-1)/2 번 연산하게 됩니다.
그래서 위와 같은 식으로 정렬되는데,
이것이 거품이 떠오르는 것과 비슷하다 하여 Bubble Sort라고 합니다.
▲헝가리 포크 댄스를 통해 Bubble-Sort를 설명한 영상
이 영상은 Bubble Sort를 잘 설명하는 예입니다.
Bubble Sort의 C/C++ 코드
|
C++ 코드 |
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 | #include <iostream> using namespace std; int main() { int n,a,b,swap; int array[1005], i; cin>>n; for(i=0; i<n; i++) cin>>array[i]; for (a=0 ; a<n-1 ;a++) { for (b=0 ;b<n-a-1; b++) { if (array[b] > array[b+1]) { swap = array[b]; array[b] = array[b+1]; array[b+1] = swap; } } } for(i=0;i<n;i++) cout<<array[i]<<" "; } | cs |
n |
자료의 개수 |
array[1005] |
약 1000개의 자료를 담을 배열 |
i |
조건문 사용 |
n의 값을 cin받습니다.
n개의 자료를 array에 넣습니다.
( b , b+1 ) 의 대소를 비교하면서 반복하고,
대소 관계에 문제가 있다면 Swap합니다.
|
|
C 코드 (재귀) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | void Bubble_Sort(int len) { for( i=0 ; i<len ; i++ ) for ( j = 0 ; j < len - i - 1 ; j++) if ( a[j] > a[j+1] ){ int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } | cs |
LEN | 자료의 개수 |
a | 자료를 담을 배열 |
i | 조건문 사용 |
|
Bubble Sort의 느린 속도 |
Bubble Sort, Insert Sort, Quick Sort에서
36000을 넘지 않는 Test Case 100,000개를 넣어 놓고
정렬했을 때 시간이 가장 빠른 경우를 출력
5회 진행해 가장 빠른 것을 출력했습니다.
Bubble Sort 사용 : 38.34초
Insert Sort 사용 : 23.04초
Quick Sort 사용 : 14.17초
Bubble Sort > Insert Sort > Quick Sort 순으로
38.34 > 23.04 > 14.17 초로 큰 격차를 보였습니다.
|
Bubble Sort 정리 |
Bubble Sort는 일일히 비교해가는 방식으로 계산을 해 나가는데,
단순한 방법으로 아주 쉽고, 간단하고, 짧은 코드가 나오지만,
시간이 오래 걸립니다.
'프로그래밍' 카테고리의 다른 글
[CMD, C++] 파일 삭제하기, string 이용하기 (0) | 2018.10.17 |
---|---|
[C++] 랜덤 무작위 수 난수 생성하기 (0) | 2018.08.15 |
영재원 과제 / 5월달 (0) | 2018.07.13 |
한양대 영재원 : 4월 단기연구과제 (0) | 2018.05.01 |