버블정렬은 가장 간단한 알고리즘입니다.
인접한 원소를 비교하고 반복적으로 재배열 하면서 작동합니다.
예:
(5 1 4 2 8)->(1 5 4 2 8), 처음 두 원소를 비교하고 5와 1을 바꿉니다.
(1 5 4 2 8)->(1 4 5 2 8), 5와 4를 바꿉니다.
(1 4 5 2 8)->(1 4 2 5 8), 5와 2를 바꿉니다.
(1 4 2 5 8)->(1 4 2 5 8), 순서가 올바르기에 5와 8은 바꾸지 않습니다. pass
(1 4 2 5 8)->(1 4 2 5 8)pass
(1 4 2 5 8)->(1 2 4 5 8), 4와 2 교환
(1 2 4 5 8)->(1 2 4 5 8)pass
(1 2 4 5 8)->(1 2 4 5 8)pass
이제 정렬이 되었지만 알고리즘 내에서는 완료 되었는지 알 수 없기에, 전부 pass될 때 까지 반복합니다.
(1 2 4 5 8)->(1 2 4 5 8)pass
(1 2 4 5 8)->(1 2 4 5 8)pass
(1 2 4 5 8)->(1 2 4 5 8)pass
(1 2 4 5 8)->(1 2 4 5 8)pass
#include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
void reculsiveBubbleSort(int arr[], int n)
{
// Base case
if (n == 1)
return;
bool all_pass = true;
for (int i=0; i<n-1; i++)
if (arr[i] > arr[i+1]){
swap(arr[i], arr[i+1]);
all_pass = false;
}
printArray(arr, n);
if(all_pass == true){
return;
}
reculsiveBubbleSort(arr, n-1);
void bubbleSort(int arr[], int n)
{
for(int i=0; i<n-1;i++){//원소와 원소 사이마다 한번씩만 반복하면 된다. 그러므로 1회 제거
bool all_pass = true;
for(int j=0; j < n-1-i; j++){//1회 반복 시 제일 뒤의 원소는 정렬이 된 상태가 된다 그러므로 i만큼 빼준다.
if (arr[j] > arr[j+1])
{
swap(&arr[j], &arr[j+1]);
all_pass=false;
}
}
printArray(arr, n);
if(all_pass == true){
break;
}
}
}
int main()
{
int arr[] = {5, 4, 3, 2, 1};
int n = sizeof(arr)/sizeof(int);
bubbleSort(arr, n);
cout<<"Sorted array: \n";
printArray(arr, n);
return 0;
}
제자리 정렬이며 안정정렬이다.
최악의 경우 시간복잡도 O(n^2)이다.
"인접한 원소를 정렬해나가기 때문에 버블처럼 보인다. 1회 반복때마다 가장 큰 원소는 맨 뒤에 자리하게 된다."
'알고리즘 > 지식' 카테고리의 다른 글
[정렬 알고리즘] 합병 정렬 (0) | 2020.03.03 |
---|---|
[정렬 알고리즘] 삽입 정렬 (0) | 2020.03.03 |
[정렬 알고리즘] 선택 정렬 (0) | 2020.03.02 |
[기본] 정렬 알고리즘 (0) | 2020.03.02 |
소수 판별 (0) | 2019.12.06 |