퀵정렬 (Quick sort)

책을 보고 이해하는데 시간이 걸렸는데 보다보니 세상에 이렇게 깔끔할 수가 있나 싶어서 여기에다가도 남긴다.

 

C와 C#을 하면서 for문의 틀에 좀 갖혀있는 느낌이었는데 다른 언어지만 재귀를 이용하면 깔끔하게 쓸 수 있구나 싶다.

def quicksort(array):
    if len(array)<2:    #원소가 2개 미만이라면 array로 반환
        return array
    else:
        pivot=array[0]    #array의 0번째 원소를 기준(pivot, 중심)으로 삼음
        less=[i for i in array[1:] if i<= pivot]    #지정한 배열의 1번째 원소부터 i가 pivot과 같거나 작으면 less 배열로 지정

        greater=[i for i in array[1:] if i>pivot]    #지정한 배열의 1번째 원소가 i가 pivot과 크다면 greadter의 배열로 지정

        return quicksort(less)+[pivot]+quicksort(greater)    #피봇을 기준으로 두고 정렬 후 함수에 반복

print(quicksort([1,15,2,7,3,13]))    #결과 확인용 프린트

퀵정렬의 요지는 중심이 될 원소를 하나 정하고 그것을 중심으로 나눠 각자 정렬 함으로서 빠르게 정렬시키는 것이다.

 

운 좋게 첫 원소가 중앙값과 가깝게 잡히면 엄청 빨라지는 거고 운이 나빠도 일반 정렬과 속도 차이는 없을 것이다. 

 

지금 보는 책은 쉬운 책이라는데 나는 읽을 때마다 내용이 달라지는거 같다.