나는 완전히 파이썬을 처음 접했고 그것에 퀵 정렬을 구현하려고 노력하고 있습니다. 누군가 내 코드를 완성하도록 도와 주시겠습니까?
세 배열을 연결하고 인쇄하는 방법을 모르겠습니다.
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)
답변
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
답변
추가 메모리없이 빠른 정렬 (제자리에 있음)
용법:
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)
답변
또 다른 간결하고 아름다운 버전이 있습니다.
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!!!
자세한 내용은 위 코드를 설명하겠습니다.
-
배열의 첫 번째 요소
arr[0]를 피벗으로 선택[arr[0]] -
qsort피벗보다 작은 배열 요소List Comprehensionqsort([x for x in arr[1:] if x < arr[0]]) -
qsort피벗보다 큰 배열 요소List Comprehensionqsort([x for x in arr[1:] if x >= arr[0]])
답변
이 답변 은 Python 2.x. 내 대답은에서의 적절한 솔루션의 해석이다 로제타 코드 작동 Python 3도 :
import random
def qsort(xs, fst, lst):
'''
Sort the range xs[fst, lst] in-place with vanilla QuickSort
:param xs: the list of numbers to sort
:param fst: the first index from xs to begin sorting from,
must be in the range [0, len(xs))
:param lst: the last index from xs to stop sorting at
must be in the range [fst, len(xs))
:return: nothing, the side effect is that xs[fst, lst] is sorted
'''
if fst >= lst:
return
i, j = fst, lst
pivot = xs[random.randint(fst, lst)]
while i <= j:
while xs[i] < pivot:
i += 1
while xs[j] > pivot:
j -= 1
if i <= j:
xs[i], xs[j] = xs[j], xs[i]
i, j = i + 1, j - 1
qsort(xs, fst, j)
qsort(xs, i, lst)
그리고 당신이 in-place 속성을 기꺼이 포기하고 싶다면, 아래는 quicksort의 기본 아이디어를 더 잘 보여주는 또 다른 버전입니다. 가독성 외에도 다른 장점은 안정적 이라는 것입니다 (정렬되지 않은 목록에서 사용했던 것과 동일한 순서로 정렬 된 목록에 동일한 요소가 나타남). 이 안정성 속성은 위에 제시된 메모리 사용량이 적은 내부 구현에서는 유지되지 않습니다.
def qsort(xs):
if not xs: return xs # empty sequence case
pivot = xs[random.choice(range(0, len(xs)))]
head = qsort([x for x in xs if x < pivot])
tail = qsort([x for x in xs if x > pivot])
return head + [x for x in xs if x == pivot] + tail
답변
Python을 사용한 Quicksort
실생활에서 우리는 항상 파이썬이 제공하는 내장 정렬을 사용해야합니다. 그러나 퀵 정렬 알고리즘을 이해하면 도움이됩니다.
여기서 나의 목표는 참조 자료로 돌아 가지 않고도 독자가 쉽게 이해하고 복제 할 수 있도록 주제를 분류하는 것입니다.
퀵 정렬 알고리즘은 기본적으로 다음과 같습니다.
- 피벗 데이터 포인트를 선택합니다.
- 피벗보다 작은 (아래) 모든 데이터 포인트를 피벗 아래의 위치로 이동-피벗보다 크거나 같은 (위) 데이터 포인트를 그 위의 위치로 이동합니다.
- 피벗 위와 아래 영역에 알고리즘 적용
데이터가 무작위로 분포되어있는 경우 첫 번째 데이터 포인트를 피벗으로 선택하는 것은 무작위 선택과 동일합니다.
읽을 수있는 예 :
먼저 주석과 변수 이름을 사용하여 중간 값을 가리키는 읽기 쉬운 예를 살펴 보겠습니다.
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
여기에 설명 된 알고리즘과 코드를 다시 설명하기 위해 피벗 위의 값을 오른쪽으로 이동하고 피벗 아래의 값을 왼쪽으로 이동 한 다음 해당 파티션을 동일한 함수에 전달하여 추가 정렬합니다.
골프 :
88 자까지 입력 할 수 있습니다.
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]])
어떻게 거기에 도달하는지 확인하려면 먼저 읽을 수있는 예제를 사용하고 주석과 독 스트링을 제거하고 제자리에서 피벗을 찾습니다.
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
이제 아래 및 위, 제자리에서 찾으십시오.
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
이제 andfalse이면 이전 요소 를 반환하고 그렇지 않으면 true이면 다음 요소를 평가하고 반환합니다.
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]]))
람다는 단일 epression을 반환하고 단일 표현식으로 단순화되었으므로 (더 읽을 수 없게 되더라도) 이제 람다를 사용할 수 있습니다.
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]]))
그리고 우리의 예제로 줄이려면 함수와 변수 이름을 한 글자로 줄이고 필요하지 않은 공백을 제거하십시오.
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]])
대부분의 코드 골프와 마찬가지로이 람다는 다소 나쁜 스타일입니다.
Hoare 파티셔닝 구성표를 사용하는 내부 Quicksort
이전 구현은 불필요한 추가 목록을 많이 만듭니다. 제자리에서이 작업을 수행 할 수 있다면 공간 낭비를 피할 수 있습니다.
아래 구현은 Hoare 파티셔닝 체계를 사용하며, 위키피디아에서 더 자세히 읽을 수 있습니다 (하지만 partition()do-while 대신 while-loop 의미 체계를 사용하고 축소 단계를 끝으로 이동하여 호출 당 최대 4 개의 중복 계산을 제거했습니다. 외부 while 루프.).
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
충분히 철저히 테스트했는지 확실하지 않습니다.
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]
결론
이 알고리즘은 컴퓨터 과학 과정에서 자주 가르치고 면접에서 요청됩니다. 재귀와 분할 정복에 대해 생각하는 데 도움이됩니다.
Quicksort는 내장 된 timsort 알고리즘이 매우 효율적이고 재귀 제한이 있기 때문에 Python에서 그다지 실용적이지 않습니다 . 우리는 목록을 제자리에서 정렬 list.sort하거나sorted 할 수 있습니다. 둘 다 a key및 reverse인수를 사용합니다.
답변
이미 이에 대한 많은 답변이 있지만이 접근 방식이 가장 깔끔한 구현이라고 생각합니다.
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
물론 모든 것을 변수에 저장하는 것을 건너 뛰고 다음과 같이 즉시 반환 할 수 있습니다.
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]])
답변
기능적 접근 :
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)
