algorithm

Question 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)
            sort(less)
            sort(pivot)
            sort(greater)

Question 2

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

Question 3

추가 메모리없이 빠른 정렬 (제자리에 있음)

용법:

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)

Question 4

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

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 Comprehension

qsort([x for x in arr[1:] if x < arr[0]])
qsort 피벗보다 큰 배열 요소 List Comprehension

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

Question 5

이 답변 은 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

Question 6

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인수를 사용합니다.

Question 7

이미 이에 대한 많은 답변이 있지만이 접근 방식이 가장 깔끔한 구현이라고 생각합니다.

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

Question 8

기능적 접근 :

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)