Thuật Toán Sắp Xếp Chọn Trực Tiếp (Selection Sort) - Góc Học IT

Trang chủ » độ Phức Tạp Của Selection Sort » Thuật Toán Sắp Xếp Chọn Trực Tiếp (Selection Sort) - Góc Học IT

Có thể bạn quan tâm

1. Ý tưởng thuật toán sắp xếp chọn trực tiếp

Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1.

Chọn phần tử nhỏ nhất trong n phần tử của danh sách ban đầu. Tìm và đổi vị trí phần tử nhỏ nhất với phần tử đầu tiên trong danh sách. Lúc này, phần tử a0 sẽ có giá trị nhỏ nhất trong danh sách.

Sau đó, xem danh sách cần sắp xếp hiện tại chỉ gồm n-1 phần tử, bắt đầu từ phần tử thứ 2 trong danh sách ban đầu. Tức là danh sách hiện tại chỉ gồm a1, a2,…,an-1.

Lặp lại quá trình trên cho danh sách hiện tại đến khi danh sách hiện tại chỉ còn 1 phần tử.

2. Các bước thực hiện thuật toán

Bước 1: i = 0;

Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n-1].

Bước 3: Đổi chỗ a[min] và a[i].

Bước 4: Nếu i < n-1 thì gán i = i+1; rồi lặp lại bước 2, ngược lại -> Dừng.

Minh họa thuật toán sắp xếp chọn trực tiếp

Mảng a gồm các phần tử cần sắp xếp với phần tử đầu tiên a[i]=20 (i=0).

Mảng cần sắp xếp

So sánh các phần tử trong mảng a để tìm phần tử nhỏ nhất a[min]=2 với min=4.

Tìm phần tử min trong mảng

Đổi chổ a[min]=2 với a[i]=20 (i=0).

Đổi chổ phần tử min với phần tử đầu tiên trong mảng đang xét

Lặp lại các bước trên cho đến khi tất cả các phần tử trong mảng được sắp xếp xong (i = n-1). Lưu ý, sau mỗi lần lặp, giá trị của i tăng lên 1 (i=i+1), a[i] sẽ là phần tử đầu tiên cần đổi chổ với a[min].

Lần lặp với i=0
Lần lặp với i=0
Lần lặp với i=1
Lần lặp với i=1
Lần lặp với i=2
Lần lặp với i=2
Lần lặp với i=3
Lần lặp với i=3

3. Cài đặt thuật toán sắp xếp chọn trực tiếp với C++

void Selection_Sort(int a[], int n){ int min;//vị trí phần tử nhỏ nhất trong dãy hiện hành for(int i=0; i<n-1; i++){ min = i; for(int j=i+1; j<n; j++){ if (a[j] < a[min]){ min = j;//ghi nhận vị trí phần tử nhỏ nhất } } swap(a[min], a[i]); } } void main() { int a[5] = {8, 4, 1, 6, 5}; Selection_Sort(a, 5); cout<<"Mang sau khi sap xep:"<<endl; for(int i=0;i<5;i++){ cout<<a[i]<<" "; } system("pause"); }
Kết quả
Mang sau khi sap xep: 1 4 5 6 8

Đánh giá giải thuật

Số phép so sánh trong trường hợp tốt nhất hoặc xấu nhất đều là n(n-1)/2. Độ phức tạp thuật toán là O(n2).

  • Các lệnh gán và nhập xuất cơ bản trong C++
  • Xây dựng danh sách liên kết kép (Doubly Linked List) với con trỏ (pointer)
  • Đếm số chữ số của một số nguyên dương trong C++
  • Sử dụng static class và anonymous class trong Java
  • Cách tạo mảng (array) và thao tác với mảng trong PHP
5/5 - (1 bình chọn)Bài trước và bài sau trong môn học<< Thuật toán sắp xếp đổi chổ trực tiếp (Interchange Sort)Thuật toán sắp xếp nổi bọt (Bubble Sort) >>

Từ khóa » độ Phức Tạp Của Selection Sort