Thuật toán sắp xếp chọn(Selection Sort)

Trong bài viết này Blog tuicocach.com sẽ giới thiệu tới các bạn thuật toán sắp xếp chọn. Đây là một trong các thuật toán sắp xếp căn bản thường dùng.

Ý tưởng của thuật toán selection sort

Minh họ thuật toán sắp xếp chọn(nguồn wikipedia.org)

Thuật toán selection sort chia mảng ra làm 2 mảng con, mảng bên trái đã được sắp xếp và bên phải chưa được sắp xếp. Thuật toán selection sort sắp xếp một mảng bằng cách đi tìm phần tử có giá trị nhỏ nhất(sắp xếp mảng tăng dần) trong đoạn đoạn chưa được sắp xếp và đổi chỗ phần tử nhỏ nhất đó với phần tử ở đầu đoạn chưa được sắp xếp(không phải đầu mảng).

Ví dụ: Sử dụng thuật toán SelectionSort sắp xếp dãy {3,2,6,9,1,4,7,10,8,5} theo thứ tự tăng dần ta sẽ thấy các bước thực hiện như sau

Cài đặt thuật toán trên ngôn ngữ C/C++

#include <stdio.h>
//Hàm đổi chỗ 2 số nguyên a, b
void swap(int &a, int &b)
{
	int temp = a;
	a=b;
	b=temp;
}
//Hàm sắp xếp chọn (selection Sort)
void selectionSort(int arr[], int n)
{
    for (int i = 0; i < n-1; i++)
    {
   	  int min_index = i;
   	  for (int j = i+1; j < n; j++)
      {
//Tìm vị trí phần tử nhỏ nhất
      	if(arr[min_index] > arr[j])
      	 min_index = j;
      }
  // Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên
     	swap(arr[i], arr[min_index]);
	}
}
//Hàm xuất mảng
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main()
{
	int arr[] = {3,2,6,9,1,4,7,10,8,5};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Kết quả chạy chương trình trên

Đánh giá thuật toán sắp xếp chèn

Độ  phức tạp thuật toán: O(n^2)

Cảm ơn đã theo dõi bài viết, nếu có bất kỳ thắc mắc hay góp ý comment bên dưới nhé.

0

0

Phiếu bình chọn

Xếp hạng bài viết