Nội dung chính
Bài tập Java - Sắp xếp chọn (Selection Sort) trong Java
Đề bài: Viết chương trình Java sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán chọn (Selection Sort).
Lời giải
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.
Dưới đây là chương trình Java để giải bài sắp xếp chọn (Selection Sort) trong Java:
package vn.viettuts.array; public class SapXepChon { public void selectionSort(int arr[]) { int indexMin, i, j; // lap qua ta ca cac so for (i = 0; i < arr.length - 1; i++) { // thiet lap phan tu hien tai la min indexMin = i; // kiem tra phan tu hien tai co phai la nho nhat khong for (j = i + 1; j < arr.length; j++) { if (arr[j] < arr[indexMin]) { indexMin = j; } } if (indexMin != i) { System.out.println(" ==> Trao doi phan tu: [" + arr[i] + ", " + arr[indexMin] + "]"); // Trao doi cac so int temp = arr[indexMin]; arr[indexMin] = arr[i]; arr[i] = temp; } System.out.println("Vong lap thu " + (i + 1)); display(arr); } } public void display(int arr[]) { int i; System.out.print("["); // Duyet qua tat ca phan tu for (i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.print("]\n"); } public static void main(String[] args) { // khoi tao mang arr int arr[] = { 6, 7, 0, 2, 8, 1, 3, 9, 4, 5 }; SapXepChon sapXepChon = new SapXepChon(); System.out.println("Mang du lieu dau vao: "); sapXepChon.display(arr); System.out.println("-----------------------------"); sapXepChon.selectionSort(arr); System.out.println("-----------------------------"); System.out.println("\nMang sau khi da sap xep: "); sapXepChon.display(arr); } }
Chạy chương trình Java trên cho kết quả như sau: