Đó là sắp xếp và tìm kiếm đối với mảng . Bởi vì sau này các bạn có thể dùng một list (danh sách) các đối tượng , thực hiện tìm kiếm hay sắp xếp theo thứ tự . ... Sau loạt bài này các bạn sẽ có cách tuy duy rất căn bản đối với các giải thuật cơ bản về danh sách các đối tượng.
I. Tìm kiếm
Có rất nhiều phương pháp cũng như thuật toán tìm kiếm . Nhưng ở đây mình sẽ giới thiệu cho các bạn 2 phương pháp căn bản.
1. Tìm kiếm tuyến tính(Linear Search Approach).
Tìm kiếm tuyến tính hay tìm kiếm tuần tự là bắt đầu bằng việc so sánh x với a1; khi x=a1, nghiệm là vị trí a1, tức là 1; khi x¹a1, so sánh x với a2. Nếu x=a2, nghiệm là vị trí của a2, tức là 2. Khi x¹a2, so sánh x với a3. Tiếp tục quá trình này bằng cách tuần tự so sánh x với mỗi số hạng của bảng liệt kê cho tới khi tìm được số hạng bằng x, khi đó nghiệm là vị trí của số hạng đó. Nếu toàn bảng liệt kê đã được kiểm tra mà không xác định được vị trí của x, thì nghiệm là 0 .
Kết quả:
Có rất nhiều phương pháp cũng như thuật toán tìm kiếm . Nhưng ở đây mình sẽ giới thiệu cho các bạn 2 phương pháp căn bản.
1. Tìm kiếm tuyến tính(Linear Search Approach).
Tìm kiếm tuyến tính hay tìm kiếm tuần tự là bắt đầu bằng việc so sánh x với a1; khi x=a1, nghiệm là vị trí a1, tức là 1; khi x¹a1, so sánh x với a2. Nếu x=a2, nghiệm là vị trí của a2, tức là 2. Khi x¹a2, so sánh x với a3. Tiếp tục quá trình này bằng cách tuần tự so sánh x với mỗi số hạng của bảng liệt kê cho tới khi tìm được số hạng bằng x, khi đó nghiệm là vị trí của số hạng đó. Nếu toàn bảng liệt kê đã được kiểm tra mà không xác định được vị trí của x, thì nghiệm là 0 .
int[] list = {1, 4, 4, 2, 5, -3, 6, 2}; int i = linearSearch(list, 4); // returns 1 int j = linearSearch(list, -4); // returns -1 int k = linearSearch(list, -3); // returns 52. Tìm kiếm nhị phân(Binary Search Approach)
Thuật toán này có thể được dùng khi bảng liệt kê có các số
hạng được sắp theo thứ tự tăng dần. Chẳng hạn, nếu các số hạng là các số thì
chúng được sắp từ số nhỏ nhất đến số lớn nhất hoặc nếu chúng là các từ hay xâu
ký tự thì chúng được sắp theo thứ tự từ điển. Thuật toán thứ hai này gọi là
thuật toán tìm kiếm nhị phân. Nó được tiến hành bằng cách so sánh phần tử cần
xác định vị trí với số hạng ở giữa bảng liệt kê. Sau đó bảng này được tách làm
hai bảng kê con nhỏ hơn có kích thước như nhau, hoặc một trong hai bảng con ít
hơn bảng con kia một số hạng. Sự tìm kiếm tiếp tục bằng cách hạn chế tìm kiếm ở
một bảng kê con thích hợp dựa trên việc so sánh phần tử cần xác định vị trí với
số hạng giữa bảng kê. Ta sẽ thấy rằng
thuật toán tìm kiếm nhị phân hiệu quả hơn nhiều so với thuật toán tìm kiếm
tuyến tính.Các bạn để ý vào hình vẽ dưới sẽ hiểu tường minh hơn
Giải thuật :
public class BinarySearch {
/** Use binary search to find the key in the list */
public static int binarySearch(int[] list, int key) {
int low = 0;
int high = list.length - 1;
while (high >= low) {
int mid = (low + high) / 2;
if (key < list[mid])
high = mid - 1;
else if (key == list[mid])
return mid;
else
low = mid + 1;
}
return -low - 1;
}
public static void main(String[] args) {
int array[] = { 1, 2, 3, 5, 7, 4, 6 };
Scanner in = new Scanner(System.in);
System.out.println("nhap key:");
int key = in.nextInt();
System.out.println("Key vi tri " + (binarySearch(array, key) + 1));
}
}
II. Sắp sếp (sort)
Mình sẽ giới thiệu cho các bạn những thuật toán sắp xếp cơ bản . Để sau này các bạn có thể trả lời phỏng vấn một cách nguy hiểm hơn . Có thể các bạn biết nhưng thuật toán này . Tuy nhiên khi hỏi tới các bạn lại không biết tên nó , hoặc không diễn đạt được nổi nó.
1.Selection Sort
Định nghĩa giải thuật :
Lần lượt chọn phần tửnhỏnhất trong dãy chỉsố k1, k2,. . ., kn với i = 0, 1, . .,n; ki< k i+1< . . ., kn và đổi chỗ cho phần tử thứ ki. Như vậy, sau j =n-1 lần chọn, chúng ta sẽ só dãy khoá được sắp xếp theo thứ tự tăng dần. Đối với dãy số trên,
chúng ta sẽ thực hiện như sau:
* Lần chọn thứ 0: Tìm trong khoảng từ 0 đến n-1bằng cách thực hiện n- 1 lần so
sánh để xác định phần tử min0 và đổi chỗ cho phần tử ở vị trí 0.
* Lần chọn thứ 1: Tìm trong khoảng từ 1 đến n-1 bằng cách thực hiện n- 2 lần so sánh để xác định phần tử min1 và đổi chỗ cho phần tử ở vị trí 1.
.....................................................................................................................................
* Lần chọn thứ i: Tìm trong khoảng từ i đến n-1 bằng cách thực hiện n- i lần so sánh để xác định phần tử mini và đổi chỗ cho phần tử ở vị trí i.
* Lần chọn thứ n-2: Tìm trong khoảng từ n-2 đến n-1 bằng cách thực hiện 1 lần so
sánh để xác định phần tử min n-2 và đổi chỗ cho phần tử ở vị trí n-2.
Cụ thể sẽ được mô tả dưới hình sau :
Giải thuật :
public static void selectionSort(double[] list) {
double currentMax;
currentMax = list[0];
int currentMaxIndex = 0;
for (int i = list.length - 1; i >= 1; i--)
// Find the maximum in the list[0..i]
{
for (int j = 1; j <= i; j++) {
if (currentMax < list[j]) {
currentMax = list[j];
currentMaxIndex = j;
}
}
// Swap list[i] with list[currentMaxIndex] if necessary;
if (currentMaxIndex != i) {
list[currentMaxIndex] = list[i];
list[i] = currentMax;
}
}
}
2. Insertion Sort
Insert Sort được thực hiện dựa trên kinh nghiệm của những người chơi bài. Khi có i-1 lá bài đã được sắp xếp đang ở trên tay, nay ta thêm lá bài thứ i thì lá bài đó được so sánh với lá bài i-1, i-2, . . để tìm được vị trí thích hợp và chèn vào quân bài thứ i.
Nguyên tắc thực hiện như sau :
* Lấy phần tử đầu tiên i0, đương nhiên tập một phần tử là tập đã được sắp xếp.
* Lấy tiếp phần tử thứ i1 chọn vị trí thích hợp của phần tử thứ i1 trong tập hai phần tử và thực hiện đổi chỗ.
* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
* Lấy tiếp phần tử thứ ik chọn vị trí thích hợp của phần tử thứ ik trong tập hai ik-1 phần tử và thực hiện đổi chỗ, dãy sẽ được sắp xếp hoàn toàn sau n-1 lần chèn phần tử vào vị trí thích hợp.
Cụ thể như hình vẽ sau :
Giải thuật :
public static void insertionSort(double[] list) {
for (int i = 1; i < list.length; i++) {
/**
* insert list[i] into a sorted sublist list[0..i-1] so that
* list[0..i] is sorted.
*/
double currentElement = list[i];
int k;
for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
list[k + 1] = list[k];
}
// Insert the current element into list[k+1]
list[k + 1] = currentElement;
}
}
3 . Sắp xếp nổi bọt (Bubble Sort)
Bubble Sort được thực hiện bằng cách đổi chỗ liên tiếp hai phần tử kế cận khi chúng ngược thứ tự. Quá trình thực hiện được duyệt từ đáy lên đỉnh. Như vậy, sau lần duyệt thứ nhất,phần tử lớn nhất sẽ được xếp đúng ở vị trí thứ n-1, ở lần duyệt thứ k thì k phần tử lớn nhất đã được xếp đúng vị trí n-1, n-2, . ., n-k+1. Sau lần duyệt thứ n-1, toàn bộ n phần tử sẽ được sắp xếp. Với phương pháp này, các phần tử có giá trị nhỏ được nổi dần lên như nước sủi bọt nhờ đó nó có tên gọi “phương pháp sủi bọt”.
Giải thuật :
public void bubbleSort(int [] array){
for(int i = 0; i< array.length; i++){
for (int j = array.length - 1; j > 0; j--) {
if(array[j] < array[j-1]){
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}
}
4. Quick Sort
Quick Sort là chọn ngẫu nhiên một phần tử nào đó của dãy làm khoá chốt. Tính từ khoá chốt, các phần tử nhỏ hơn khoá phải được xếp vào trước chốt (đầu dãy), mọi phần tử sau chốt được xếp vào sau chốt (cuối dãy). Để làm được việc đó, các phần tử trong dãy sẽ được so sánh với khoá chốt và tráo đổi vị trí cho nhau, hoặc cho khoá chốt nếu phần tử đó lớn hơn chốt mà lại nằm trước chốt hoặc nhỏ hơn chốt nhưng lại nằm sau chốt. Khi việc đổi chỗ lần đầu tiên đã thực hiện xong thì dãy hình thành hai đoạn: một đoạn bao gồm các phần tử nhỏ hơn chốt, một đoạn gồm các phần tử lớn hơn chốt, còn chốt chính là vị trí của phần tử trong dãy được sắp xếp.
Áp dụng cho mỗi đoạn trước chốt và sau chốt cho tới khi các đoạn còn lại hai phần tử thì việc ghi nhớ không còn cần thiết nữa. Dãy sẽ được sắp xếp khi tất cả các đoạn được xử lý xong. Ví dụ với dãy:
42 23 74 11 65 58 94 36 99 87
Ta chọn chốt đầu tiên là 42. Để phát hiện ra hai khoá cần đổi chỗ cho nhau, ta dùng hai biến i, j với giá trị ban đầu i=2, j=10. Nếu ki< 42 thì tiếp tục tăng i và lặp lại cho tới khi
gặp phần tử thứ ki>42. Duyệt các phần tử thứ kj với 42 nếu kj> 42 thì j giảm đi một, cho
tới khi gặp phần tử thứ kj<42 thì phần tử thứ ki và kj được đổi chỗ cho nhau. Quá trình sẽ
được lặp lại với ki và kj cho tới khi i=j chính là vị trí dành cho khoá 42. Cuối cùng chúng ta
đổi chỗ 42 cho khoá cho kj.
Các bạn có thể tham khảo hình ảnh tại đây để có thể hiểu rõ hơn về nguyên lý của thuật toán quick sort
Giải thuật :
// Tìm chốt
public int findPivot(int i, int j, int[] array) {
if (array.length == 1) {
return -1;
}
int k = i + 1;
int pivot = array[i];
while ((k <= j) && (array[k] == pivot)) {
k++;
}
if (k > j) {
return -1;
}
if (array[k] > pivot) {
return k;
} else {
return i;
}
}
// Tìm partition
public int pointPartition(int i, int j, int pivotKey, int[] array) {
int partition = -1;
int L = i;
int R = j;
while (L <= R) {
while (array[L] < pivotKey)
L++;
while (array[R] >= pivotKey)
R--;
if (L < R) {
int temp = array[L];
array[L] = array[R];
array[R] = temp;
}
}
partition = L;
return partition;
}
// Sắp xếp
public void quickSort(int i, int j, int[] array) {
int pivot = findPivot(i, j, array);
if (pivot == -1)
return;
int partition = pointPartition(i, j, array[pivot], array);
quickSort(i, partition - 1, array);
quickSort(partition, j, array);
}
OK như vậy là cũng ổn rồi . Bây giờ là bài tập vận dụng của các bạn . Hãy chăm chỉ lên nào các chiến binh.
Bài 1 :Viết
chương trình nhập vào vào mảng A có n phần tử, các phần tử là những số nguyên
lớn hơn 0 và nhỏ hơn 100 được nhập vào từ bàn phím. Thực hiện các chức năng
sau
a)
Tìm phần tử lớn nhất và lớn thứ 2 trong mảng cùng chỉ
số của các số đó.
b)
Sắp xếp mảng theo thứ tự giảm dần (Sử dụng một trong các thuật toán sắp xếp ở trên).
c)Nhập một số nguyên x và chèn x vào mảng A sao cho vẫn
đảm bảo tính sắp xếp giảm dần
Note : Trong source code mình làm theo hướng khác để các bạn hiểu thêm về cách làm.
Bài 2 : Nhập số n và dãy các
số thực a0 , a1
,..., an-1. Không đổi chỗ các phần tử và không dùng thêm mảng số
thực nào khác (có thể dùng mảng số nguyên nếu cần) hãy cho hiện trên màn hình
dãy trên theo thứ tự tăng dần
Bài 3 : Viết chương trình thử nghiệm các thuật toán
trên một dãy n số nguyên ngẫu nhiên (10<n<100)
a) Sắp
xếp chọn
b) Sắp
xếp chèn
c) Sắp
xếp nổi bọt
d) Sắp
xếp nhanh
e) Sắp
xếp trộn (bổ sung)
f) Sắp
xếp vun đống (Heap Sort) (bố sung)
Source code : here
Pass extract : https://coderandtutorial.blogspot.com
No comments:
Post a Comment