Thuật toán Bubble Sort

 

Hôm nay chúng ta cùng tìm hiểu về thuật toán  Bubble Sort.

1. Nguyên lý cơ bản của Bubble Sort

– Là một thuật toán đơn giản dễ hiểu và dễ thực hiện.

– Thực hiện việc kiểm tra so sánh sánh hai phần tử bên cạnh nhau, rồi hoán đổi vị trí cho nhau.

– Độ phức tạp của thuật toán là: O = N²

2 Thực hành.

// Phattrienphanmem123az.com
#include <iostream>
#include <conio.h>

using namespace std;

void Swap(int& x, int& y)
{
  int temp = x;
  x = y;
  y = temp;
}

void BubbleSort(int arr[], int n)
{
  for (int i = 0; i < n-1; ++i)
  {
    bool swapped = false;
    for (int j = 0; j < n-i-1; ++j)
    {
      if (arr[j] > arr[j+1])
      {
        Swap(arr[j], arr[j+1]);
        swapped = true;
      }
    }

    if (swapped == false)
      break;
  }
}

void Show(int arr[], int size)
{
  for (int i=0; i < size; ++i)
    std::cout << arr[i] << " ";
}

int main()
{
  int arr[] = {44, 36, 15, 12, 32, 10, 80};
  int n = sizeof(arr)/sizeof(arr[0]);
  BubbleSort(arr, n);
  std::cout << "Sorted List: \n";
  Show(arr, n);
  _getch();
  return 0;
}

TPham