Try This Quick Sort

In Chapter 5, you saw a simple classification method called
bubble sorting. It was mentioned at that time that there are
significantly better ratings. Here, you will develop a version of one of the best: quick sort (Quicksort).
Quick classification, invented and named by C.A.R. Hoare, is the best general-purpose classification algorithm currently available. I couldn't show it in Chapter 5 because the best implementation of quick sort is based on recursion. The version we will develop classifies an array of characters, but the logic can be adapted to classify any type of object.
Quick sort is based on the idea of ​​partitions. The general procedure involves selecting a value, called comparing, and then dividing the array into two sections. All elements greater than or equal to the partition value are inserted on one side and smaller ones are inserted on the other. This process is repeated for each remaining section until the array is sorted. For example, given the array fedacb and using the value d as the compare, the first pass of quick sort would rearrange the array as shown below:

Initial f e d a c b
Passage 1 b c a d e f

This process is then repeated for each section – i.e. bca and def. As you can see, the process is essentially recursive in nature, and in fact, the cleanest implementation of quick sort is recursive.
You can select the comparison value in two ways. You can select it randomly or by finding the average of a small set of values ​​taken from the array. To obtain an optimal classification, you must select a value that is exactly in the middle of the value range. However, it is not easy to do this for most datasets. The worst case is when the selected value is at one end. Even so, quick sort will run correctly.
The version of quick sort we will develop selects the middle element of the array as the comparison.

See QSDemo.java.

Quick Sort:

• One of the most efficient and widely used classification algorithms.
• Invented by C.A.R. Hoare.
• Based on the concept of partitions, where the array is divided into sections that are recursively sorted.
• More efficient than bubble sort and other simple methods.

Operation:

• Comparison Value (Pivot):
• A value is chosen as a reference (pivot) and the array is organized around that value.
• Elements smaller than the pivot go to one side and larger ones to the other.
• The process is repeated recursively for each section until the array is completely sorted.

Quicksort

QSDemo

The above is the detailed content of Try This Quick Sort. For more information, please follow other related articles on the PHP Chinese website!