Tìm hiểu thuật toán sắp xếp nhanh(QuickSort)

Thuật toán QuickSort là một trong những thuật toán sắp xếp hiệu quả nhất và dựa trên việc chia một mảng thành các mảng nhỏ hơn, sắp xếp trong các mảng nhỏ này để đi tới kết quả. Sắp xếp nhanh có khả năng sắp xếp danh sách các yếu tố dữ liệu nhanh hơn đáng kể so với bất kỳ thuật toán sắp xếp phổ biến nào. Nếu so với các thuật toán sắp xếp phổ biến như Insertion sort, selection sort hay bubble sort, thì quicksort cho một hiệu năng đáng kể.

Chúng ta sẽ tìm hiểu quick sort là gì? Cách sử dụng và lập trình thuật toán quick sort sắp xếp nhanh bằng ngôn ngữ Java

Thuật toán Quick sort là một thuật toán chia để trị.Thuật toán sẽ chọn một phần tử trong chuỗi, mảng để làm điểm đánh dấu (pivot). Sau khi lựa chọn được điểm đánh dấu (pivot) sẽ thực hiện chia mảng thành các mảng con việc này gọi là phân đoạn (partition). Và lặp đi lặp lại như vậy. cho đến khi kết thúc

Vì thế hiệu suât của QuickSort phụ thuộc vào các lựa chọn điểm đánh dấu pivot. và thuật toán phân đoạn Nếu lựa chọn pivot tốt, thì thuật toán sẽ có tốc độ nhanh hơn.

Cách lựa chọn Pivot trong thuật toán sắp xếp nhanh:

Trong một mảng, dãy số cho trước, chúng ta có thể lựa chọn pivot bằng các cách sau:

Chọn phần từ đầu tiên của mảng
Chọn phần tử cuối cùng của mảng
Chọn phần tử random trong mảng
Chọn phần tử có giá trị nằm giữa mảng
Cho một mảng và xác định phần tử Xlà pivot
Xử lý Đặt Xvào đúng vị trí của mảng đã sắp xếp
Di chuyển tất cả các phần tử của mảng nhỏ hơn Xqua bên trai, và lớn hơn sang bên phải

Khi đó ta sẽ có 2 mảng con: mảng bên trai của X và mảng bên phải của X. Tiếp tục công việc với mỗi mảng con(chọn pivot, phân đoạn) cho tới khi mảng được sắp xếp.

Hướng dẫn code phân đoạn partition:

Đặt pivot là phần tử cuối cùng của dãy số arr.

Ví dụ thuật toán phân đoạn :

package gatostudy.com.sort;

// Java program for implementation of QuickSort
class QuickSort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] < pivot)
{
i++;

// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;

return i+1;
}

/* The main function that implements QuickSort()
arr[] –> Array to be sorted,
low –> Starting index,
high –> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);

// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}

/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+” “);
System.out.println();
}

// Driver program
public static void main(String args[])
{
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = arr.length;

QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);

System.out.println(“sorted array”);
printArray(arr);
}
}
/*This code is contributed by Rajat Mishra */

Đoạn sau mô tả cụ thể việc chia đoạn để lấy đặt đúng vị trí của pivot.

arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes:  0   1   2   3   4   5   6 

low = 0, high =  6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1

Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0 
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j 
                                     // are same

j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30 

j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j] 
i = 3 
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped 

We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot) 
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped