TUTORIAL · Algorithm
버블 정렬
이 튜토리얼에서는 버블 정렬 알고리즘을 소개합니다.
이 페이지의 내용
버블 정렬은 간단한 정렬 알고리즘입니다. 인접한 요소를 반복적으로 비교하고 순서가 잘못된 경우 교체하여 작동합니다. 반복되는 비교는 배열의 끝에서 가장 작은 / 가장 큰 요소를 버블 링하므로이 알고리즘을 버블 정렬이라고합니다. 비효율적이지만 여전히 정렬 알고리즘의 기초를 나타냅니다.
버블 정렬 알고리즘
n 개의 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.
-
처음 두 요소 (
A[0]및A[1])의 쌍에서 시작하여 값을 비교하고 순서가 올바르지 않으면 서로 바꿉니다. 다음 쌍 (A[1]및A[2])에 대해 동일하게 수행하고 나머지 배열에서도 유사하게 이동합니다. 가장 작은 / 가장 큰 요소는이 단계 후 마지막 위치에 있습니다. -
나머지 반복에 대해 위의
(n-2)단계를 반복합니다. 마지막 요소가 이미 정렬되어 있으므로 매번 배열 크기를 줄입니다. 이 반복에서 가장 작은 / 가장 큰 요소가 가장 오른쪽 위치로 이동합니다.
위 알고리즘의 1 단계를 통과라고도합니다. 크기가 n 인 배열을 정렬하려면n-1 패스가 필요합니다.
버블 정렬 알고리즘 예제
배열이(5,3,4,2,1)이라고 가정합니다. 버블 정렬 알고리즘을 사용하여 정렬합니다.
- 첫 번째 패스 :
| (** 5 3 ** 4 2 1) | → | (** 3 5 ** 4 2 1) | (3 <5 스왑 됨) |
| (3 ** 5 4 ** 2 1) | → | (3 ** 4 5 ** 2 1) | (4 <5 스왑 됨) |
| (3 4 ** 5 2 ** 1) | → | (3 4 ** 2 5 ** 1) | (2 <5 스왑 됨) |
| (3 4 2 ** 5 1 **) | → | (3 4 2 ** 1 5 **) | (1 <5 스왑 됨) |
- 두 번째 패스 :
| (** 3 4 ** 2 1 5) | → | (** 3 4 ** 2 1 5) | |
| (3 ** 4 2 ** 1 5) | → | (3 ** 2 4 ** 1 5) | (2 <4 스왑 됨) |
| (3 2 ** 4 1 ** 5) | → | (3 2 ** 1 4 ** 5) | (1 <4 스왑 됨) |
- 세 번째 패스 :
| (** 3 2 ** 1 4 5) | → | (** 2 3 ** 1 4 5) | (2 <3 스왑 됨) |
| (2 ** 3 1 ** 4 5) | → | (2 ** 1 3 ** 4 5) | (1 <3 스왑 됨) |
- 네 번째 패스 :
| (** 2 1 ** 3 4 5) | → | (** 1 2 ** 3 4 5) | (1 <2 스왑 됨) |
네 번째 패스 후에 정렬 된 배열을 얻습니다-(1 2 3 4 5)
버블 정렬 알고리즘 구현
#include <iostream>
using namespace std;
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int n = 5;
int arr[5] = {5, 3, 4, 2, 1};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bubble_sort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
버블 정렬 알고리즘 복잡성
시간 복잡성
- 평균 사례
평균적으로 n-i 비교는 버블 종류의 i번째 패스에서 이루어진다. 따라서 n 개의 패스가있는 경우 평균 시간 복잡도는 다음과 같이 구할 수 있습니다.
(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2
따라서 시간 복잡도는 O(n2) 정도입니다.
- 최악의 경우
최악의 경우는 배열이 역으로 정렬되어 최대 비교 및 스와핑 횟수를 수행해야하는 경우에 발생합니다.
최악의 시간 복잡도는 O(n2)입니다.
- 베스트 케이스
가장 좋은 경우는 배열이 이미 정렬 된 다음 N 개의 비교 만 필요한 경우에 발생합니다.
최상의 경우 시간 복잡도는O(n)입니다.
공간 복잡성
이 알고리즘의 공간 복잡도는 임시 변수 이외의 추가 메모리가 필요하지 않기 때문에O(n)입니다.
