Sắp xếp chọn (Selection Sort) trong Java: Hướng dẫn cách làm

Sắp xếp chọn (Selection Sort) Java tìm mục nhỏ nhất trong danh sách và di chuyển giá trị đó đến đầu danh sách. Điều này xảy ra lặp lại cho đến khi mọi phần tử danh sách đầu tiên đã được sắp xếp. Selection sort trả về danh sách đã sắp xếp.

Làm sao sắp xếp danh sách trong Java? Bạn có vài lựa chọn. Một lựa chọn phổ biến là selection sort.

Trong hướng dẫn này, chúng ta sẽ nói về selection sort là gì và cách hoạt động. Chúng ta cũng đi qua cách xây dựng selection sort trong Java để bạn biết xây dựng của riêng mình. Hãy bắt đầu!

Selection Sort trong Java là gì?

Selection sort lặp lại tìm mục nhỏ nhất (minimum item) trong danh sách và di chuyển nó đến đầu các mục chưa sắp xếp trong danh sách. Quá trình này lặp lại cho mọi mục danh sách cho đến khi danh sách được sắp xếp.

Mục đầu tiên trong danh sách coi là mục nhỏ nhất. Mục này so sánh với phần tử tiếp theo. Nếu phần tử tiếp theo nhỏ hơn, các phần tử hoán đổi. Thuật toán tìm phần tử nhỏ nhất cho đến khi đến phần tử cuối. Sau đó, chương trình di chuyển mục nhỏ nhất đến đầu danh sách.

Trong selection sort, danh sách chứa hai phần: danh sách đã sắp xếp (sorted list) và danh sách chưa sắp xếp (unsorted list). Khi phần tử được sắp xếp, chúng di chuyển từ mảng con chưa sắp xếp sang mảng con đã sắp xếp.

Bạn có thể sắp xếp danh sách theo thứ tự tăng dần hoặc giảm dần.

Khi nào nên dùng Selection Sort?

Selection sort tối ưu khi cần sắp xếp danh sách nhỏ. Điều này vì có cách hiệu quả hơn sắp xếp danh sách lớn. Thuật toán như merge sort, insertion sort, và quick sort hiệu quả hơn selection sort trong lập trình Java.

Selection sort hoạt động tốt nhất khi kiểm tra tất cả phần tử mảng là bắt buộc. Trường hợp này nếu vài hoặc không mục nào trong danh sách được sắp xếp. Selection sort thường vượt trội bubble sort, dễ hiểu hơn.

Selection Sort hoạt động như thế nào?

Không ích thử triển khai thuật toán Java mà không biết trước muốn thuật toán làm gì. Hãy bắt đầu đi qua các bước selection sort sắp xếp danh sách theo thứ tự.

Xem mảng chưa sắp xếp sau:

Selection sort đặt mục đầu tiên là nhỏ nhất trong danh sách. Đây là giá trị tạm thời thay đổi mỗi khi chương trình so sánh. Giá trị này lưu trong biến riêng.

Mục "minimum" so sánh với phần tử thứ hai. Phần tử này ở phần chưa sắp xếp mảng; mọi phần tử sau phần tử đã sắp xếp là chưa sắp xếp.

Giả sử phần tử thứ hai nhỏ hơn "minimum". Trong trường hợp này, giá trị "minimum" đặt thành giá trị phần tử thứ hai. 14 nhỏ hơn 17, nên giá trị minimum mới thành 14.

Quá trình lặp lại cho mỗi mục danh sách. 9 nhỏ hơn 14. Vì vậy, giá trị "minimum" thành 9. 9 không nhỏ hơn 12, nên giá trị minimum giữ nguyên.

Sau một lần lặp, danh sách tìm thấy 9 là số nhỏ nhất. Mục này di chuyển đến đầu danh sách:

Quá trình bắt đầu lại từ phần tử chưa sắp xếp đầu tiên. Vì vậy, bộ so sánh tiếp theo bắt đầu từ 17:

• 17 bằng minimum.
• Chương trình so sánh 17 với 14. Giá trị "minimum" thành 14.
• Chương trình so sánh 14 với 12. Giá trị "minimum" thành 12.
• Chương trình di chuyển 12 đến cuối các mục đã sắp xếp trong danh sách.

Danh sách trông như sau:

Quá trình lặp lại cho đến khi danh sách sắp xếp. Khi thuật toán hoàn thành, danh sách sau trả về:

Danh sách đã sắp xếp theo thứ tự tăng dần.

Cách xây dựng Selection Sort trong Java

Biết selection sort hoạt động như thế nào là một chuyện; xây dựng nó là chuyện khác. Hãy viết selection sort Java dùng logic thảo luận trong phần đi qua.

Thiết lập chương trình (Set Up the Program)

Tạo file selection_sort.java. Chúng ta bắt đầu bằng import thư viện Java Arrays vào mã:

import java.util.Arrays;

Chúng ta dùng thư viện này sau trong mã. Dùng để chuyển mảng đã sắp xếp thành chuỗi để in ra console.

Tạo hàm sắp xếp (Create a Sort Function)

Tiếp, khai báo lớp và tạo phương thức thực hiện selection sort. Thêm sau vào file selection_sort.java:

class SelectionSort { void sortNumbers(int array[]) { int size = array.length; for (int item = 0; item < size - 1; item++) { int minimum = item; for (int number = minimum + 1; number < size; number++) { if (array[number] < array[minimum]) { minimum = number; } } int temporary = array[item]; array[item] = array[minimum]; array[minimum] = temporary; } } } 

Trong lớp, định nghĩa phương thức sortNumbers thực hiện sắp xếp. Bắt đầu bằng tính độ dài mảng. Lưu độ dài mảng trong biến Java.

Sau đó, tạo vòng lặp for Java. Vòng lặp lặp qua mọi mục danh sách. Bên trong for này, tìm mục minimum, là mục đầu tiên danh sách.

Chúng ta bắt đầu vòng lặp for khác so sánh mục minimum với mọi mục danh sách.

Nếu số vòng lặp đọc nhỏ hơn số minimum, giá trị "minimum" thành số đó. Trong vòng lặp, "number" đại diện giá trị chỉ mục số so sánh với giá trị minimum.

Khi số minimum đã so sánh với mọi số danh sách, vòng lặp for bên trong dừng. Số minimum sau đó di chuyển sau tất cả số đã sắp xếp trong danh sách.

Gọi hàm sắp xếp (Call the Sort Function)

Mã chưa làm gì. Chúng ta chưa gọi lớp và cho nó danh sách sắp xếp.

Dưới phương thức sortNumbers trong danh sách, thêm mã sau:

public static void main(String args[]) { int[] toSort = { 17, 14, 9, 12 }; SelectionSort newSort = new SelectionSort(); newSort.sortNumbers(toSort); System.out.println(Arrays.toString(toSort)); } 

Bên trong phương thức main khai báo danh sách mục sắp xếp tên toSort. Khởi tạo thể hiện SelectionSort tên newSort. Dùng để gọi phương thức sortNumbers, sắp xếp giá trị mảng toSort.

Sau phương thức sortNumbers thực thi, in mảng đã sắp xếp ra console. Làm bằng phương thức Arrays.toString(), chuyển mảng thành danh sách chuỗi.

Chạy mã:

[9, 12, 14, 17]

Danh sách đã sắp xếp!

Selection Sort Java: Sắp xếp giá trị theo thứ tự giảm dần

Có giá trị sắp xếp thứ tự giảm dần. Để làm vậy, thay dòng mã sau trong phương thức sortNumbers:

if (array[number] < array[minimum]) {

Với mã này:

if (array[number] > array[minimum]) {

Mã này kiểm tra xem giá trị "minimum" có lớn hơn giá trị truy cập bởi vòng lặp for không. Nghĩa là giá trị "minimum" sẽ phản ánh giá trị cao nhất danh sách thay vì thấp nhất.

Để tránh nhầm lẫn, nên đổi tên "minimum" thành "maximum", nếu sắp xếp danh sách thứ tự giảm dần.

Bạn đã làm. Bạn đã sắp xếp danh sách Java dùng thuật toán selection sort.

Độ phức tạp Selection Sort Java là gì?

Có ba độ phức tạp thời gian cần xem khi đánh giá thuật toán: trường hợp tốt, xấu, và trung bình.

Selection sort có độ phức tạp tốt, trung bình, và xấu O(n^2). Nghĩa là thuật toán sẽ mất thời gian tăng theo mũ khi số mục danh sách tăng.

Bạn bối rối độ phức tạp thuật toán? Xem series hai phần Big O Notation. Đó là ký hiệu dùng mô tả độ phức tạp thuật toán.

Kết luận

Selection sort là phương pháp hiệu quả sắp xếp danh sách dữ liệu. Chúng hoạt động bằng chọn mục nhỏ nhất từ danh sách chưa sắp xếp và di chuyển mục đó đến đầu danh sách chưa sắp xếp. Quá trình lặp lại cho đến khi danh sách sắp xếp.

Bạn muốn thành lập trình viên Java? Xem hướng dẫn How to Learn Java. Bạn tìm thấy mẹo học hàng đầu và lời khóa khóa học trực tuyến tốt nhất và tài nguyên học tập trong hướng dẫn.