Thứ Tư, 30 Tháng Mười Một 2022
Trang chủLập trìnhCTDL & Thuật toánThuật toán sắp xếp chọn(Selection Sort)

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)
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

Minh hóa ví dụ thuật toán sắp xếp chọn

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
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x