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(n²)
  Trường hợp xấu nhất: O(n²)

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;
  }
}

Sắp xếp chèn (Insertion sort)

Ý tưởng:Duyệt mảng n phần tử. Với mỗi phần tử được duyệt, chuyển nó sang trái cho đến khi nó lớn hơn phần tử bên trái.
Độ phức tạp
    Trường hợp tốt nhất: O(n)
    Trường hợp xấu nhất: O(n²)
    Trường hợp trung bình: O(n²)
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 insertion_sort(array arr, integer arr_size)
{
  integer i = 2;
  while(i <= arr_size)
  {
    value = arr[i];
    integer k = i;
    while(k > 1 and arr[k - 1] > value)
    {
      arr[k] = arr[k - 1];
      k = k - 1;
    }
    arr[k] = value;
    i = i + 1;
  }
  return arr;
}

C/C++ code

void insert_sort(int arr[], int arr_size)
{
  for(int i = 1; i < arr_size; i++)
  {
    int value = arr[i];
    int k = i;
    while(k > 0 && arr[k - 1] > value)
    {
      arr[k] = arr[k - 1];
      k--;
    }
    arr[k] = value;
  }
}

Java code

private static void insertion_sort(int arr[])
{
  int arr_size = arr.length;
  for(int i = 1; i < arr_size; i++)
  {
    int value = arr[i];
    int k = i;
    while(k > 0 && arr[k - 1] > value)
    {
      arr[k] = arr[k - 1];
      k--;
    }
    arr[k] = value;
  }
}

Các thuật toán sắp xếp

Sắp xếp (sorting) là đặt các phần tử của một danh sách theo một thứ tự nhất định. Bài toán sắp xếp là bài toán cơ bản trong khoa học máy tính, được ứng dụng trong các bài toán tìm kiếm (searching), trộn (merging),...
Các bài toán sắp xếp thường được chia thành hai lớp bài toán: sắp xếp bằng so sánh (comparision sorts) và sắp xếp không so sánh (non-comparision sorts).
Sắp xếp bằng so sánh:

  Bubble sort
  Selection sort
  Insertion sort
  Quicksort
  Merge sort
  Heapsort
  Binary tree sort
  In-place merge sort
  Introsort
  Timsort
  Shell sort
  Cycle sort
  Library sort
  Patience sorting
  Smoothsort
  Strand sort
  Tournament sort
  Cocktail sort
  Comb sort
  Gnome sort
  UnShuffle sort
  Block sort

Sắp xếp không so sánh:

  Pigeonhole sort
  Bucket sort
  Couting sort
  LSD Radix sort
  MSD Radix sort
  Spreadsort