Giới thiệu các thuật toán sắp xếp nâng cao trong cấu trúc dữ liệu và giải thuật
Mục tiêu của bài học này là cung cấp kiền thức về các thuật toán sắp xếp nâng cao như:
- Quick Sort
- Shell Sort
- Counting Sort
- Radix Sort
- Merge Sort
Giới thiệu cơ bản thuật toán sắp xếp nhanh (Quick Sort)
Thuật toán là quick sort một thuật toán sắp xếp nhanh (phát triển bởi C.A.R. Hoare) trên một danh sách cho trước, gồm hai giai đoạn, giai đoạn 1, chia nó thành hai danh sách bằng cách so sánh từng phần tử của danh sách với một phần tử được chọn (được gọi là phần tử chốt). Những phần tử nhỏ hơn hoặc bằng phần tử chốt được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử lớn hơn chốt được đưa về phía sau và thuộc danh sách đứng sau. Cứ tiếp tục chia như vậy tới khi các danh sách con đều có độ dài bằng 1
Phần này giới thiệu kiến thức cơ bản của về thuật toán quick sort
Link Page: https://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm
Thuật toán quick sort là thuật toán chia để trị, bước chia (partition) cũng là một bước dài và khó để tìm trụ (pivot), bước trị chỉ là việc đệ quy trên phần nhỏ hơn của mảng dựa trên giá trị pivot
Video này trình bày, giải thích về thuật toán quick sort thông qua giả mã và ví dụ cụ thể.
Link Video: Giới thiệu Quick Sort (Quick Sort)
Video này tiếp tục giải thích về bước partition trong thuật toán quick sort thông qua giả mã và ví dụ cụ thể.
Link Video:
https://www.udemy.com/introduction-to-data-structures-algorithms-in-java/learn/v4/t/lecture/805552
Giới thiệu cơ bản về thuật toán Shell Sort
Thuật toán Shell Sort là phiên bản nâng cấp của Insertion Sort, ý tưởng chính của thuật toán là phân chia dãy ban đầu thành những dãy con mà mỗi phần tử của dãy cách nhau 1 vị trí là h. Sử dụng Insertion sort áp dụng trên mỗi dãy con đó, sẽ làm cho các phần tử được đưa về vị trí đúng tương đối (trong dãy con) 1 cách nhanh chóng.
Sau đó tiếp tục giảm khoảng cách h để tạo thành các dãy con mới (Tạo điều kiện để so sánh một phần tử với nhiều phần tử khác trước đó không ở cùng dãy con với nó) và lại tiếp tục sắp xếp.
Thuật toán dừng khi h = 1, lúc này bảo đảm tất cả các phần tử trong dãy ban đầu sẽ được so sánh với nhau để xác định trật tự cuối cùng.
Nguồn tài liệu này sẽ giới thiệu cơ bản về thuật toán Shell Sort
Link Page: https://www.tutorialspoint.com/data_structures_algorithms/shell_sort_algorithm.htm
Video giới thiệu thuật toán shell sort được nâng cấp từ thuật toán insertion sort thông qua ví dụ.
Link Video: Thuật toán Shell Sort (shell sort)
Cài đặt Shell Sort trên JAVA
class EffSort
{int [] a; int n;
EffSort() {}
EffSort(int [] b)
{int i;
n = b.length;
a = new int[n];
for(i=0;i<n;i++) a[i]= b[i];
}
// Set giá trị cho mảng
void setData(int [] b)
{int i;
n = b.length;
a = new int[n];
for(i=0;i<n;i++)
a[i]= b[i];
}
// Hiển thị giá trị trong mảng
void display()
{int i;
for(i=0;i<n;i++)
System.out.print(" " + a[i]);
System.out.println();
}
//==================================================
// shell sort
void insertSort2(int h)
{int i,j,x;
for(i=h;i<n;i++)
{x=a[i];
j=i;
while(j-h>=0 && x<a[j-h])
{a[j]=a[j-h];//Keo nut lon hon x len h vi tri
j=j-h;
};
a[j]=x;
}
};
void shellSort(int [] step)
{ /*Cac buoc tang la step[0],step[1],...,step[stepnum] trong do
step[0]>step[1]>...>step[stepnum] */
int h,i,stepnum;
stepnum = step.length;
for(i=0;i<stepnum;i++)
{h=step[i];
insertSort2(h);
}
};
void shellSort()
{int [] step = {5,3,1};
shellSort(step);
};
}
//==================================================
public class Main
{public static void main(String args[])
{int [] b = {7,3,5,9,11,8,6,15,10,12,14};
EffSort t = new EffSort(b);
t.shellSort();t.display();
System.out.println();
}
}
Thuật toán sắp xếp đếm (Counting Sort)
Thuật toán Counting Sort: Counting Sort là thuật toán đếm số lần xuất hiện của các giá trị khác nhau trong mảng ban đầu và gán giá trị vừa đếm vào vị trí tương ứng của 1 mảng có độ dài là giá trị lớn nhất của mảng.
Đây là hàm code bằng java trình bày thuật toán
int[] countingSort(int[] a, int k) {
int c[] = new int[k];
for (int i = 0; i < a.length; i++)
c[a[i]]++;
for (int i = 1; i < k; i++)
c[i] += c[i-1];
int b[] = new int[a.length];
for (int i = a.length-1; i >= 0; i--)
b[--c[a[i]]] = a[i];
return b;
}
Video giới thiệu thuật toán Counting sort
Link video: Thuật toán sắp xếp đếm (Counting Sort)
Thuật toán sắp xếp theo cơ số (Radix Sort)
Radix Sort dựa trên tính chất "số" của các khóa. Trong giải thuật sắp xếp theo cơ số, ta không chỉ so sánh giá trị của các khóa mà so sánh các thành phần của khóa. Giả sử các khóa là các số biểu diễn theo hệ ghi số cơ số M. Khi đó sắp xếp theo cơ số sẽ so sánh từng k.
Chúng ta mô tả cách sắp này khi cơ số M=10. Giả sử phải sắp các hồ sơ đánh số bởi 3 chữ số thập phân. Đầu tiên ta chia các hồ sơ vào các đống có cùng chữ số hàng trăm (đồng thời xếp các đống theo thứ tự của chữ số hàng trăm), trong mỗi đống con lại phân chia theo chữ số hàng chục, cuối cùng trong mỗi đống có cùng chữ số hàng trăm và hàng chục, sắp xếp theo thứ tự của chữ số hàng đơn vị.
Trong máy tính, đương nhiên việc sắp xếp theo cơ số nhị phân (cơ số 2) hoặc cơ số là lũy thừa của 2 là thuận lợi nhất. Trong trường hợp cơ số 2, việc phân hoạch tương tự như phân hoạch trong Quick Sort, chỉ khác ở chỗ cách chọn phần tử chốt.
Radix Sort hoàn toàn có thể được áp dụng để sắp xếp string.
Video giới thiệu về thuật toán Radix Sort thông qua ví dụ
Link Video: Thuật toán sắp xếp theo cơ số (Radix Sort)
Cài đặt Radix Sort in JAVA
/****************************************************************************
* Author: Isai Damier * Title: Radix Sort * Project: geekviewpoint * Package: algorithms * * Statement: * Given a disordered list of integers, rearrange them in natural order. * * Sample Input: {18,5,100,3,1,19,6,0,7,4,2} * * Sample Output: {0,1,2,3,4,5,6,7,18,19,100} * * Time Complexity of Solution: * Best Case O(k*n); Average Case O(k*n); Worst Case O(k*n), * where k is the length of the longest number and n is the * size of the input array. * * Note: if k is greater than log(n) then an n*log(n) algorithm would be a * better fit. In reality we can always change the radix to make k * less than log(n). * * Approach:
* radix sort, like counting sort and bucket sort, is an integer based * algorithm (i.e. the values of the input array are assumed to be * integers). Hence radix sort is among the fastest sorting algorithms * around, in theory. The particular distinction for radix sort is that it * creates a bucket for each cipher (i.e. digit); as such, similar to * bucket sort, each bucket in radix sort must be a growable list that may * admit different keys. * * For decimal values, the number of buckets is 10, as the decimal system * has 10 numerals/cyphers (i.e. 0,1,2,3,4,5,6,7,8,9). Then the keys are * continuously sorted by significant digits.
***************************************************************************/
public void radixsort(int[] input) { final int RADIX = 10; // declare and initialize bucket[] Khai báo và khởi tạo List<Integer>[] bucket = new ArrayList[RADIX]; for (int i = 0; i < bucket.length; i++) { bucket[i] = new ArrayList<Integer>(); } // sort boolean maxLength = false; int tmp = -1, placement = 1; while (!maxLength) { maxLength = true; // split input between lists for (Integer i : input) { tmp = i / placement; bucket[tmp % RADIX].add(i); if (maxLength && tmp > 0) { maxLength = false; } }
// empty lists into input array int a = 0; for (int b = 0; b < RADIX; b++) { for (Integer i : bucket[b]) { input[a++] = i; } bucket[b].clear(); } // move to next digit placement *= RADIX; }}
Thuật toán sắp xếp trộn (Merge Sort)
Thuật toán Merge Sort cùng với sắp xếp nhanh (quick sort) là hai thuật toán sắp xếp dựa vào tư tưởng "chia để trị" (divide and conquer). Thủ tục cơ bản là việc trộn hai danh sách đã được sắp xếp vào một danh sách mới theo thứ tự. Nó có thể bắt đầu trộn bằng cách so sánh hai phần tử một (chẳng hạn phần tử thứ nhất với phần tử thứ hai, sau đó thứ ba với thứ tư...) và sau khi kết thúc bước 1 nó chuyển sang bước 2. Ở bước 2 nó trộn các danh sách hai phần tử thành các danh sách bốn phần tử. Cứ như vậy cho đến khi hai danh sách cuối cùng được trộn thành một.
Nguồn tài liệu này sẽ giới thiệu cơ bản về thuật toán merge_sort
Link page: https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.htm
Video này giới thiệu về thuật toán merge_sort thông qua ví dụ
Link Video: Sắp xếp hợp nhất (Merge sort)
Cài đặt Merge Sort trên JAVA
Ngoài ra các bạn có thể xem code Merge sort in java
import java.util.*;
class EffSort
{int [] a; int n;
EffSort() {}
EffSort(int [] b)
{int i;
n = b.length;
a = new int[n];
for(i=0;i<n;i++) a[i]= b[i];
}
void setData(int [] b)
{int i;
n = b.length;
a = new int[n];
for(i=0;i<n;i++)
a[i]= b[i];
}
void display()
{int i;
for(i=0;i<n;i++)
System.out.print(" " + a[i]);
System.out.println();
}
//==================================================
/*Sap xep danh sach theo thu tu tang dan bang phuong phap
Merge Sort.
Input: Day a[0],a[1],...,a[n-1]
Output: Danh sach da duoc sap xep
*/
void mergeSort(int p, int r)
{if(p>=r) return;
int q = (p+r)/2;
mergeSort(p,q);
mergeSort(q+1,r);
merge(p,q,r);
}
void merge(int p, int q, int r)
{if(!(p<=q) && (q<=r)) return;
int n,i,j,k,x; n = r-p+1;
int [] b = new int[n];
i=p;j=q+1;k=0;
while(i<=q && j<=r)
{if(a[i]<a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while(i<=q) b[k++] = a[i++];
while(j<=r) b[k++] = a[j++];
k=0;
for(i=p;i<=r;i++) a[i] = b[k++];
}
}
//==================================================
public class Main
{public static void main(String args[])
{int [] b = {7,3,5,9,11,8,6,15,10,12,14};
EffSort t = new EffSort(b);
int n=b.length;
t.mergeSort(0,n-1);t.display();
System.out.println();
}
}
********************
Bài tập thực hành:
Viết chương trình để nhập vào một mảng a gồm n số nguyên, sau đó hãy sắp xếp các phần tử trong mảng bằng phương pháp quick sort. Tạo menu cho chương trình, menu gồm các chức năng sau:
- Nhập mảng a gồm n số nguyên
- Sắp xếp mảng a
- Hiển thị giá trị của mảng a ra màn hình
Gợi ý:
- Gợi ý về Input và Output:
Menu sẽ hiển thị như sau:
1. Nhập dữ liệu
2. Sắp xếp
3. Hiển thị giá trị mảng a
Nhập vào chức năng 1/2/3:1
input:
n= 11;
a[] = 7,3,5,9,11,8,6,15,10,12,14;
Nhập vào chức năng 1/2/3: 3
Output: 7,3,5,9,11,8,6,15,10,12,14;
Nhập vào chức năng 1/2/3: 2
Nhập vào chức năng 1/2/3: 3
Output: 3 5 6 7 8 9 10 11 12 14 15
- Chương trình gồm có các lớp và các phương thức cơ bản sau (các em có thể thêm các lớp, các phương thức nếu cảm thấy cần thiết) hoặc có thể làm theo cách khác
// Lớp EffSort
class EffSort
{int [] a; int n;
EffSort() {}
EffSort(int [] b)
{int i;
n = b.length;
a = new int[n];
for(i=0;i<n;i++) a[i]= b[i];
}
void display()
{int i;
for(i=0;i<n;i++)
System.out.print(" " + a[i]);
System.out.println();
}
//--------------------------------------------------
void swap(int [] a, int i, int k) // Hàm hoán vị
{int x; x=a[i];a[i]=a[k];a[k]=x;
}
//==================================================
/*CAI DAT GIAI THUAT QUICKSORT}
Phương thức partition sẽ phân hoạch danh sách từ low đến up thành 2 phần:
các nút có nội dung <= a[pivot] nằm bên trái pivot, các nútt có nội dung > a[pivot] nằm bên phải
Chọn nút trục=a[low], quét 2 đầu, i từ dưới lên, j trên xuống và đổi chỗ các phần tử sai chỗ, khi kết thúc quét thì đổi chỗ cho a[low]
và a[j], vậy nút trục sẽ chuyển đến vị trí j;*/
int partition(int low,int up) // return pivot index
{……………………...
}
// Phương thức quicksort sẽ gọi tới phương thức partition để sắp xếp theo thuật toán quick sort
void quickSort(int low,int up)
{………………………………...
}
//-----------------------------------------------------
void quickSort()
{quickSort(0,n-1);
}
}
//==================================================
public class Main{
static int [] b;
// Phương thức input để nhập giá trị cho mảng b;
static void input(int [] b)
{…………………….}
/*Trong phương thức main phải xây dựng menu để gọi tới các phương thức cần thiết như input(b), gọi tới phương thức khởi tạo EffSort(b) và quickSort(); display() trong lớp EffSort*/
public static void main(String args[])
{
……………………………………….
}
}