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)

4.5 ★ | 2 Vote

May be interested

  • Excel does not have Sort Oldest to Newest, what should I do?Excel does not have Sort Oldest to Newest, what should I do?
    you are sorting time data but excel does not have sort oldest to newest. fix the display error problem with tipsmake now.
  • How to sort dates in ascending and descending ways in ExcelHow to sort dates in ascending and descending ways in Excel
    how to sort dates in ascending and descending ways in excel. the following article helps you to sort dates in ascending or descending order in excel quickly and effectively. method 1: step 1: select the data column containing dates to sort - on the data tab
  • How to Bring Mac Quick Look to WindowsHow to Bring Mac Quick Look to Windows
    quick look is a feature that helps users preview files without opening the application on mac, for example you can click on a word file and press space to see the content.
  • How to Sort Alphabetically in Microsoft WordHow to Sort Alphabetically in Microsoft Word
    alphabetizing is a skill worth learning in word, especially if you often work with tables of contents and lists. luckily, once you know it, the process is very simple. this guide will help you learn how to sort lists alphabetically on any version of word.
  • Selection sort algorithm (Selection Sort)Selection sort algorithm (Selection Sort)
    selection sort is a simple algorithm. this sorting algorithm is an algorithm based on in-place comparison, in which the list is divided into two parts, sorted (list) on the left and unsorted (unsorted list) in the right. initially, the sorted part is blank and the unordered part is the original list.
  • How to Sort Gmail by SenderHow to Sort Gmail by Sender
    this is an article that shows you how to sort emails by sender in gmail using inbox search methods. note that these are only alternatives; gmail doesn't allow you to sort your entire inbox by sender. however, you can find a way to see all emails by sender.
  • Bubble Sort (Bubble Sort)Bubble Sort (Bubble Sort)
    bubble arrangement is a simple sort algorithm. this sorting algorithm is carried out based on comparing pairs of adjacent and swap elements if they are not in order.
  • Insert algorithm (Insertion Sort)Insert algorithm (Insertion Sort)
    sort insertion is a sorting algorithm based on in-place comparison. here, a sub-list is always maintained in sorted form. inserting is inserting an element into the sorted list of children. the element is inserted in the appropriate position so that the list is still in order.
  • 8 tips when using Quick Look in OS X8 tips when using Quick Look in OS X
    quick look of os x allows users to view the content of a file by selecting it in the finder and then pressing the spacebar.
  • 6 useful tips for Windows6 useful tips for Windows
    do you find it interesting when friends or family members find you perform some tasks with your computer, things they have never seen before?