TUTORIAL · Algorithm
버블 정렬 재귀
이 튜토리얼은 버블 정렬 재귀 알고리즘을 사용하여 배열에서 정렬을 수행하는 방법을 보여줍니다.
이 페이지의 내용
버블 정렬은 간단한 정렬 알고리즘입니다. 인접한 요소를 반복적으로 비교하고 순서가 잘못된 경우 교체하여 작동합니다. 반복되는 비교는 배열의 끝에서 가장 작은 / 가장 큰 요소를 버블 링하므로이 알고리즘을 버블 정렬이라고합니다. 비효율적이지만 여전히 정렬 알고리즘의 기초를 나타냅니다.
버블 정렬 재귀 알고리즘
n 개의 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.
-
배열
A의 크기가1이면 배열이 이미 정렬 된 것입니다. 그래서 돌아 오십시오. -
그렇지 않으면 주어진 하위 배열에 대해 반복적 인 버블 정렬의 한 번의 패스를 수행합니다. 마지막 요소를 올바른 위치에 배치합니다.
-
재귀 호출을 사용하여 크기가 1만큼 축소 된 더 작은 하위 배열에서 위 단계를 다시 수행합니다.
버블 정렬 재귀 알고리즘 예제
배열이(5,3,4,2,1)이라고 가정합니다. 버블 정렬 알고리즘을 사용하여 정렬합니다.
- 첫 번째 패스 :
| (** 5 3 ** 42 1) | → | (** 3 5 ** 42 1) | (3 <5 스왑 됨) |
| (3 ** 5 4 ** 2 1) | → | (3 ** 4 5 ** 2 1) | (4 <5 스왑 됨) |
| (34 ** 5 2 ** 1) | → | (34 ** 2 5 ** 1) | (2 <5 스왑 됨) |
| (34 2 ** 5 1 **) | → | (34 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 ** 34 5) | → | (** 1 2 ** 34 5) | (1 <2 스왑 됨) |
네 번째 패스 후에 정렬 된 배열을 얻습니다-(12 34 5)
버블 정렬 재귀 알고리즘 구현
#include <bits/stdc++.h>
using namespace std;
void bubbleSort(int arr[], int n) {
if (n == 1) return;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
}
}
bubbleSort(arr, n - 1);
}
int main() {
int n = 8;
int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bubbleSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
버블 정렬 알고리즘 복잡성
시간 복잡성
- 평균 사례
평균적으로 ’n-i’비교는 거품 정렬의 ith패스에서 이루어집니다. 따라서 n 개의 패스가있는 경우 평균 시간 복잡도는 다음과 같이 구할 수 있습니다.
(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2
따라서 시간 복잡도는 O(n2) 정도입니다.
- 최악의 경우
최악의 경우는 배열이 역으로 정렬되어 최대 비교 및 스와핑 횟수를 수행해야하는 경우에 발생합니다.
최악의 시간 복잡도는 O(n2)입니다.
- 베스트 케이스
가장 좋은 경우는 배열이 이미 정렬 된 다음 N 개의 비교 만 필요한 경우에 발생합니다.
최상의 경우 시간 복잡도는O(n)입니다.
공간 복잡성
이 알고리즘의 공간 복잡성은 스택 내부에 저장된 재귀 호출로 인해 O(n)입니다.
