버블 정렬

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

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

버블 정렬 알고리즘

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

위 알고리즘의 1 단계를 통과라고도합니다. 크기가 n 인 배열을 정렬하려면n-1 패스가 필요합니다.

버블 정렬 알고리즘 예제

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

• 첫 번째 패스 :

• 두 번째 패스 :

• 세 번째 패스 :

• 네 번째 패스 :

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

• 최악의 경우

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

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

• 베스트 케이스

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

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

공간 복잡성

이 알고리즘의 공간 복잡도는 임시 변수 이외의 추가 메모리가 필요하지 않기 때문에O(n)입니다.