Quick Sort (Quick Sort)

What is Quick Sort?

Quick Sort is a highly efficient algorithm and is based on dividing the array into smaller pieces. The algorithm quickly divides the array into two parts by comparing each element of the array with an element called a Pivot element: an array of elements smaller than or equal to key and array elements The rest consists of larger or equal elements.

This split process continues until the length of the sub-arrays is equal to 1. The quick sorting algorithm appears to be quite effective for large data sets where the average case complexity and the case of especially O (nlogn) where n is the number of elements.

Techniques for selecting key elements in quick sort algorithms (Quick Sort)

The technique to select latch elements greatly affects the ability to fall into infinite loops for special cases. It is best to choose the pivot element located in the median of the list. Then, after log2 (n) the split time we will reach the size of the child arrays by 1.

Here are ways to select latch elements:

Select the top or bottom element as the latch element.

Select the middle element of the list as a latch element.

Select the middle element in the top three elements, centered and standing at the end as the latch element.

Select random elements as latch elements. However, this is very easy to lead to the possibility of falling into special circumstances.

Illustrate how to divide in a quick sort algorithm (Quick Sort)

The illustration below illustrates how to find the key element in the array. Here, we select the latch element at the bottom of the list.

Quick Sort (Quick Sort) Picture 1

The latch element divides the list into two parts. And using recursion, we find the key element for the child arrays until the list has only one element.

Quick-key element algorithm (Quick Sort)

Based on how to divide the list in the quick sort algorithm above, we can write an algorithm as below.

 Bước 1 : Chọn phần tử chốt là phần tử có chỉ mục cao nhất (phần tử ở cuối danh sách) Bước 2 : Khai báo hai biến để trỏ tới bên trái và bên phải của danh sách, ngoại trừ phần tử chốt Bước 3 : Biến bên trái trỏ tới mảng con bên trái Bước 4 : Biến bên phải trỏ tới mảng con bên phải Bước 5 : Khi giá trị tại biến bên trái là nhỏ hơn phần tử chốt thì di chuyển sang phải Bước 6 : Khi giá trị tại biến bên phải là lớn hơn phần tử chốt thì di chuyển sang trái Bước 7 : Nếu không trong trường hợp cả bước 5 và bước 6 thì tráo đổi giá trị biến trái và phải Bước 8 : Nếu left ≥ right, thì đây chính là giá trị chốt mới

Sample key algorithm in quick sort (Quick Sort)

From the steps above, we can deduce the sample code for the Quick Sort algorithm as follows:

 B ắ t đầ u h à m partitionFunc ( left , right , pivot ) leftPointer = left - 1 rightPointer = right while True th ự c hi ệ n while A [++ leftPointer ] < pivot th ự c hi ệ n //không làm điều gì k ế t th ú c while while rightPointer > 0 && A [-- rightPointer ] > pivot th ự c hi ệ n //không làm điều gì k ế t th ú c while if leftPointer >= rightPointer break else Tr á o đổ i leftPointer , rightPointer k ế t th ú c if k ế t th ú c while Tr á o đổ i leftPointer , right return leftPointer K ế t th ú c h à m 

Quick Sort (Quick Sort)

Using latch element algorithm recursively, we can end up with smaller sub-arrays. Then each of these sub-arrays can be processed with quick sort. Below, I use recursive algorithm for quick sort:

 Bước 1 : Lấy phần tử chốt là phần tử ở cuối danh sách Bước 2 : Chia mảng bởi sử dụng phần tử chốt Bước 3 : Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên trái Bước 4 : Sử dụng sắp xếp nhanh một cách đệ qui với mảng con bên phải

Sample algorithm for Quick Sort (Quick Sort)

From the algorithm above, we can deduce the sample code for the algorithm to use recursion for quick sort as follows:

 B ắ t đầ u h à m quickSort ( left , right ) if right - left <= 0 return else pivot = A [ right ] partition = partitionFunc ( left , right , pivot ) quickSort ( left , partition - 1 ) quickSort ( partition + 1 , right ) k ế t th ú c if K ế t th ú c h à m 

According to Tutorialspoint

Previous lesson: Shell Sort in data structure and algorithm

Next lesson: Graph data structure (Graph)