Python을 사용한 빠른 정렬

퀵 정렬은 O(nlogn)의 시간 복잡도를 갖는 일반적으로 사용되는 정렬 알고리즘입니다. 실제 응용 프로그램에서 빠른 정렬은 일반적으로 다른 정렬 알고리즘보다 훨씬 빠릅니다. Python은 많은 내장 정렬 기능을 제공하지만 빠른 정렬을 이해하고 구현하는 것은 여전히 ​​중요합니다. 이번 글에서는 Python을 통해 Quick Sort 알고리즘을 구현해보겠습니다.

빠른 정렬은 피벗 값(피벗)을 선택한 다음 목록에서 피벗 값보다 작은 모든 요소를 ​​하위 목록에 배치하고 피벗 값보다 큰 모든 요소를 ​​다른 하위 목록에 배치하여 작동합니다. 그러면 두 개의 하위 목록이 재귀적으로 빠르게 정렬됩니다. 결국 모든 하위 목록은 재귀적으로 정렬된 다음 단일 정렬 목록으로 병합됩니다.

다음은 Python에서 빠른 정렬을 구현하는 코드입니다.

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

위 코드에서는 먼저 목록의 길이를 확인합니다. 목록 길이가 2보다 작으면 원래 목록을 반환합니다. 그렇지 않으면 목록의 첫 번째 요소를 피벗 값으로 선택합니다. 그런 다음 목록 내포를 사용하여 피벗 값보다 작거나 같은 요소를 하나의 목록에 넣고 피벗 값보다 큰 요소를 다른 목록에 넣습니다. 다음으로, 더 작은 목록과 더 큰 목록을 재귀적으로 정렬하고 정렬된 목록을 함께 연결합니다. 피벗 값은 연결된 목록의 중간에 배치됩니다.

이 알고리즘은 적합한 참조 번호를 선택해야 합니다. 선택한 기본 번호가 목록에서 가장 큰(또는 가장 작은) 값인 경우 재귀적으로 정렬된 하위 목록 크기는 1만 줄어듭니다. 이 경우 퀵소트 알고리즘의 시간복잡도는 O(n2)로 퇴화될 수 있다. 이를 방지하기 위해 기준값을 무작위로 선택하는 방법을 사용할 수 있습니다. 이 방법은 기본 값이 목록에서 가장 큰(또는 가장 작은) 값이 아닌 경우 평균적으로 재귀적으로 정렬된 하위 목록의 크기를 보장합니다.

다음은 벤치마크 값의 무작위 선택을 사용하는 Python 코드입니다.

import random

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    else:
        pivot_index = random.randint(0, len(arr) - 1)
        pivot = arr[pivot_index]
        less = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i <= pivot]
        greater = [i for i in arr[:pivot_index] + arr[pivot_index + 1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

위 코드에서는 먼저 random.randint() 함수를 사용하여 벤치마크 값을 무작위로 선택합니다. 그런 다음 기준 값보다 작거나 같은 요소를 하나의 목록에 넣고 기준 값보다 큰 요소를 다른 목록에 넣습니다. 이는 이전 구현과 유사합니다.

요약하자면, Python을 통해 퀵 정렬 알고리즘을 구현하고, 재귀적으로 정렬되는 하위 리스트의 크기 불균형을 피하기 위해 벤치마크 값을 무작위로 선택하는 방식을 사용했습니다. 이 알고리즘은 평균적인 상황에서 O(nlogn)의 시간 복잡도로 목록을 빠르게 정렬할 수 있는 분할 정복(Divide and Conquer) 아이디어를 기반으로 합니다.

위 내용은 Python을 사용한 빠른 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!