Bài tập về các thuật toán sắp xếp trong Java có lời giải
Để củng cố lại kiến thức về thuật toán sắp xếp, eLib giới thiệu đến bạn một số bài tập về các thuật toán sắp xếp cơ bản. Bạn có thể tham khảo các bài học trước để thực hành lại. Cùng thử nhé!
Mục lục nội dung
1. Sắp xếp nổi bọt (Bubble 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 nổi bọt (Bubble Sort).
Lời giải
Sắp xếp nổi bọt (Bubble Sort) là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.
Giải thuật này không thích hợp sử dụng với các 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à Ο(n2) với n là số phần tử.
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.
Dưới đây là chương trình Java để giải bài sắp xếp nổi bọt (Bubble Sort) trong Java:
package vn.eLib.array;
public class SapXepNoBot {
public void bubbleSort(int arr[]) {
int temp;
int i,
j;
boolean swapped = false;
// lap qua tat ca cac so
for (i = 0; i < arr.length - 1; i++) {
swapped = false;
// vong lap thu hai
for (j = 0; j < arr.length - 1 - i; j++) {
System.out.print("So sanh cac phan tu: [" + arr[j] + ", " + arr[j + 1] + "]");
// kiem xa xem so ke tiep co nho hon so hien tai hay khong
// trao doi cac so.
// (Muc dich: lam noi bot (bubble) so lon nhat)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
System.out.println(" => trao doi [" + arr[j] + ", " + arr[j + 1] + "]");
} else {
System.out.println(" => khong can trao doi.");
}
}
// neu khong can trao doi nua, tuc la
// mang da duoc sap xep va thoat khoi vong lap.
if (!swapped) {
break;
}
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
};
SapXepNoBot sapXepNoBot = new SapXepNoBot();
System.out.println("Mang du lieu dau vao: ");
sapXepNoBot.display(arr);
System.out.println("-----------------------------");
sapXepNoBot.bubbleSort(arr);
System.out.println("-----------------------------");
System.out.println("\nMang sau khi da sap xep: ");
sapXepNoBot.display(arr);
}
}
Chạy chương trình Java trên cho kết quả như sau:
2. 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.eLib.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:
3. Sắp xếp chèn (Insertion 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 (Insertion Sort).
Lời giải
Sắp xếp chèn là một giải thuật sắp xếp dựa trên so sánh in-place. Ở đây, một danh sách con luôn luôn được duy trì dưới dạng đã qua sắp xếp. Sắp xếp chèn là chèn thêm một phần tử vào danh sách con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo thứ tự.
Với cấu trúc dữ liệu mảng, chúng ta tưởng tượng là: mảng gồm hai phần: một danh sách con đã được sắp xếp và phần khác là các phần tử không có thứ tự. Giải thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh sách con (của cùng mảng đó).
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Dưới đây là chương trình Java để giải bài sắp xếp chèn (Insertion Sort) trong Java:
package vn.eLib.array;
public class SapXepChen {
public void insertionSort(int arr[]) {
int valueToInsert;
int holePosition;
int i;
// lap qua tat ca cac so
for (i = 1; i < arr.length; i++) {
// chon mot gia tri de chen
valueToInsert = arr[i];
// lua chon vi tri de chen
holePosition = i;
// kiem tra xem so lien truoc co lon hon gia tri duoc chen khong
while (holePosition > 0 && arr[holePosition - 1] > valueToInsert) {
arr[holePosition] = arr[holePosition - 1];
holePosition--;
System.out.println("Di chuyen phan tu: " + arr[holePosition]);
}
if (holePosition != i) {
System.out.println(" Chen phan tu: " + valueToInsert + ", tai vi tri: " + holePosition);
// chen phan tu tai vi tri chen
arr[holePosition] = valueToInsert;
}
System.out.println("Vong lap thu " + i);
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
};
SapXepChen sapXepChen = new SapXepChen();
System.out.println("Mang du lieu dau vao: ");
sapXepChen.display(arr);
System.out.println("-----------------------------");
sapXepChen.insertionSort(arr);
System.out.println("-----------------------------");
System.out.println("\nMang sau khi da sap xep: ");
sapXepChen.display(arr);
}
}
Chạy chương trình Java trên cho kết quả như sau:
4. Sắp xếp nhanh (Quick 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 nhanh (Quick Sort).
Lời giải
Giải thuật sắp xếp nhanh (Quick Sort) là một giải thuật hiệu quả cao và dựa trên việc chia mảng dữa liệu thành các mảng nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng với một phần tử được chọn gọi là phần tử chốt (Pivot): một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và mảng còn lại bao gồm các phần tử lớn hơn hoặc bằng phần tử chốt.
Dưới đây là chương trình Java để giải bài sắp xếp nhanh (Quick Sort) trong Java:
package vn.eLib.array;
public class SapXepNhanh {
// ham de trao doi gia tri
public void swap(int arr[], int num1, int num2) {
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}
// ham de chia mang thanh 2 phan, su dung phan tu chot (pivot)
public int partition(int arr[], int left, int right, int pivot) {
int leftPointer = left - 1;
int rightPointer = right;
while (true) {
while (arr[++leftPointer] < pivot) {
// khong lam gi
}
while (rightPointer > 0 && arr[--rightPointer] > pivot) {
// khong lam gi
}
if (leftPointer >= rightPointer) {
break;
} else {
System.out.println(" Phan tu duoc trao doi: " + arr[leftPointer] + ", " + arr[rightPointer]);
swap(arr, leftPointer, rightPointer);
}
}
System.out.println(" Phan tu chot duoc trao doi: " + arr[leftPointer] + ", " + arr[right]);
swap(arr, leftPointer, right);
display(arr);
return leftPointer;
}
// ham sap xep
public void quickSort(int arr[], int left, int right) {
if (right - left <= 0) {
return;
} else {
int pivot = arr[right];
int partitionPoint = partition(arr, left, right, pivot);
quickSort(arr, left, partitionPoint - 1);
quickSort(arr, partitionPoint + 1, right);
}
}
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
};
SapXepNhanh sapXepNhanh = new SapXepNhanh();
System.out.println("Mang du lieu dau vao: ");
sapXepNhanh.display(arr);
System.out.println("-----------------------------");
sapXepNhanh.quickSort(arr, 0, arr.length - 1);
System.out.println("-----------------------------");
System.out.println("\nMang sau khi da sap xep: ");
sapXepNhanh.display(arr);
}
}
Javahạy chương trình Java trên cho kết quả như sau:
5. Sắp xếp trộn (Merge 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 trộn (Merge Sort).
Lời giải
Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Javaonquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.
Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.
Dưới đây là chương trình Java để giải bài sắp xếp trộn (Merge Sort) trong Java:
package vn.eLib.array;
public class SapXepTron {
public void merging(int arr[], int temp[], int low, int mid, int high) {
int l1,
l2,
i;
l1 = low;
l2 = mid + 1;
for (i = low; l1 <= mid && l2 <= high; i++) {
if (arr[l1] <= arr[l2]) {
temp[i] = arr[l1++];
} else {
temp[i] = arr[l2++];
}
}
while (l1 <= mid) {
temp[i++] = arr[l1++];
}
while (l2 <= high) {
temp[i++] = arr[l2++];
}
for (i = low; i <= high; i++) {
arr[i] = temp[i];
}
}
public void sort(int arr[], int temp[], int low, int high) {
int mid;
if (low < high) {
mid = (low + high) / 2;
sort(arr, temp, low, mid);
sort(arr, temp, mid + 1, high);
merging(arr, temp, low, mid, high);
// hien thi mang
display(arr);
} else {
return;
}
}
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
};
int temp[] = new int[10];
SapXepTron sapXeptron = new SapXepTron();
System.out.println("Mang du lieu dau vao: ");
sapXeptron.display(arr);
System.out.println("-----------------------------");
sapXeptron.sort(arr, temp, 0, arr.length - 1);
System.out.println("-----------------------------");
System.out.println("\nMang sau khi da sap xep: ");
sapXeptron.display(arr);
}
}
Javahạy chương trình Java trên cho kết quả như sau:
Trên đây là 5 bài tập về các thuật toán sắp xếp trong Java mà eLib muốn giới thiệu đến bạn. Có rất nhiều cách giải và còn rất nhiều dạng bài tập liên quan đến các thuật toán sắp xếp trong Java, bạn có thể tham khảo trên các bài viết của eLib. Chúc các bạn thành công!
