Advertisement
Trong kiến thức lập trình nói chung và cấu trúc dữ liệu nói riêng thì các thuật toán sắp xếp chiếm một vai trò vô cùng quan trọng. Một trong đó là thuật toán Selection Sort hay còn được gọi là giải thuật sắp xếp chọn. Bài viết này mình sẽ hướng dẫn chi tiết về cách sử dụng giải thuật trên và code minh họa bằng ngôn ngữ lập trình C.
Phương pháp sắp xếp Selection Sort là gì?
Giải thuật sắp xếp chọn là một thuật toán sắp xếp đơn giản. Thuật toán sắp xếp này là một thuật toán dựa trên so sánh tại chỗ, trong đó danh sách được chia thành hai phần, phần được sắp xếp ở đầu bên trái và phần chưa được sắp xếp ở đầu bên phải. Ban đầu, phần được sắp xếp trống và phần chưa sắp xếp là toàn bộ danh sách.
Phần tử nhỏ nhất được chọn từ mảng chưa sắp xếp và hoán đổi với phần tử ngoài cùng bên trái và phần tử đó trở thành một phần của mảng được sắp xếp. Quá trình này tiếp tục di chuyển qua lại mảng chưa được sắp xếp bởi một phần tử sang phải.
Thuật toán này không phù hợp với các tập dữ liệu lớn vì độ phức tạp trung bình. Khi bạn sắp xếp với một cơ sở dữ liệu lớn thì quá trình này sẽ chậm và tốn nhiều bộ nhớ máy tính.
Giải thuật sắp xếp Selection Sort
Bước 1: Chọn phần tử có khóa nhỏ nhất trong n phần tử từ a[0] đến a[n-1] và hoán vị nó với phần tử a[0].
Bước 2: Chọn phần tử có khóa nhỏ nhất trong n – 1 phần tử từ a[1] đến a[n-1] và hoán vị nó với a[1].
Tổng quát ở bước thứ i chọn phần tử có khóa nhỏ nhất trong n – i phần tử từ a[i] đến a[n-1] và hoán vị nó với a[i].
Sau n – 1 bước thì mảng đã được sắp xếp.
Phương pháp chọn khóa hoặc phần tử đầu tiên
Bước 1: Đầu tiên ta đặt khóa nhỏ nhất là khóa của a[i] (lowkey = a[i]key) và chỉ số của phần tử có khóa nhỏ nhất là là i (lowindex = i).
Bước 2: Xét các phần tử a[j] với j từ i + 1 đến n -1, nếu khóa của a[j] nhỏ hơn khóa nhỏ nhất (a[j].key < lowkey) thì đặt lại khóa nhỏ nhất là là khóa của a[j] (lowkey = a[j].key). Và phần tử có khóa nhỏ nhất là j (lowendex = j).
Bước 3: Khi đã xét hết các phần tử a[j] với j > n- 1 thì phần tử có khóa nhỏ nhất là a[lowindex].
Phương pháp sắp xếp bằng ví dụ minh họa
Cho một dãy số gồm: 5, 6, 2, 10, 32, 1. Ta sẽ áp dụng thuật toán Selection Sort để sắp xếp lại mảng số nguyên trên theo thứ tự tăng dần.
Lưu đồ thuật toán Selection Sort
Để giúp các bạn hiểu rõ hơn về cách viết chương trình sắp xếp selection sort này, mình có vẽ một lưu đồ thuật toán chi tiết. Các bạn có thể xem và hiểu rõ hơn cách xây dựng một chương trình đơn giản nha.
Mã code minh họa thuật giải Selection Sort
Mình sẽ sử dụng ngôn ngữ lập trình C để minh họa phương pháp sắp xếp Selection Sort.
Void Selectionsort(void)
{
int i, j, lowindex;
keytype lowkey;
for(int i = 0; i< n-2; i++)
lowindex = i;
lowkey = a[i].key;
for(int j = i +1; j < n - 1; j++)
if(a[j].key < lowkey){
lowkey = a[j].key;
lowindex = j; }
Swap(&a[i], &a[lowindex)
}
Hàm Swap có nội dụng như sau:
void Swap( int a, int b)
{
int temp = a;
a = b; b = temp;
}
Với những chia sẽ trên, mình mong rằng các bạn sẽ hiểu rõ hơn về thuật toán sắp xếp Selection Sort này. Và các bạn nên nhớ cần tư duy để tìm ra các phương pháp lập trình theo ý mình sẽ mang lại hiệu quả cao hơn.
Advertisement
