알고리즘의 시작 정렬 알고리즘(sort Algorithm) 4. 퀵 정렬

 

 

 

안녕하세요

오늘은 퀵정렬입니다.

이름에도 써 있듯 퀵(quick)하게 정렬 됩니다.

이해하는데 한참 걸렸어요 ㅜㅜ 시작해보겠습니다.

 

퀵정렬

---

분할해서 정렬한다고 생각하시면 되는데

 

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

 

퀵정렬에서는 피봇값을 하나 잡습니다. 여기서는 첫번째 것을 잡아볼게요

 

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

 

왼쪽에는 아무것도 없으니 그대로 두고

오른쪽 부분에서

오른쪽으로 이동하면서 나보다 큰값을 찾고

왼쪽으로 이동하면서 나보다 작은 값을 찾습니다.

 

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

 

나보다 큰 값은 10이 될 것이고 작은 값은 없고 다시 나에게로 오게 됩니다.

이렇게 엇갈렸을 때는 작은 값과 피봇값을 바꿔 줍니다.

 

자기 자신을 바꾸는 것이니 그대로

 

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

 

10을 피봇값으로 정하고 하게 되면 

역시 왼쪽은 그대로 두고 오른쪽을 보면

피봇보다 큰 값은 못찾고 작은 값은 9를 바로 찾게되죠

엇갈렸습니다. 두개를 바꿔주면

 

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

 

피봇값은 그대로 인덱스 1이고

 

같은 과정을 반복하면 

 

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

 

코드로 표현해보면

def quickSort(data,start,end):
    
    key = start
    i = start + 1
    j = end

    
    if(start>=end):
        return 
    
    while(i <= j): #엇갈릴 때까지
        while(i <= end and data[i] <= data[key]):
            i+=1
        while(data[j]>=data[key] and j>start):
            j-=1


        if(i>j):
            temp = data[j]
            data[j] = data[key]
            data[key] = temp
        else:
            temp = data[j]
            data[j] = data[i]
            data[i] = temp
    
    print(lst, start,j,end)
    
    quickSort(data,start,j-1)
    quickSort(data,j+1,end)

lst = [1,10,5,8,7,6,4,3,2,9]
quickSort(lst,0,len(lst)-1)
print(lst)

이렇게 됩니다.

제가 동빈나님 걸 보고 코딩을 했는데 동빈나 님은 C를 이용해서 하시기 때문에 파이썬은 다를까?

해서 찾아봤더니....

 

def quickSort2(lst):

    if(len(lst)<2):
        return lst

    pivot = lst[len(lst)//2] #임의의 피봇값
    less,more,equal = [],[],[]

    for i in lst:
        if(i>pivot):
            more.append(i)
        elif(i<pivot):
            less.append(i)
        elif(i==pivot):
            equal.append(i)

    return quickSort2(less) + equal + quickSort2(more)


if __name__ == "__main__":
    lst = [1,10,5,8,7,6,4,3,2,9]
    print(quickSort2(lst))

이렇게나 간단하게 가능하더라구요....

좀 현타온게 아직 제가 파이썬이 많이 부족하다는걸 깨달았어요.. ㅜ3ㅜ

 

 

 

오늘은 여기까지!

태클은 언제나 환영입니다!