I wrote a note for myself about Quicksort.
--A high-speed sorting algorithm based on the divide-and-conquer method that can handle large data sizes. --Computational complexity is O (nlogn) --Because there are logn layers and the amount of calculation for each layer is O (n). --Unstable sorting that changes the order of the same values when sorting --No need for memory to temporarily store data
quick_sort.py
def partition(A, p, r):
x = A[r-1]
i = p-1
for j in range(p, r-1):
if A[j] <= x:
i += 1
A[i], A[j] = A[j], A[i]
A[i+1], A[r-1] = A[r-1], A[i+1]
return i+1
n = int(input())
A = list(map(int, input().split()))
def quick_sort(A, p, r):
if p < r:
q = partition(A, p, r)
quick_sort(A, p, q)
quick_sort(A, q+1, r)
return A
print(quick_sort([3, 1, 10, 2.5, 11, 3, 21,4, -1], 0, 9))
# [-1, 1, 2.5, 3, 3, 4, 10, 11, 21]
The above algorithm has a constant selection of criteria (the last value), so it may be inefficient depending on the data sequence. Computational complexity may be O (n ^ 2) The recursion may be too deep and an error may occur Therefore, it is necessary to devise ways to randomly select the criteria, select the median, and so on.
Sort algorithm and implementation in Python
Recommended Posts