Tìm hiểu giải thuật sắp xếp Selection Sort

Sharing is caring!

Gần đây, trong công việc có một số bài toán cần sử dụng giải thuật sắp xếp (sorting). Cũng đã lâu lắm rồi tui đã không sử dụng các thuật toán sắp xếp này nữa, nhân dịp này tui sẽ viết một bài để giới thiệu 2 cái giải thuật sắp xếp đơn giản, dễ hiểu nhất đó là Selection Sort và Bubble Sort. Trong bài này tui sẽ viết cho Selection Sort trước.

Tuy rằng trong các ngôn ngữ hiện giờ như C#, Java, PHP… đều hỗ trợ các hàm dùng để sắp xếp một array hay một collection tăng dần hay giảm dần, bạn chỉ cần truyền vào điều kiện cần sort là nó sẽ sort cho bạn luôn. Nhưng cũng có một số trường hợp bạn cần phải viết lại hàm sort đó thì sao? Bỏ qua yếu tố sắp xếp nhanh hay chậm, ở đây tui muốn các bạn hiểu được thế nào là sắp xếp một array hay một collection, giúp bạn có trải nghiệm tốt hơn về kỹ thuật lập trình. Vậy chúng ta bắt đầu nha.

1. Selection Sort:

Có thể nói đây là giải thuật sắp xếp đơn giản nhất bởi vì ý tưởng của nó rất là đơn giản luôn. Cứ đi tìm thằng nào nhỏ nhất(tăng dần) hoặc lớn nhất(giảm dần), bóc nó bỏ lên phía đầu array hoặc collection là xong.

Ý tưởng như sau:

Với phần tử đầu tiên của array, ta tìm xem coi có thằng nào trong số còn lại mà nhỏ hơn phần tử đầu tiên và phải nhỏ nhất. Sau đó hoán vị phần tử nhỏ nhất này với phần tử đầu tiên. Cứ như vậy với phần tử thứ 2, thứ 3…. Cho đến hết array.

Đọc ý tưởng thấy có vẻ hơi đơ đơ nhỉ. Thôi thì xem ví dụ tui chạy bằng tay, các bạn “cố gắng” hiểu nha. Ở đây tui sử dụng array và sắp xếp array này tang dần để làm ví dụ cho nó dễ hình dung nha. Happy-Grin

Ví dụ:

Tui có một array gồm 8 phần tử(chỉ số đi từ 0-7) như sau:

selection_sort_00

màu xanh dương: phần tử của array đã được sắp xếp.

màu đỏ: là phần tử có giá trị nhỏ nhất

màu tím: là phần tử được neo để hoán vị với phần tử nhỏ nhất

Bước 1:

Tui giữ phần tử thứ 0 có giá trị là 30, sau đó tìm trong các phần tử còn lại thì thấy phần tử thứ 1 có giá trị là 10 và là nhỏ nhất. Sau đó ta hoán vị chúng selection_sort_01_1

Sau khi hoán vị, phần tử 1 có giá trị 10 sẽ nằm ở vị trí đầu tiên

selection_sort_01_2

Bước 2:

Tui tiếp tục với phần tử thứ 1 có giá trị là 30 và neo nó tiếp. Sau đó tìm phần tử có giá trị nhỏ nhất tính từ phần tử màu tím (phần  tử được neo) thì thấy phần tử thứ 5 có giá trị 14 là nhỏ nhất

selection_sort_02_1

Sau khi hoán vị thì ta được như sau, lúc này phía đầu array, 2 giá trị 10 và 14 đã được sắp xếp:

selection_sort_02_2

Bước 3:

Tui lại neo phần tử thứ 2 lúc này là 70. và tìm trong các phần tử còn lại thì thấy phần tử thứ 3 có giá trị nhỏ nhất là 25. selection_sort_03_1

Hoán vị 70 với 25 thì ta được như sau:

selection_sort_03_2

Bước 4:

Neo phần tử thứ 3 có giá trị 70. Phần tử nhỏ nhất là phần tử thứ 5 có giá trị 30

selection_sort_04_1

Lại tiếp tục hoán vị hai đứa nó, ta được:

selection_sort_04_2

Cứ tiếp tục như vậy với các phần tử còn lại (màu đen)

Bước 5:

Hoán vị 90 với 49.

selection_sort_05_1

selection_sort_05_2

Bước 6:

Hoán vị 70 với 65.

selection_sort_06_1

selection_sort_06_2

Bước 7:

Hoán vị 90 với 70.

selection_sort_07_1

selection_sort_07_2

Vậy là qua 7 bước chạy bằng tay, tui đã có được một array với thứ tự được sắp xếp tăng dần. Hy vọng là các bạn hiểu được cách hoạt động của giải thuật này. Tired

Ở trên là ví dụ cùng hình ảnh minh họa để các bạn hiểu cái giải thuật nó hoạt động như thế nào. Bây giờ tui sẽ cài đặt thuật toán này bằng C# và PHP cho các bạn tham khảo. Bắt đầu nha.

2. Cài đặt thuật toán Selection Sort:

Với ví dụ trên, các bạn thấy, cứ qua một bước ta phải duyệt cái array tính từ vị trí neo để tìm cái phần tử nhỏ nhất, và ta lập lại điều này cho đến phần tử cuối cùng. Do đó, ta cần 2 vòng lặp for:

  1. vòng for i cho duyệt qua các phần tử để neo
  2. vòng for j cho việc tìm trong số các phần tử còn lại tính từ vị trí của phần tử được neo để tìm phần tử có giá trị nhỏ nhất, và vòng for j được lồng vào trong vòng for i.

Code snippet for C#:

Hàm swap hai phần tử:

Vòng lặp for i, ta chỉ cần i chạy đến phần tử kế cuối thôi, và vòng for j chạy đến phần tử cuối cùng để khi đó nếu phần tử kế cuối lớn hơn phần tử cuối cùng thì nó sẽ swap (giống như ở bước 7).

Khi vòng lặp for i bắt đầu chạy, tui set giá trị cho biến minValueIndexi, lý do là tui sẽ tìm thằng có giá trị nhỏ nhất tính từ vị trí neo thứ i luôn.

Với vòng lặp for j, tui cho j chạy từ vị trí kế tiếp i, có nghĩa j = i + 1 để mà so sánh. Cứ như vậy tui so sánh đến cuối array, nếu có phần tử thứ j nào nhỏ hơn phần tử neo i (lúc này là minValueIndex = i) thì tui gán giá trị lại cho minValueIndex j (điều kiện là a[j] < a[minValueIndex]). Khi chạy đến hết array nếu minValueIndex có giá trị khác ban đầu thì phần tử thứ j này có giá trị nhỏ nhất.

Sau đó kiểm tra nếu (minValueIndex != i) thì tui sẽ swap phân tử a[i] với a[minValueIndex]. Thấy hơi rối rối rồi nhé Afraid

Full Code for C#:

Code snippet for PHP:

Hy vọng qua bài viết về giải thuật sắp xếp Selection Sort này sẽ giúp các bạn hiểu và vận dụng tốt vòng lặp for cũng như hiểu được ý tưởng của giải thuật này. Cũng khá thú vị đấy chứ nhỉ! THANK-YOU

Sharing is caring!

Làm quen với lập trình
Tìm hiểu giải thuật sắp xếp Bubble Sort

Vincent Le

Tui là Lê Minh Đạt, tên tiếng anh là Vincent(do thích nhân vật Vincent Valentine, ai từng là fan của trò Final Fantasy VII thì sẽ biết nhân vật này, hehe). Đang tập tành làm một blogger viết về mảng lập trình, mong muốn được chia sẻ những gì đã học được, tích góp được trong 10 năm đi làm thợ code.

shares