Monday, June 16, 2014

Sắp xếp nổi bọt (Bubble sort)

Ý tưởng: Duyệt qua mảng giá trị, so sánh giá trị của từng cặp phần tử cạnh nhau, nếu thứ tự không đúng thì đổi vị trí của chúng.
Độ phức tạp:
  Trường hợp tốt nhất: O(n)
  Trường hợp trung bình: O(n2)
  Trường hợp xấu nhất: O(n2)

Thuật toán
- Input: Mảng arr gồm n phần tử không có thứ tự
- Output: Mảng arr gồm n phần tử có thự tự (trong trường hợp này là thứ tự tăng dần)

Mã giả
Function bubble_sort (array arr, integer arr_size)
{
    integer i;
    for i from 1 to  arr_size do
    {
        integer j;
        for j from 2 to  arr_size do
        {
            if arr[j - 1] > arr[j] then
            {
                swap(arr[j - 1], arr[j]);
            }
        }
    }
    return  arr;
}

Function swap(integer  a, integer  b)
{
    integer temp = a;
    a = b;
    b = temp;
}

C++ code
void bubble_sort(int arr[], int arr_size)
{
  for(int i = 0; i < arr_size; i++)
  {
    bool stop = true;
    for(int j = 1; j < arr_size; j ++)
    {
      if(arr[j - 1] > arr[j])
      {
        stop = false;
        swap(arr[j - 1], arr[j]);
      }
    }
    if(stop) break;
  }
}