Quick jump with Python

Question

I am completely new to python and I am trying to implement quicksort in it. Can someone please help me fill out my code?

I do not know how to combine the three arrays and print them.

def sort(array=[12,4,5,6,7,3,1,15]): less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) if x == pivot: equal.append(x) if x > pivot: greater.append(x) sort(less) sort(pivot) sort(greater) 

Answer 1

 def sort(array=[12,4,5,6,7,3,1,15]): """Sort the array by using quicksort.""" less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) elif x == pivot: equal.append(x) elif x > pivot: greater.append(x) # Don't forget to return something! return sort(less)+equal+sort(greater) # Just use the + operator to join lists # Note that you want equal ^^^^^ not pivot else: # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array. return array 

Answer 2

Quick sorting without additional memory (in place)

Using:

 array = [97, 200, 100, 101, 211, 107] quicksort(array) # array -> [97, 100, 101, 107, 200, 211] 

 def partition(array, begin, end): pivot = begin for i in xrange(begin+1, end+1): if array[i] <= array[begin]: pivot += 1 array[i], array[pivot] = array[pivot], array[i] array[pivot], array[begin] = array[begin], array[pivot] return pivot def quicksort(array, begin=0, end=None): if end is None: end = len(array) - 1 def _quicksort(array, begin, end): if begin >= end: return pivot = partition(array, begin, end) _quicksort(array, begin, pivot-1) _quicksort(array, pivot+1, end) return _quicksort(array, begin, end) 

Answer 3

There is another concise and beautiful version.

 def qsort(arr): if len(arr) <= 1: return arr else: return qsort([x for x in arr[1:] if x < arr[0]]) + \ [arr[0]] + \ qsort([x for x in arr[1:] if x >= arr[0]]) # this comment is just to improve readability due to horizontal scroll!!! 

Let me explain the codes above for details.

1. select the first element of arr[0] as pivot

   [arr[0]]

2. qsort those array elements that are smaller than pivot, with List Comprehension

   qsort([x for x in arr[1:] if x < arr[0]])

3. qsort those array elements that are larger than pivot, with List Comprehension

   qsort([x for x in arr[1:] if x >= arr[0]])

Answer 4

If I search for “quick python sort” in Google, this question will be the first result. I understand that the initial question was to “help fix the code”, but there are many answers that do not take this request into account: the second is currently the second vote , a terrible one-line with a fun comment “You are fired” and, in general, many implementations that are not in place (i.e., use additional memory in proportion to the size of the input data list). This answer provides an in-place solution, but it is intended for python 2.x So, here follows my interpretation of the in-place solution from Rosetta Code, which is also excellent python 3 for python 3 :

 import random def qsort(l, fst, lst): if fst >= lst: return i, j = fst, lst pivot = l[random.randint(fst, lst)] while i <= j: while l[i] < pivot: i += 1 while l[j] > pivot: j -= 1 if i <= j: l[i], l[j] = l[j], l[i] i, j = i + 1, j - 1 qsort(l, fst, j) qsort(l, i, lst) 

And if you are ready to give up ownership on the spot, the following is another version that better illustrates the basic ideas related to quick sorting. Besides readability, its other advantage is that it is stable (equal items appear in the sorted list in the same order in which they were used in the unsorted list). This stability property is not satisfied with the smaller amount of memory implemented in the place presented above.

 def qsort(l): if not l: return l # empty sequence case pivot = l[random.choice(range(0, len(l)))] head = qsort([elem for elem in l if elem < pivot]) tail = qsort([elem for elem in l if elem > pivot]) return head + [elem for elem in l if elem == pivot] + tail 

Answer 5

There are many answers to this already, but I think this approach is the purest implementation:

 def quicksort(arr): """ Quicksort a list :type arr: list :param arr: List to sort :returns: list -- Sorted list """ if not arr: return [] pivots = [x for x in arr if x == arr[0]] lesser = quicksort([x for x in arr if x < arr[0]]) greater = quicksort([x for x in arr if x > arr[0]]) return lesser + pivots + greater 

You can, of course, skip storing everything in variables and immediately return them as follows:

 def quicksort(arr): """ Quicksort a list :type arr: list :param arr: List to sort :returns: list -- Sorted list """ if not arr: return [] return quicksort([x for x in arr if x < arr[0]]) \ + [x for x in arr if x == arr[0]] \ + quicksort([x for x in arr if x > arr[0]]) 

Answer 6

Quick jump with Python

In real life, we should always use the built-in sorting provided by Python. However, understanding the quicksort algorithm is instructive.

My goal here is to break the topic in such a way that it is easy to understand and reproduce by the reader, without returning to reference materials.

The quicksort algorithm is essentially the following:

1. Select a summary point.
2. Move all data points smaller (lower) than the rotation axis to a position below the rotation axis - move those that are greater than or equal to (higher) the rotation axis to a position above it.
3. Apply the algorithm to areas above and below the pivot point

If the data is distributed randomly, selecting the first data point, since the bar is equivalent to random selection.

Readable example:

First, let's look at a readable example that uses comments and variable names to indicate intermediate values:

 def quicksort(xs): """Given indexable and slicable iterable, return a sorted list""" if xs: # if given list (or tuple) with one ordered item or more: pivot = xs[0] # below will be less than: below = [i for i in xs[1:] if i < pivot] # above will be greater than or equal to: above = [i for i in xs[1:] if i >= pivot] return quicksort(below) + [pivot] + quicksort(above) else: return xs # empty list 

To repeat the algorithm and code described here, we move the values ​​above the pivot point to the right and the values ​​below the pivot point to the left, and then pass these sections to the same function for further sorting.

Golfed:

It can be golf up to 88 characters:

 q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]]) 

To see how we get there, first take our readable example, delete comments and docstrings and find the anchor point in place:

 def quicksort(xs): if xs: below = [i for i in xs[1:] if i < xs[0]] above = [i for i in xs[1:] if i >= xs[0]] return quicksort(below) + [xs[0]] + quicksort(above) else: return xs 

Now find lower and higher in place:

 def quicksort(xs): if xs: return (quicksort([i for i in xs[1:] if i < xs[0]] ) + [xs[0]] + quicksort([i for i in xs[1:] if i >= xs[0]])) else: return xs 

Now, knowing this and returns the previous element, if false, otherwise, if it is true, it evaluates and returns the next element, we have:

 def quicksort(xs): return xs and (quicksort([i for i in xs[1:] if i < xs[0]] ) + [xs[0]] + quicksort([i for i in xs[1:] if i >= xs[0]])) 

Since lambdas returns a single click, and we simplified one expression (even if it becomes more unreadable), we can now use lambda:

 quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] ) + [xs[0]] + quicksort([i for i in xs[1:] if i >= xs[0]])) 

And to shorten our example, reduce the names of functions and variables to one letter and eliminate spaces that are not required.

 q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]]) 

Please note that this lambda, like most golf games, is pretty bad.

QuickSort in place using the Hoare splitting scheme

The preliminary implementation creates many unnecessary additional lists. If we can do this locally, we will avoid losing space.

The implementation below uses the Hoare partitioning scheme, which you can learn more about Wikipedia about (but we apparently deleted up to 4 redundant calculations on the partition() call, using the while-loop semantics instead of do-while and moving the narrowing steps to the end of the outer while loop.).

 def quicksort(a_list): """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort""" def _quicksort(a_list, low, high): # must run partition on sections with 2 elements or more if low < high: p = partition(a_list, low, high) _quicksort(a_list, low, p) _quicksort(a_list, p+1, high) def partition(a_list, low, high): pivot = a_list[low] while True: while a_list[low] < pivot: low += 1 while a_list[high] > pivot: high -= 1 if low >= high: return high a_list[low], a_list[high] = a_list[high], a_list[low] low += 1 high -= 1 _quicksort(a_list, 0, len(a_list)-1) return a_list 

Not sure if I checked it thoroughly enough:

 def main(): assert quicksort([1]) == [1] assert quicksort([1,2]) == [1,2] assert quicksort([1,2,3]) == [1,2,3] assert quicksort([1,2,3,4]) == [1,2,3,4] assert quicksort([2,1,3,4]) == [1,2,3,4] assert quicksort([1,3,2,4]) == [1,2,3,4] assert quicksort([1,2,4,3]) == [1,2,3,4] assert quicksort([2,1,1,1]) == [1,1,1,2] assert quicksort([1,2,1,1]) == [1,1,1,2] assert quicksort([1,1,2,1]) == [1,1,1,2] assert quicksort([1,1,1,2]) == [1,1,1,2] 

Conclusion

This algorithm is often taught in computer science courses and is asked for in an interview for an interview. It helps us think about recursion and divide and win.

Quicksort is not very practical in Python, as our built-in timsort algorithm is quite efficient, and we have recursion limits. We would expect sorting lists in place with list.sort or creating new sorted lists with sorted - both of which accept key and reverse arguments.

Answer 7

functional approach:

 def qsort(list): if len(list) < 2: return list pivot = list.pop() left = filter(lambda x: x <= pivot, list) right = filter(lambda x: x > pivot, list) return qsort(left) + [pivot] + qsort(right) 

Answer 8

functional programming aproach

 smaller = lambda xs, y: filter(lambda x: x <= y, xs) larger = lambda xs, y: filter(lambda x: x > y, xs) qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else [] print qsort([3,1,4,2,5]) == [1,2,3,4,5] 

Answer 9

I think that both answers here work fine for the provided list (which answers the original question), but will break if an array containing non-unique values ​​is passed. Therefore, for completeness, I would simply point out a small error in each and explain how to fix them.

For example, try sorting the following array [12,4,5,6,7,3,1,15,1] (note that 1 appears twice) with Brionius . At some point, the less array and the equal array will end with a pair of values ​​(1,1) that cannot be divided at the next iteration and len ()> 1 ... therefore, you get an infinite loop

You can fix it either by returning the array if it is less empty or better not causing the sorting in your equal array, as in zangw answer

 def sort(array=[12,4,5,6,7,3,1,15]): less = [] equal = [] greater = [] if len(array) > 1: pivot = array[0] for x in array: if x < pivot: less.append(x) if x == pivot: equal.append(x) if x > pivot: greater.append(x) # Don't forget to return something! return sort(less)+ equal +sort(greater) # Just use the + operator to join lists # Note that you want equal ^^^^^ not pivot else: # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array. return array 

Fancier's solution also breaks, but for another reason there is no return clause in the recursive string, which at some point will return None and try to add it to the list ....

To fix this, just add a return to this line

 def qsort(arr): if len(arr) <= 1: return arr else: return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]]) 

Answer 10

Separation . Dividing an array into an axis where smaller elements move to the left and larger elements move to the right or vice versa. A rod may be a random element from an array. To make this algorithm, we need to know what the initial and final index of the array is, and where is the code. Then set the two auxiliary pointers L, R.

So, we have a user of the array [..., begin, ..., end, ...]

The starting position of the L and R pointers
[..., start, next, ..., end ...]
R L

whereas L <end
1. If user [pivot]> user [L] moves R by one and replaces user [R] with user [L]
2. move L one

After the user swap [R] with the user [pivot]

Quick sorting . Use the partition algorithm until each subsequent part of the axis break begins to index more or equal to the end of the index.

 def qsort(user, begin, end): if begin >= end: return # partition # pivot = begin L = begin+1 R = begin while L < end: if user[begin] > user[L]: R+=1 user[R], user[L] = user[L], user[R] L+= 1 user[R], user[begin] = user[begin], user[R] qsort(user, 0, R) qsort(user, R+1, end) tests = [ {'sample':[1],'answer':[1]}, {'sample':[3,9],'answer':[3,9]}, {'sample':[1,8,1],'answer':[1,1,8]}, {'sample':[7,5,5,1],'answer':[1,5,5,7]}, {'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]}, {'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]}, {'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]}, {'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]}, {'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]}, {'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]} ] for test in tests: sample = test['sample'][:] answer = test['answer'] qsort(sample,0,len(sample)) print(sample == answer) 

Answer 11

Or, if you prefer a single line, which also illustrates the equivalent of Python C / C ++ varags, lambda expressions and if statements:

 qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x]) 

Answer 12

 def quick_sort(array): return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \ + quick_sort([x for x in array[1:] if x >= array[0]]) if array else [] 

Answer 13

 def Partition(A,p,q): i=p x=A[i] for j in range(p+1,q+1): if A[j]<=x: i=i+1 tmp=A[j] A[j]=A[i] A[i]=tmp l=A[p] A[p]=A[i] A[i]=l return i def quickSort(A,p,q): if p<q: r=Partition(A,p,q) quickSort(A,p,r-1) quickSort(A,r+1,q) return A 

Answer 14

The "true" implementation in place [Algorithms 8.9, 8.11 from the book of designing and applying algorithms by Michael T. Goodrich and Roberto Tamassia]:

 from random import randint def partition (A, a, b): p = randint(a,b) # or mid point # p = (a + b) / 2 piv = A[p] # swap the pivot with the end of the array A[p] = A[b] A[b] = piv i = a # left index (right movement ->) j = b - 1 # right index (left movement <-) while i <= j: # move right if smaller/eq than/to piv while A[i] <= piv and i <= j: i += 1 # move left if greater/eq than/to piv while A[j] >= piv and j >= i: j -= 1 # indices stopped moving: if i < j: # swap t = A[i] A[i] = A[j] A[j] = t # place pivot back in the right place # all values < pivot are to its left and # all values > pivot are to its right A[b] = A[i] A[i] = piv return i def IpQuickSort (A, a, b): while a < b: p = partition(A, a, b) # p is pivot location #sort the smaller partition if p - a < b - p: IpQuickSort(A,a,p-1) a = p + 1 # partition less than p is sorted else: IpQuickSort(A,p+1,b) b = p - 1 # partition greater than p is sorted def main(): A = [12,3,5,4,7,3,1,3] print A IpQuickSort(A,0,len(A)-1) print A if __name__ == "__main__": main() 

Answer 15

The algorithm has 4 simple steps:

• Divide the array into 3 different parts: left, right and right, where pivot will have only one element. We select this rotation element as the first element of the array.
• Add elements to the appropriate part by comparing them with the rotation element. (explanation in comments)
• Repeat this algorithm until all array elements are sorted.
• Finally attach left + pivot + right parts

Code for the algorithm in python:

 def my_sort(A): p=A[0] #determine pivot element. left=[] #create left array right=[] #create right array for i in range(1,len(A)): #if cur elem is less than pivot, add elem in left array if A[i]< p: left.append(A[i]) #the recurssion will occur only if the left array is atleast half the size of original array if len(left)>1 and len(left)>=len(A)//2: left=my_sort(left) #recursive call elif A[i]>p: right.append(A[i]) #if elem is greater than pivot, append it to right array if len(right)>1 and len(right)>=len(A)//2: # recurssion will occur only if length of right array is atleast the size of original array right=my_sort(right) A=left+[p]+right #append all three part of the array into one and return it return A my_sort([12,4,5,6,7,3,1,15]) 

Perform this algorithm recursively with the left and right sides.

Answer 16

Another implementation of quicksort:

 # A = Array # s = start index # e = end index # p = pivot index # g = greater than pivot boundary index def swap(A,i1,i2): A[i1], A[i2] = A[i2], A[i1] def partition(A,g,p): # O(n) - just one for loop that visits each element once for j in range(g,p): if A[j] <= A[p]: swap(A,j,g) g += 1 swap(A,p,g) return g def _quicksort(A,s,e): # Base case - we are sorting an array of size 1 if s >= e: return # Partition current array p = partition(A,s,e) _quicksort(A,s,p-1) # Left side of pivot _quicksort(A,p+1,e) # Right side of pivot # Wrapper function for the recursive one def quicksort(A): _quicksort(A,0,len(A)-1) A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1] print(A) quicksort(A) print(A) 

Answer 17

For Python version 3.x : a functional style using the operator module, primarily to improve readability.

 from operator import ge as greater, lt as lesser def qsort(L): if len(L) <= 1: return L pivot = L[0] sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])] return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater)) 

and tested as

 print (qsort([3,1,4,2,5]) == [1,2,3,4,5]) 

Answer 18

 def quick_sort(self, nums): def helper(arr): if len(arr) <= 1: return arr #lwall is the index of the first element euqal to pivot #rwall is the index of the first element greater than pivot #so arr[lwall:rwall] is exactly the middle part equal to pivot after one round lwall, rwall, pivot = 0, 0, 0 #choose rightmost as pivot pivot = arr[-1] for i, e in enumerate(arr): if e < pivot: #when element is less than pivot, shift the whole middle part to the right by 1 arr[i], arr[lwall] = arr[lwall], arr[i] lwall += 1 arr[i], arr[rwall] = arr[rwall], arr[i] rwall += 1 elif e == pivot: #when element equals to pivot, middle part should increase by 1 arr[i], arr[rwall] = arr[rwall], arr[i] rwall += 1 elif e > pivot: continue return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:]) return helper(nums) 

Answer 19

This is a quicksort version using the Hoare partition scheme and with fewer swaps and local variables

 def quicksort(array): qsort(array, 0, len(array)-1) def qsort(A, lo, hi): if lo < hi: p = partition(A, lo, hi) qsort(A, lo, p) qsort(A, p + 1, hi) def partition(A, lo, hi): pivot = A[lo] i, j = lo-1, hi+1 while True: i += 1 j -= 1 while(A[i] < pivot): i+= 1 while(A[j] > pivot ): j-= 1 if i >= j: return j A[i], A[j] = A[j], A[i] test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14] print quicksort(test) 

Answer 20

I know that many people answered this question correctly, and I liked reading them. My answer is almost the same as that of zangw, but I think that the previous authors did not explain very well how everything actually works ... so I will try to help others who may visit this question / answers in the future about a simple solution for implement quick sorting.

How it works?

1. Essentially, we select the first element as our bar from our list, and then create two sublists.
2. Our first sublist contains items that are smaller than pivot
3. Our second sublist contains our elements that are greater than or equal to pivot
4. Then we quickly sort each of them and combine the first group + summary + second group to get the final result.

Here is an example along with visual accompaniment ... (summary) 9,11,2,0

average: n log n

worst case: n ^ 2

The code:

 def quicksort(data): if (len(data) < 2): return data else: pivot = data[0] # pivot #starting from element 1 to the end rest = data[1:] low = [each for each in rest if each < pivot] high = [each for each in rest if each >= pivot] return quicksort(low) + [pivot] + quicksort(high) 

items = [9,11,2,0] print (quick sort (items))

Answer 21

The algorithm contains two boundaries, one of which has elements smaller than the pivot point (tracked by the index "j"), and the other has elements larger than the pivot point (tracked by the index "i").

At each iteration, the new element is processed by increasing j.

Invariant: -

1. all the elements between the rod and i are smaller than the rod, and
2. all elements between i and j are larger than the anchor point.

If the invariant is violated, the ith and jth elements are interchanged, and I increases.

After all the elements have been processed, and all after the summary has been split, the summary element is replaced with the last element less than it.

The rotation element will now be at its right place in the sequence. Elements before it will be smaller than it, and elements after it will be larger than it, and they will not be sorted.

 def quicksort(sequence, low, high): if low < high: pivot = partition(sequence, low, high) quicksort(sequence, low, pivot - 1) quicksort(sequence, pivot + 1, high) def partition(sequence, low, high): pivot = sequence[low] i = low + 1 for j in range(low + 1, high + 1): if sequence[j] < pivot: sequence[j], sequence[i] = sequence[i], sequence[j] i += 1 sequence[i-1], sequence[low] = sequence[low], sequence[i-1] return i - 1 def main(sequence): quicksort(sequence, 0, len(sequence) - 1) return sequence if __name__ == '__main__': sequence = [-2, 0, 32, 1, 56, 99, -4] print(main(sequence)) 

Axis selection

A “good” turn will result in two subsequences of approximately the same size. Deterministically, the rotation element can be selected in a naive way or by calculating the median of the sequence.

A naive implementation of axis selection will be the first or last element. In this case, the worst-case execution time will be when the input sequence is already sorted or sorted in reverse order, since one of the subsequences will be empty, which will remove only one element per recursive call.

Perfectly balanced separation is achieved when the axis is the median element of the sequence. There are an equal number of elements more than this and less than this. This approach guarantees a better overall operating time, but requires much more time.

A non-deterministic / random way to select an axis will be to select an element randomly. This is a simple and easy approach that minimizes the worst case scenario and also results in a roughly balanced split. This will also provide a balance between the naive approach and the middle approach by choosing a hinge.

Answer 22

• pivot_value,
• while, while, ,
• , , , . , , ,
• split_point

! - - . , , . , O (N ^ 2).

 def quicksort10(alist): quicksort_helper10(alist, 0, len(alist)-1) def quicksort_helper10(alist, first, last): """ """ if first < last: split_point = partition10(alist, first, last) quicksort_helper10(alist, first, split_point - 1) quicksort_helper10(alist, split_point + 1, last) def partition10(alist, first, last): done = False pivot_value = alist[first] leftmark = first + 1 rightmark = last while not done: while leftmark <= rightmark and alist[leftmark] <= pivot_value: leftmark = leftmark + 1 while leftmark <= rightmark and alist[rightmark] >= pivot_value: rightmark = rightmark - 1 if leftmark > rightmark: done = True else: temp = alist[leftmark] alist[leftmark] = alist[rightmark] alist[rightmark] = temp temp = alist[first] alist[first] = alist[rightmark] alist[rightmark] = temp return rightmark 

Answer 23

 def quick_sort(l): if len(l) == 0: return l pivot = l[0] pivots = [x for x in l if x == pivot] smaller = quick_sort([x for x in l if x < pivot]) larger = quick_sort([x for x in l if x > pivot]) return smaller + pivots + larger 

Answer 24

:

 def partition(data, p, right): print("\n==> Enter partition: p={}, right={}".format(p, right)) pivot = data[right] print("pivot = data[{}] = {}".format(right, pivot)) i = p - 1 # this is a dangerous line for j in range(p, right): print("j: {}".format(j)) if data[j] <= pivot: i = i + 1 print("new i: {}".format(i)) print("swap: {} <-> {}".format(data[i], data[j])) data[i], data[j] = data[j], data[i] print("swap2: {} <-> {}".format(data[i + 1], data[right])) data[i + 1], data[right] = data[right], data[i + 1] return i + 1 def quick_sort(data, left, right): if left < right: pivot = partition(data, left, right) quick_sort(data, left, pivot - 1) quick_sort(data, pivot + 1, right) data = [2, 8, 7, 1, 3, 5, 6, 4] print("Input array: {}".format(data)) quick_sort(data, 0, len(data) - 1) print("Output array: {}".format(data)) 

Answer 25

: -

 def quicksort(array): if len(array) < 2: return array else: pivot= array[0] less = [i for i in array[1:] if i <= pivot] greater = [i for i in array[1:] if i > pivot] return quicksort(less) + [pivot] + quicksort(greater) print(quicksort([10, 5, 2, 3])) 

Answer 26

 def is_sorted(arr): #check if array is sorted for i in range(len(arr) - 2): if arr[i] > arr[i + 1]: return False return True def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index if right - left < 1: #if we have empty or one element array - nothing to do return else: left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer while left_point <= right_point: #while we have not checked all elements in the given array swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot if swap_left and swap_right: #if both True we can swap elements under left and right pointers arr[right_point], arr[left_point] = arr[left_point], arr[right_point] left_point += 1 right_point -= 1 else: #if only one True we don't have place for to swap it if not swap_left: #if we dont need to swap it we move to next element left_point += 1 if not swap_right: #if we dont need to swap it we move to prev element right_point -= 1 arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot) qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot) def main(): import random arr = random.sample(range(1, 4000), 10) #generate random array print(arr) print(is_sorted(arr)) qsort_in_place(arr, 0, len(arr) - 1) print(arr) print(is_sorted(arr)) if __name__ == "__main__": main() 

Answer 27

 # 编程珠玑实现# 双向排序: 提高非随机输入的性能# 不需要额外的空间,在待排序数组本身内部进行排序# 基准值通过random随机选取# 入参: 待排序数组, 数组开始索引 0, 数组结束索引 len(array)-1 import random def swap(arr, l, u): arr[l],arr[u] = arr[u],arr[l] return arr def QuickSort_Perl(arr, l, u): # 小数组排序i可以用插入或选择排序# if ul < 50 : return arr # 基线条件: low index = upper index; 也就是只有一个值的区间if l >= u: return arr # 随机选取基准值, 并将基准值替换到数组第一个元素swap(arr, l, int(random.uniform(l, u))) temp = arr[l] # 缓存边界值, 从上下边界同时排序i, j = l, u while True: # 第一个元素是基准值,所以要跳过i+=1 # 在小区间中, 进行排序# 从下边界开始寻找大于基准值的索引while i <= u and arr[i] <= temp: i += 1 # 从上边界开始寻找小于基准值的索引# 因为j肯定大于i, 所以索引值肯定在小区间中while arr[j] > temp: j -= 1 # 如果小索引仍小于大索引, 调换二者位置if i >= j: break arr[i], arr[j] = arr[j], arr[i] # 将基准值的索引从下边界调换到索引分割点swap(arr, l, j) QuickSort_Perl(arr, l, j-1) QuickSort_Perl(arr, j+1, u) return arr print('QuickSort_Perl([-22, -21, 0, 1, 2, 22])', QuickSort_Perl([-22, -21, 0, 1, 2, 22], 0, 5)) 

Answer 28

.

N len(N) > 0 . K = [N] .

Note. .

 def BinaryRip2Singletons(K, S): K_L = [] K_P = [ [K[0][0]] ] K_R = [] for i in range(1, len(K[0])): if K[0][i] < K[0][0]: K_L.append(K[0][i]) elif K[0][i] > K[0][0]: K_R.append(K[0][i]) else: K_P.append( [K[0][i]] ) K_new = [K_L]*bool(len(K_L)) + K_P + [K_R]*bool(len(K_R)) + K[1:] while len(K_new) > 0: if len(K_new[0]) == 1: S.append(K_new[0][0]) K_new = K_new[1:] else: break return K_new, S N = [16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1] K = [ N ] S = [] print('K =', K, =', S) while len(K) > 0: K, S = BinaryRip2Singletons(K, S) print('K =', K, =', S) 

:

 K = [[16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]] S = [] K = [[11, 15, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1], [16], [16], [19]] S = [] K = [[10, 4, 10, 5, 2, 3, 4, 7, 1], [11], [15, 12, 14], [16], [16], [19]] S = [] K = [[4, 5, 2, 3, 4, 7, 1], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [] K = [[2, 3, 1], [4], [4], [5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [] K = [[5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4] K = [[15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11] K = [[12, 14], [15], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11] K = [] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11, 12, 14, 15, 16, 16, 19] 

Answer 29

 def quicksort(arr): if len(arr) < 2: return arr #base case else: pivot = arr[0] less = [i for i in arr[1:] if i <= pivot] more = [i for i in arr[1:] if i > pivot] return quicksort(less) + [pivot] + quicksort(more) 

Answer 30

 def quick_sort(list): if len(list) ==0: return [] return quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ] + quick_sort( filter( lambda item: item > list[0], list))