Quick sort is often used because the sorting efficiency is more efficient among several sorting methods with the same O(N*logN).
The basic idea of the method is:
1. Start by taking a number from the series as the base number.
2. Partitioning process, put all numbers larger than this number to the right of it, and all numbers less than or equal to it to the left of it.
3. Repeat step 2 for the left and right intervals until there is only one number in each interval.
Now let's go through an example to illustrate fast platooning.
Let's say there is an array:
6 2 4 5 3
Step 1: Pick a base number, don't be intimidated by the term, you can think of it as a number that compares sizes, because sorting is comparing sizes, the
For example, I chose the last number 3 as the base number, in turn, the number of arrays and 3 comparisons, smaller than 3 put on the left, larger than 3 put on the right, so that there are the following results:
2 3 6 4 5
Step 2: Determine the number of intervals, after the first step in the left interval there is only one number, there is no number to compare with it, so there is no need to repeat the operation, the right interval there:
6 4 5
Repeat the first step and select 5 as the base number to get the comparison results:
4 5 6
In this way, the left and right intervals are only one number, which marks the completion of sorting, and finally all the intervals are merged to get the sorting result:
2 3 4 5 6
def quick_sort(array):
less = []; greater = []
if len(array) <= 1:
return array
pivot = ()
for x in array:
if x <= pivot: (x)
else: (x)
return quick_sort(less) + [pivot] + quick_sort(greater)
list = [2,4,2,6,7,8,1]
print quick_sort(list)
[1, 2, 2, 4, 6, 7, 8]
Isn't it much simpler than C, C#, JAVA and so on ^. ^.
TIP: Fast sorting with de-emphasis
As follows, just modify the collection to a single-valued element, which we'll demonstrate using Python 3 here.
# -*- coding: utf-8 -*- import random L = [2, 3, 8, 4, 9, 5, 6, 5, 6, 10, 17, 11, 2] def qsort(L): if len(L)<2: return L pivot_element = (L) small = [i for i in L if i< pivot_element] #medium = [i for i in L if i==pivot_element] large = [i for i in L if i> pivot_element] return qsort(small) + [pivot_element] + qsort(large) print(qsort(L))
Output.
[2, 3, 4, 5, 6, 8, 9, 10, 11, 17]
Sorting and de-duplication can also be done directly using, sets.
mylist = list(set(L)) # Collections automatically sort strings