[ARGORITHM]ソート

ソース。

## 퀵 정렬
# 왼쪽 데이터는 피봇보다 크고, 오른쪽 데이터는 피봇보다 작아야
# 퀵 정렬은 재귀로 -> 계속분할이 일어남
# 분할은 pivot과 right의 원소가 바뀌는것

array= [5, 7, 9, 0, 3, 1 ,6 ,2 ,4 ,8]

def quick_sort(array, start, end):
    if start >= end : # 원소 1개인 경우 종료
        return
    pivot = start # 피봇 첫번째 원소
    left = start +1
    right = end

    # 분할 기준 왼 < 오 위치 안바뀌는 경우
    while(left <= right):
        # 피봇보다 큰 데이터 찾을 때까지 , 
        while(left<= end and array[left] <= array[pivot]):
            left += 1

        # 피봇보다 작은 데이터 찾을 때까지
        while (right>start and array[right]>= array[pivot]):
            right -= 1

        # 엇갈렸다면, 작은 데이터와 피봇 교체
        if(left > right):
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행 , pivot <-> right
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)

quick_sort(array , 0, len(array)-1)
print(array)

ドレッシング2パイジャー麺~

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0] # 피봇은 첫 번째 원소
    tail = array[1:] # 피봇ㅇ르 제외한 리스트

    # 기존 방법과 다르게 
    left_side = [x for x in tail if x<= pivot]  # 분할된 왼쪽
    right_side = [x for x in tail if x> pivot]

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬, 전체 리스트 반화
    return quick_sort(left_side)+ [pivot] + quick_sort(right_side)

print(quick_sort(array))

ソート数