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

Trang chủ » Cách Làm Sắp Xếp Chọn » Thuật Toán Sắp Xếp Chọn Trực Tiếp (Selection Sort)

Có thể bạn quan tâm

Sign in Sign in Welcome!Log into your account your username your password Forgot your password? Password recovery Recover your password your email Search Thursday, December 18, 2025
  • Sign in / Join
Sign in Welcome! Log into your account your username your password Forgot your password? Get help Password recovery Recover your password your email A password will be e-mailed to you. sinhvientot.net sinhvientot.net sinhvientot.net sinhvientot.net Home Lập trình C/C++ Thuật toán sắp xếp chọn trực tiếp (Selection Sort) Facebook Twitter Pinterest WhatsApp

Như đã trình bày ở giải thuật Interchange Sort thì có rất nhiều các giải thuật về bài toán sắp xếp nhưng giải thuật nào mang lại tính hiệu quả cao cho công việc cũng như dễ hiểu cho bạn đọc thì hôm nay chúng ta sẽ cùng tìm hiểu thêm về một giải thuật nữa mang tên là chọn trực tiếp hay còn gọi là Selection Sort.

Ý tưởng

Ý tưởng chính của thuật toán là xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét thì dừng giải thuật.

Giải thuật

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]

Bước 3:

Dùng hàm swap để đổi chỗ a[i] và a[min]

Bước 4:

Nếu i < n – 1 thì

i = i + 1;

Lặp lại bước 2;

Ngược lại: Dừng

Ví dụ: Cho dãy A gồm 4 phần tử 10, 5, 14, 9. Hãy dùng giải thuật sắp xếp Selection Sort để minh họa.

Đầu tiên i=0. a0 = 10. Gán cho 10 là giá trị nhỏ nhất.

Chạy từ a1 đến a3 xét thấy a1 là phần tử nhỏ nhất ( min) nên đổi chỗ giữa a0 và a1.

Dãy mới: 5, 10, 14, 9.

Do đã tìm được phần tử nhỏ nhất của mảng đưa ra đầu mảng nên sẽ tăng i lên 1 đơn vị:

i=i+1=1. a1= 10.

Chạy từ a1 đến a3 xét thấy a3=9 là phần tử nhỏ nhất nên tiến hành đổi chỗ giữa a1 và a3.

Dãy mới: 5, 9, 14 , 10.

Tương tự từ a1 đến a3 không còn phần từ nào nhỏ hơn 9 nên i sẽ tăng lên 1 đơn vị:

i=i+1=2. a2=14.

Chạy từ a2 đến a3 xét thấy a3=10 là phần tử nhỏ nhất nên tiến hành đổi chỗ giữa a2 và a3.

Dãy mới: 5, 9, 10, 14.

Sau đó tăng i lên 1 đơn vị:

i=i+1=3. Do không thỏa i<n-1 nên chúng ta dừng giải thuật ở đây và nhận được dãy đã sắp xếp là:

5, 9, 10, 14.

Code C/C++

Hàm sắp xếp theo thuật toán Selection Sort:

void Sapxep(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n; j++) if (a[min]>a[j]) min = j; swap(a[i], a[min]); } }

Hàm đổi chỗ 2 phần tử ( Swap ): 

void swap(int &a, int &b) { int x = a; a = b; b = x; }

Hàm main:

void main() { int A[100]; NhapMang(A, N); Sapxep(A, N); printf("Mang sau khi sap xep la: "); XuatMang(A, N); getch(); }

Trước khi chạy hàm main các bạn phải có hàm nhập và xuất mảng 1 chiều. Các bạn có thể xem tại đây.

Kết quả:

SO PHAN TU:

6

Phan tu thu 0: 7

Phan tu thu 1: 11

Phan tu thu 2: 1

Phan tu thu 3: 4

Phan tu thu 4: 6

Phan tu thu 5: 0

Noi dung cua mang la:     7   11    1    4    6    0

Mang sau khi sap xep la:      0   1    4    6    7    11

Trên đây là một trong những thuật toán sắp xếp của bài toán C/C++. Selection Sort là một thuật toán giải quyết bài toán sắp xếp, còn rất nhiều các giải thuật sắp xếp khác mà chúng tôi sẽ gửi đến các bạn ở các ở các bài viết sau. Xem thêm Thuật toán sắp xếp nổi bọt (BubbleSort)

Chúc các bạn thành công.

RELATED ARTICLESMORE FROM AUTHOR

C/C++

Sự khác nhau giữa Inline function và Macro trong C

C/C++

Trong ngôn ngữ C/C++ có bao nhiêu vùng nhớ (Memory layout)

C/C++

Cấu trúc dữ liệu danh sách nhân viên

C/C++

Tổng quan File trong C

C/C++

Cấu trúc kiểu dữ liệu sinh viên

C/C++

Cấu trúc mô tả một điểm trên tọa độ xOy

1 COMMENT

  1. void Sapxep(int a[], int n) { for (int i = 0; i < n – 1; i++) { int min = i; for (int j = i + 1; j a[j]) min = j; swap(a[i], a[min]); } }

    Hàm Sapxep của bạn viết sai rồi Theo mình thì phải sửa lại như bên dưới: void Sapxep(int a[], int n) { for (int i = 0; i < n – 1; i++) { int min = a[i]; for (int j = i + 1; j a[j]) min = a[j]; swap(min, a[j]); } }

    Log in to leave a comment

LEAVE A REPLY Cancel reply

Log in to leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Danh sách các bài học

Các kiểu dữ liệu cơ bản trong ngôn ngữ C/C++

Mr Good - April 16, 2016 0

Hướng dẫn Tạo Project Visual C++ trong Visual Studio 2012

April 16, 2016

Biến-Hằng-Câu lệnh và biểu thức trong C/C++

April 16, 2016

Cấu trúc IF-ELSE

April 16, 2016

Cấu trúc switch – case

April 16, 2016

Vòng lặp For

April 16, 2016

Cấu trúc While, Do-while

April 16, 2016

Cách sử dụng hàm trong lập trình

April 16, 2016

Mảng một chiều

April 16, 2016 Load more

Bài viết mới nhất

Download

Download Cisco Packet Tracer

Windows 10

Hướng dẫn cài đặt webserver trên localhost để chạy wordpress

HPE

Hướng dẫn cấu hình IP ILO máy chủ HP DL380 Gen10

CentOS

CentOS 8 – Giới thiệu về hệ điều hành Linux (P1)

Load more © Copyright 2016, All Rights Reserved. Donations are always appreciated! MEW: 0x296f1a39d5Ca3cb83C76724eA38af3B90B90109D MORE STORIES

Một số vấn đề thường gặp khi triển khai hệ thống Wifi cho nhiều...

Trần Ngọc Quốc Phong - November 4, 2016 0

Phương pháp học tập hiệu quả học phần ngôn ngữ lập trình

Vũ Văn Vinh - June 26, 2016 0

Từ khóa » Cách Làm Sắp Xếp Chọn