파이썬으로 Quicksort

나는 파이썬에 완전히 익숙하지 않다. 그리고 나는 그것에 퀵 소트를 구현하려하고있다. 누군가 제 코드 작성을 도와 주시겠습니까?

3 개의 배열을 연결하여 인쇄하는 방법을 모르겠습니다.

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)

해결법

==============================

1.

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

==============================

2.추가 메모리가없는 빠른 정렬 (자리 표시)

추가 메모리가없는 빠른 정렬 (자리 표시)

용법:

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)

==============================

3.또 다른 간결하고 아름다운 버전이 있습니다.

또 다른 간결하고 아름다운 버전이 있습니다.

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!!!

자세한 내용은 위의 코드를 설명하겠습니다.

==============================
4.Google에서 "python quicksort implementation"을 검색하면이 질문이 가장 먼저 나타납니다. 나는 초기 문제가 "코드 수정에 도움이되었다"는 것을 이해하지만, 이미 그 요청을 무시한 많은 해답이있다. 현재 두 번째로 찬성표를 던진 하나의 맹목적 인 "You are fired"의견을 가진 끔찍한 한 줄짜리 주석이며 일반적으로 (즉, 입력 목록 크기에 비례하여 추가 메모리를 사용하는) 많은 구현이 필요합니다. 이 대답은 in-place 솔루션을 제공하지만 python 2.x를위한 것입니다. 그래서, 아래는 Rosetta Code의 in-place 솔루션에 대한 나의 해석을 따르며, Python 3에서도 잘 작동합니다.

Google에서 "python quicksort implementation"을 검색하면이 질문이 가장 먼저 나타납니다. 나는 초기 문제가 "코드 수정에 도움이되었다"는 것을 이해하지만, 이미 그 요청을 무시한 많은 해답이있다. 현재 두 번째로 찬성표를 던진 하나의 맹목적 인 "You are fired"의견을 가진 끔찍한 한 줄짜리 주석이며 일반적으로 (즉, 입력 목록 크기에 비례하여 추가 메모리를 사용하는) 많은 구현이 필요합니다. 이 대답은 in-place 솔루션을 제공하지만 python 2.x를위한 것입니다. 그래서, 아래는 Rosetta Code의 in-place 솔루션에 대한 나의 해석을 따르며, 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)
```
그리고 내부 속성을 버릴 용의가 있다면 아래는 quicksort의 기본 아이디어를 잘 보여주는 또 다른 버전입니다. 가독성을 제외하고는 다른 장점은 안정적이라는 것입니다 (동일한 요소는 정렬되지 않은 목록에 있던 것과 동일한 순서로 정렬 된 목록에 나타납니다). 이 안정성 속성은 위에 제시된 메모리 부족 배타적 인 내부 구현에서 유지되지 않습니다.
```
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
```

==============================

5.이미 이것에 대한 해답이 많이 있지만이 방법이 가장 깨끗한 구현이라고 생각합니다.

이미 이것에 대한 해답이 많이 있지만이 방법이 가장 깨끗한 구현이라고 생각합니다.

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]])

==============================
6.실생활에서 우리는 항상 파이썬이 제공하는 내장 된 정렬을 사용해야합니다. 그러나 퀵 정렬 알고리즘을 이해하는 것은 도움이됩니다.

실생활에서 우리는 항상 파이썬이 제공하는 내장 된 정렬을 사용해야합니다. 그러나 퀵 정렬 알고리즘을 이해하는 것은 도움이됩니다.

내 목표는 참조 자료로 돌아 가지 않고도 독자가 쉽게 이해하고 복제 할 수 있도록 주제를 분류하는 것입니다.

퀵 소트 알고리즘은 본질적으로 다음과 같습니다.

데이터가 무작위로 분포하는 경우 첫 번째 데이터 요소를 피벗으로 선택하면 임의 선택이됩니다.

먼저 주석과 변수 이름을 사용하여 중간 값을 가리키는 읽기 가능한 예제를 살펴 보겠습니다.
```
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
```
이제 그 사실을 알고 false라면 이전 요소를 반환하고, 그렇지 않으면 다음 요소를 평가하여 반환합니다.
```
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]]))
```
lambdas는 하나의 표현식을 반환하기 때문에 하나의 표현식으로 단순화했습니다 (읽을 수 없게되었지만). 이제는 람다를 사용할 수 있습니다.
```
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 분할 스키마를 사용합니다 (그러나 do-while 대신 while 루프 구문을 사용하고 partitioning () 호출로 네 번까지 중복 계산을 제거했습니다. 외부 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는 우리의 내장 시간 소트 알고리즘이 매우 효율적이고 재귀 한계가 있기 때문에 파이썬에서는 그다지 실용적이지 않습니다. list.sort를 사용하여 목록을 현재 위치에서 정렬하거나 정렬 된 새 정렬 목록을 만들 것을 기대합니다. 둘 다 키와 반대 인수를 사용합니다.

==============================

7.기능적 접근 :

기능적 접근 :

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)

==============================

8.기능적 프로그래밍 접근법

기능적 프로그래밍 접근법

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]

==============================
9.둘 다 여기에 답변을 원래의 질문에 대한 답변을 제공 한 목록에 대한 확인 작동하지만 생각한다면 고유 한 값이 아닌 배열을 전달하는 경우 중단됩니다. 그래서 완벽을 기하기 위해 각각의 작은 오류를 지적하고 오류를 수정하는 방법을 설명합니다.

둘 다 여기에 답변을 원래의 질문에 대한 답변을 제공 한 목록에 대한 확인 작동하지만 생각한다면 고유 한 값이 아닌 배열을 전달하는 경우 중단됩니다. 그래서 완벽을 기하기 위해 각각의 작은 오류를 지적하고 오류를 수정하는 방법을 설명합니다.

예를 들어 Brionius 알고리즘으로 다음 배열 [12,4,5,6,7,3,1,15,1] (1이 두 번 나타남)을 정렬하려고합니다. 어떤 시점에서는 더 적은 배열이 비어있게됩니다. 그리고 다음 반복과 len ()> 1에서 분리 할 수없는 값 쌍 (1,1)을 가진 등호 배열 ... 따라서 무한 루프로 끝날 것입니다

less가 비어있는 경우 배열을 반환하거나 zangw 대답처럼 같은 배열에서 sort를 호출하지 않는 것이 좋습니다.
```
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
```
더 멋진 솔루션도 중단되지만 다른 원인으로 인해 재귀 라인의 return 절이 누락되어 어느 시점에 None을 반환하고 목록에 추가하려고합니다.

그것을 고치려면 그 라인에 리턴을 추가하십시오.
```
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]])
```

==============================

10.

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 []

==============================

11.

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

==============================

12."실제"내부 구현 [Algorithm 8.9, 8.11, Michael T. Goodrich 및 Roberto Tamassia의 알고리즘 설계 및 응용 프로그램 북]

"실제"내부 구현 [Algorithm 8.9, 8.11, Michael T. Goodrich 및 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's 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()

==============================

13.이 알고리즘은 다음과 같은 간단한 4 단계로 구성됩니다.

이 알고리즘은 다음과 같은 간단한 4 단계로 구성됩니다.

파이썬에서 알고리즘에 대한 코드 :

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])

왼쪽과 오른쪽 부분으로이 알고리즘을 재귀 적으로 수행하십시오.

==============================
14.버전 Python 3.x의 경우 : 주로 가독성을 높이기 위해 연산자 모듈을 사용하는 기능 스타일입니다.

버전 Python 3.x의 경우 : 주로 가독성을 높이기 위해 연산자 모듈을 사용하는 기능 스타일입니다.
```
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))
```
다음과 같이 테스트됩니다.
```
print (qsort([3,1,4,2,5]) == [1,2,3,4,5])
```

==============================

15.

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)

==============================
16.파티션 - 작은 요소가 왼쪽으로 이동하고 큰 elemets가 오른쪽으로 이동하거나 그 반대로 피벗을 사용하여 배열을 분할합니다. 피벗은 배열의 임의 요소 일 수 있습니다. 이 알고리즘을 만들기 위해서는 배열의 시작과 끝 인덱스가 무엇인지, 피벗 (pivot)이 어디인지 알아야합니다. 그런 다음 두 개의 보조 포인터 L, R을 설정하십시오.

파티션 - 작은 요소가 왼쪽으로 이동하고 큰 elemets가 오른쪽으로 이동하거나 그 반대로 피벗을 사용하여 배열을 분할합니다. 피벗은 배열의 임의 요소 일 수 있습니다. 이 알고리즘을 만들기 위해서는 배열의 시작과 끝 인덱스가 무엇인지, 피벗 (pivot)이 어디인지 알아야합니다. 그런 다음 두 개의 보조 포인터 L, R을 설정하십시오.

그래서 우리는 배열 사용자 [..., 시작, ..., 끝, ...]

L 및 R 포인터의 시작 위치 [..., 시작, 다음, ..., 끝 ...] R L

L 사용자 [L]을 누른 다음 R을 하나 이동하고 사용자 [R]을 사용자 [L] 2. L을 하나 옮긴다.

사용자 [R]을 (를) 사용자 [피봇]과 바꾼 후,

빠른 정렬 - 피벗에 의한 분할의 모든 다음 부분이 끝 인덱스보다 크거나 같을 때까지 파티션 알고리즘을 사용하십시오.
```
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)
```
==============================
17.또는 파이썬에서 C / C ++ varags, lambda 식 및 if 식과 동일한 기능을하는 1 개의 라이너를 선호하는 경우 :

또는 파이썬에서 C / C ++ varags, lambda 식 및 if 식과 동일한 기능을하는 1 개의 라이너를 선호하는 경우 :
```
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])
```

==============================

18.나는 아래 코드를 붙이고있다! 이 퀵 소트는 피벗 값의 위치 때문에 훌륭한 학습 도구입니다. 그것은 일정한 장소에 있기 때문에, 당신은 여러 번 걸을 수 있고 실제로 그것이 어떻게 작동하는지 잠깐 살펴볼 수 있습니다. 실제로는 O (N ^ 2) 런타임을 피하기 위해 피벗을 무작위로 추출하는 것이 가장 좋습니다.

나는 아래 코드를 붙이고있다! 이 퀵 소트는 피벗 값의 위치 때문에 훌륭한 학습 도구입니다. 그것은 일정한 장소에 있기 때문에, 당신은 여러 번 걸을 수 있고 실제로 그것이 어떻게 작동하는지 잠깐 살펴볼 수 있습니다. 실제로는 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

==============================

19.

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

==============================

20.파티션 단계에서 인쇄 된 변수를 사용한 전체 예제 :

파티션 단계에서 인쇄 된 변수를 사용한 전체 예제 :

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))

==============================

21.또 다른 quicksort 구현 :

또 다른 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)

==============================

22.이것은 Hoare 파티션 방식을 사용하고 스왑 및 로컬 변수 수가 적은 퀵 소트의 버전입니다.

이것은 Hoare 파티션 방식을 사용하고 스왑 및 로컬 변수 수가 적은 퀵 소트의 버전입니다.

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)

==============================

23.다음은 쉬운 구현 방법입니다.

다음은 쉬운 구현 방법입니다.

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]))

==============================

24.

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))

==============================

25.

def quicksort(items):
    if not len(items) > 1:
        return items
    items, pivot = partition(items)
    return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot + 1:])


def partition(items):
    i = 1
    pivot = 0
    for j in range(1, len(items)):
        if items[j] <= items[pivot]:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i - 1], items[pivot] = items[pivot], items[i - 1]
    return items, i - 1

==============================

26.인레이 정렬

인레이 정렬

def qsort(a, b=0, e=None):
    # partitioning
    def part(a, start, end):
        p = start
        for i in xrange(start+1, end):
            if a[i] < a[p]:
                a[i], a[p+1] = a[p+1], a[i]
                a[p+1], a[p] = a[p], a[p+1]
                p += 1
        return p

    if e is None:
        e = len(a)
    if e-b <= 1: return

    p = part(a, b, e)
    qsort(a, b, p)
    qsort(a, p+1, e)

재귀없이 :

deq = collections.deque()
deq.append((b, e))
while len(deq):
    el = deq.pop()
    if el[1] - el[0] > 1:
        p = part(a, el[0], el[1])
        deq.append((el[0], p))
        deq.append((p+1, el[1]))

==============================
27.덜 동등한 세 가지 배열을 취한 다음 모든 것을 연결하는 대신 전통적인 개념 (분할 방법)을 시도해보십시오.

덜 동등한 세 가지 배열을 취한 다음 모든 것을 연결하는 대신 전통적인 개념 (분할 방법)을 시도해보십시오.

http://pythonplanet.blogspot.in/2015/08/quick-sort-using-traditional-partition.html

이것은 inbuilt 함수를 사용하지 않고 있습니다.

파티셔닝 기능 -
```
def partitn(alist, left, right):  
 i=left  
 j=right  
 mid=(left+right)/2   

pivot=alist[mid]  
while i <= j:  
    while alist[i] < pivot:  
        i=i+1   

    while alist[j] > pivot:  
        j=j-1   

    if i <= j:  
        temp = alist[i]  
        alist[i] = alist[j]  
        alist[j] = temp  
        i = i + 1   
        j = j - 1   
```
==============================
28.난 nums 라이브러리를 사용하여 quicksort 할 것입니다. 정말 유용한 라이브러리라고 생각합니다. 그들은 이미 빠른 정렬 방법을 구현했지만 사용자 정의 방법을 구현할 수도 있습니다.

난 nums 라이브러리를 사용하여 quicksort 할 것입니다. 정말 유용한 라이브러리라고 생각합니다. 그들은 이미 빠른 정렬 방법을 구현했지만 사용자 정의 방법을 구현할 수도 있습니다.
```
import numpy
array = [3,4,8,1,2,13,28,11,99,76] #The array what we want to sort

indexes = numpy.argsort( array , None, 'quicksort', None)
index_list = list(indexes)

temp_array = []

for index in index_list:
    temp_array.append( array[index])

array = temp_array

print array #it will show sorted array
```

from https://stackoverflow.com/questions/18262306/quicksort-with-python by cc-by-sa and MIT license

'PYTHON' 카테고리의 다른 글

[PYTHON] 파이썬에서 두 개의 사전 비교하기 (0)	2018.10.03
[PYTHON] HttpResponse를 장고로 스트리밍하는 법 (0)	2018.10.03
[PYTHON] IP가 파이썬 2.x에서 네트워크에 있는지 어떻게 확인할 수 있습니까? (0)	2018.10.03
[PYTHON] id () 함수는 무엇을 위해 사용됩니까? (0)	2018.10.03
[PYTHON] 파이썬에서는 YAML 매핑을 OrderedDicts로 어떻게로드 할 수 있습니까? (0)	2018.10.03

복붙노트

[PYTHON] 파이썬으로 Quicksort

파이썬으로 Quicksort

해결법

1.

2.추가 메모리가없는 빠른 정렬 (자리 표시)

3.또 다른 간결하고 아름다운 버전이 있습니다.

5.이미 이것에 대한 해답이 많이 있지만이 방법이 가장 깨끗한 구현이라고 생각합니다.

6.실생활에서 우리는 항상 파이썬이 제공하는 내장 된 정렬을 사용해야합니다. 그러나 퀵 정렬 알고리즘을 이해하는 것은 도움이됩니다.

7.기능적 접근 :

8.기능적 프로그래밍 접근법

10.

11.

12."실제"내부 구현 [Algorithm 8.9, 8.11, Michael T. Goodrich 및 Roberto Tamassia의 알고리즘 설계 및 응용 프로그램 북]

13.이 알고리즘은 다음과 같은 간단한 4 단계로 구성됩니다.

14.버전 Python 3.x의 경우 : 주로 가독성을 높이기 위해 연산자 모듈을 사용하는 기능 스타일입니다.

15.

17.또는 파이썬에서 C / C ++ varags, lambda 식 및 if 식과 동일한 기능을하는 1 개의 라이너를 선호하는 경우 :

19.

20.파티션 단계에서 인쇄 된 변수를 사용한 전체 예제 :

21.또 다른 quicksort 구현 :

22.이것은 Hoare 파티션 방식을 사용하고 스왑 및 로컬 변수 수가 적은 퀵 소트의 버전입니다.

23.다음은 쉬운 구현 방법입니다.

24.

25.

26.인레이 정렬

27.덜 동등한 세 가지 배열을 취한 다음 모든 것을 연결하는 대신 전통적인 개념 (분할 방법)을 시도해보십시오.

28.난 nums 라이브러리를 사용하여 quicksort 할 것입니다. 정말 유용한 라이브러리라고 생각합니다. 그들은 이미 빠른 정렬 방법을 구현했지만 사용자 정의 방법을 구현할 수도 있습니다.

'PYTHON' 카테고리의 다른 글

티스토리툴바