[CLRS] [7-3] A randomized quicksort

1. Randomized Quicksort

- 우리는 7-2 에서 Quicksort의 최악의 상황에 대해서 알아보았다.

- 최악의 상황 같은 경우 매순간마다 최대,최솟값을 고르게 되면 발생하게 되는데,

- 이를 최대한 방지하기 위해서 이 값을 뽑는것 자체를 random으로 뽑게되면

- 최댓,최솟값을 고르게 되는 상황이 극악으로 낮아지게 되며,

- 이미 정렬된 배열에서도 효율적으로 사용가능하다.

 

2. Code 

import random

def randomlized_quicksort(arr):
    if len(arr)<=1:
        return arr
    pivot = arr[random.randint(0,len(arr)-1)]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return randomlized_quicksort(left) + middle + randomlized_quicksort(right)

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

print(randomlized_quicksort(l))