Thuật Toán Selection Sort

Bài hôm nay chúng ta cùng tìm hiểu về các thuật toán sắp xếp.

Đây cũng là một chủ để phổ biến về thuật toán trong kỹ thuật lập trình và nó được sử dụng nhiều trong các dự án phần mềm.

Có rất nhiều các thuật toán được sử dụng cho bài toán sắp xếp một danh sách.

Bài đầu tiên này, chúng ta cùng tìm hiểu về thuật toán Selection Sort (Thuật toán sắp xếp lựa chọn)

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

+ Tìm ra phần từ nhỏ nhất trong tập T ban đầu, và hoán đổi vị trí của nó cho phần tử đầu tiên.

+ Như vậy phần tử đầu tiên là phần tử có giá trị nhỏ nhất.

+ Ta không quan tâm đến nó nữa bắt đầu 1 tập con tính từ phần tử thứ hai, lại làm tương tự như trên, tìm phần tử nhỏ nhất trong tập con và hoán vị nó về vị trí ban đâu của tập.

=> Cứ như vậy cho đến khi chuỗi chỉ còn 1 phần tử thì dừng lại.

Như vậy về bản chất là chúng ta sẽ hoán vị n-1 phần tử.

Độ phức tạp thời gian : O (N²) // Là số phần tử.

2 Thực hành Selection Sort



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

void Swap(int& a, int& b)
{
  int temp = a;
  a = b;
  b = temp;
}

void SelectionSort(int arr[], int n)
{
  for (int i = 0; i < n-1; ++i)
  {
    int min_idx = i;
    for (int j = i+1; j < n; j++)
    {
      if (arr[j] < arr[min_idx])
        min_idx = j;
    }
    Swap(arr[min_idx], arr[i]);
  }
}

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

int main()
{
  int arr[] = {44, 35, 2, 12, 10};
  int n = sizeof(arr)/sizeof(arr[0]);
  SelectionSort(arr, n);
  std::cout << "Sorted list: \n";
  Show(arr, n);

  _getch();
  return 0;
}