Selection sort là thuật toán gì
|
Selection sort được dùng khá phổ biến trong ngôn ngữ lập trình C/C++. Bài viết này sẽ giúp bạn hiểu rõ hơn về Selection sort một cách đơn giản và dễ hiểu nhất nhé Show Nội dung bài viết
Sắp xếp chọn – Selection sort là gì?Khái niệmSelection sort còn được gọi là thuật toán sắp xếp chọn. Thuật toán này sẽ giúp so sánh các phần tử trong mảng với nhau để tìm các phần tử có giá trị nhỏ nhất hoặc lớn nhất (tùy theo thứ tự sắp xếp). Sau đó đẩy các giá trị ấy về phía đầu của mảng để tạo thành một dãy số sắp xếp theo thứ tự hoàn chỉnh. Ý tưởngÝ tưởng thuật toán sắp xếp chọn dưới đây sẽ sắp xếp mảng theo thứ tự từ bé đến lớn (tăng dần). Bạn có thể thực hiện tương tự cho trường hợp sắp xếp từ lớn đến bé (giảm dần). Với thuật toán sắp xếp, ta chia mảng thành các phần sau:
Quá trình sắp xếp diễn ra như sau:
Giải thuậtBước 1: Chạy vòng lặp for (i = 0; i < n-1; i++) để di chuyển ranh giới của mảng đã sắp xếp và chưa sắp xếp. Bước 2: Chạy vòng lặp for (j = i+1; j < n; j++) để tìm số nhỏ nhất a[min] trong dãy số chưa sắp xếp. Bước 3: Hoán vị a[min] và a[i]. Bước 4: Liên tục lặp lại 3 bước trên cho đến khi sắp xếp dãy theo thứ tự đúng thì ngừng. Thuật toán sắp xếp chọn Selection sortCode minh họaCode: Thuật toán sắp xếp chọn selection sort Gợi ý:
Hy vọng bài viết này sẽ giúp bạn làm chủ được Selection sort để ứng dụng vào công việc một cách hiệu quả nhất nhé. Chúc các bạn thực hiện thành công! Giải thuật sắp xếp chọn (Selection Sort) là gì ? Giải thuật sắp xếp chọn (Selection Sort) là một giải thuật đơn giản. Giải thuật sắp xếp này là một giải thuật dựa trên việc so sánh in-place, trong đó danh sách được chia thành hai phần, phần được sắp xếp (sorted list) ở bên trái và phần chưa được sắp xếp (unsorted list) ở bên phải. Ban đầu, phần được sắp xếp là trống và phần chưa được sắp xếp là toàn bộ danh sách ban đầu. Phần tử nhỏ nhất được lựa chọn từ mảng chưa được sắp xếp và được tráo đổi với phần bên trái nhất và phần tử đó trở thành phần tử của mảng được sắp xếp. Tiến trình này tiếp tục cho tới khi toàn bộ từng phần tử trong mảng chưa được sắp xếp đều được di chuyển sang mảng đã được sắp xếp. Giải thuật này không phù hợp với tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là O(n2) với n là số phần tử. Bạn tìm hiểu khái niệm in-place trong chương: Một số khái niệm cơ bản về giải thuật sắp xếp. Cách giải thuật sắp xếp chọn (Selection Sort) làm việcDưới đây là các hình minh họa cho cách giải thuật sắp xếp chọn làm việc. Giả sử chúng ta có một mảng như sau: Từ vị trí đầu tiên trong danh sách đã được sắp xếp, toàn bộ danh sách được duyệt một cách liên tục. Vị trí đầu tiên có giá trị 14, chúng ta tìm toàn bộ danh sách và thấy rằng 10 là giá trị nhỏ nhất. Do đó, chúng ta thay thế 14 với 10. Sau một vòng lặp, giá trị 10 thay thế cho giá trị 14 tại vị trí đầu tiên trong danh sách đã được sắp xếp. Chúng ta tráo đổi hai giá trị này. Tại vị trí thứ hai, giá trị 33, chúng ta tiếp tục quét phần còn lại của danh sách theo thứ tự từng phần tử. Chúng ta thấy rằng 14 là giá trị nhỏ nhất thứ hai trong danh sách và nó nên xuất hiện ở vị trí thứ hai. Chúng ta tráo đổi hai giá trị này. Sau hai vòng lặp, hai giá trị nhỏ nhất đã được đặt tại phần đầu của danh sách đã được sắp xếp. Tiến trình tương tự sẽ được áp dụng cho phần còn lại của danh sách. Các hình dưới minh họa cho các tiến trình này. Tiếp theo chúng ta sẽ theo dõi một số khía cạnh khác của giải thuật sắp xếp chọn. Giải thuật cho sắp xếp chọn (Selection Sort)Bước 1: Thiết lập MIN về vị trí 0 Bước 2: Tìm kiếm phần tử nhỏ nhất trong danh sách Bước 3: Tráo đổi với giá trị tại vị trí MIN Bước 4: Tăng MIN để trỏ tới phần tử tiếp theo Bước 5: Lặp lại cho tới khi toàn bộ danh sách đã được sắp xếp Giải thuật mẫu cho sắp xếp chọnBắt đầu giải thuật sắp xếp chọn (Selection Sort)
list : mảng các phần tử
n : kích cỡ mảng
for i = 1 tới n - 1
/* thiết lập phần tử hiện tại là min*/
min = i
/* kiểm tra phần tử có là nhỏ nhất không */
for j = i+1 tới n
if list[j] < list[min] thì
min = j;
kết thúc if
kết thúc for
/* tráo đổi phần tử nhỏ nhất với phần tử hiện tại*/
if indexMin != i then
tráo đổi list[min] và list[i]
kết thúc if
kết thúc for
Kết thúc giải thuật
Để theo dõi code đầy đủ của giải thuật sắp xếp chọn trong ngôn ngữ C, mời bạn click chuột vào chương: Giải thuật sắp xếp chọn (Selection Sort) trong C. Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.  Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi. |
