버블 정렬 재귀

1. 버블 정렬 재귀 알고리즘
2. 버블 정렬 재귀 알고리즘 예제
3. 버블 정렬 재귀 알고리즘 구현
4. 버블 정렬 알고리즘 복잡성

버블 정렬은 간단한 정렬 알고리즘입니다. 인접한 요소를 반복적으로 비교하고 순서가 잘못된 경우 교체하여 작동합니다. 반복되는 비교는 배열의 끝에서 가장 작은 / 가장 큰 요소를 버블 링하므로이 알고리즘을 버블 정렬이라고합니다. 비효율적이지만 여전히 정렬 알고리즘의 기초를 나타냅니다.

버블 정렬 재귀 알고리즘

n 개의 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다.

버블 정렬 재귀 알고리즘 예제

배열이(5,3,4,2,1)이라고 가정합니다. 버블 정렬 알고리즘을 사용하여 정렬합니다.

• 첫 번째 패스 :

• 두 번째 패스 :

• 세 번째 패스 :

• 네 번째 패스 :

네 번째 패스 후에 정렬 된 배열을 얻습니다-(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(n²) 정도입니다.

• 최악의 경우

최악의 경우는 배열이 역으로 정렬되어 최대 비교 및 ​​스와핑 횟수를 수행해야하는 경우에 발생합니다.

최악의 시간 복잡도는 O(n²)입니다.

• 베스트 케이스

가장 좋은 경우는 배열이 이미 정렬 된 다음 N 개의 비교 만 필요한 경우에 발생합니다.

최상의 경우 시간 복잡도는O(n)입니다.

공간 복잡성

이 알고리즘의 공간 복잡성은 스택 내부에 저장된 재귀 호출로 인해 O(n)입니다.