[코드잇 divide and Conquer] 퀵소트 python

쿽소트.py

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    tmp = my_list[index1]
    my_list[index1] = my_list[index2]
    my_list[index2] = tmp
    return my_list


# 퀵 정렬에서 사용되는 partition 함수
# 파티션 로직은 예술이다... 볼때마다 곱씹어보기~
def partition(my_list, start, end):
  
    b = 0 //big이 시작되는 인덱스
    i = 0 //확인되지 않은 인덱스
    p = end //피벗 인덱스

    for i in range(0, p):
        if my_list[p] < my_list[i]:
            pass
        else:
            swap_elements(my_list, b, i)
            b += 1
            i += 1

    swap_elements(my_list, b, p)
    return b

    #divine
    #conquer
    #combine

# 퀵 정렬
def quicksort(my_list, start, end):
    # 코드를 작성하세요.
    merge_index = 0
    merge_index = partition(my_list,start,end)

    #baseCase는 1개 남앗을때 자신리턴하면됨
    if merge_index == start:
        return my_list

    #divine 부분 
    quicksort(my_list,0,merge_index-1 )#피벗 기준으로 왼쪽것을 다시 quicksort한다
    quicksort(my_list,merge_index,end)#피벗 기준 오른쪽을 다시 quicksort한다
    
    #combine 
    #사실상 컴바인 부분이 필요없다 왜냐하면 이미 파티션을 거치면 정렬이 되어있는 배열이 되어있기때문
    너무 깔끔하고







# 테스트 1
list1 = [1, 3, 5, 7, 9, 11, 13, 11]
quicksort(list1, 0, len(list1) - 1)
print(list1)

# 테스트 2
list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
quicksort(list2, 0, len(list2) - 1)
print(list2)

# 테스트 3
list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]
quicksort(list3, 0, len(list3) - 1)
print(list3)