퀵 정렬(quick sort)

퀵 정렬

퀵 정렬은 합병 정렬과 같이 분할 정복 알고리즘의 종류중 하나로 기준값(pivot) 을 두어 기준값 보다 작으면 왼쪽 크면 오른쪽에 정렬하는 방식의 알고리즘 이다.

 

시간복잡도

평균: O(n log n)

최악: O(n2) -> 배열이 이미 정렬되 있거나 역순으로 정렬될경우

 

 

import random
def quick_sort(li,start,end):
    l = start #시작을 왼쪽 인덱스에 저장
    r = end #마지막을 오른쪽 인덱스에 저장 
    pivot = li[int((l+r)/2)] #배열의 중간값을 피벗으로 설정
    while l <= r: # 왼쪽인덱스가 오른쪽 인덱스보다 커지기 전까지 실행
        while li[l] < pivot: # 왼쪽값이 피벗값보다 커지거나 같으면(피벗값이 가장 클경우 대비) 종료
            l = l+1 # 종료전까지 인덱스를 증가시킴
        while li[r] > pivot: #오른쪽값이 피벗보다 작거나 같으면(피벗값이 가장 작을경우 대비) 종료
            r = r-1 #종료전까지 인덱스를 감소시킴
        if l <= r: # 만약 왼쪽 인덱스가 오른쪽인덱스보다 작은경우 왼쪽값이 오른쪽 값보다 크므로
            swap(li,l,r) # 오른쪽과 왼쪽을 변경
            l = l+1 #이미 변경된 값들이므로 다음 비교를 위해
            r = r-1 #왼쪽을 증가시키고 오른쪽을 감소시킴
    print(li)
    if l < end: #만약 왼쪽인덱스가 마지막보다 작다면 비교할 부분이 남아있으므로
        quick_sort(li,l,end) #start = 왼쪽인덱스 end = 마지막을 매개변수로 넘겨 재귀호출 실행
    if r > start:#만약 오른쪽 인덱스가 시작보다 클 경우 비교할 부분이 남아있으므로
        quick_sort(li,start,r)#start =시작 end = 오른쪽인덱스를 매개변수로 넘겨 재귀호출 실행

def swap(li,idx1,idx2): #list 의 idx1과 idx2를 변경하는 메서드
    temp = li[idx1]
    li[idx1] = li[idx2]
    li[idx2] = temp  

arr1 = []
n = random.randint(1,100)
for i in range(10):
    while n in arr1:#중복제거
        n = random.randint(1,100)
    arr1.append(n) #1~100 무작위 숫자 생성 후 리스트에 추가

quick_sort(arr1,0,len(arr1)-1)
print("최종결과")
print(arr1)

 

 

실행결과

[38, 21, 54, 43, 8, 32, 62, 94, 10, 97]
[8, 21, 54, 43, 38, 32, 62, 94, 10, 97]
[8, 21, 10, 32, 38, 43, 62, 94, 54, 97]
[8, 21, 10, 32, 38, 43, 54, 94, 62, 97]
[8, 21, 10, 32, 38, 43, 54, 62, 94, 97]
[8, 21, 10, 32, 38, 43, 54, 62, 94, 97]
[8, 10, 21, 32, 38, 43, 54, 62, 94, 97]
[8, 10, 21, 32, 38, 43, 54, 62, 94, 97]
최종결과
[8, 10, 21, 32, 38, 43, 54, 62, 94, 97]