[python] (divide and conquer) 퀵 정렬

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


# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의
    i = start
    b = start
    p = end

    # 범위안의 모든 값들을 볼 때까지 반복문을 돌린다
    while i < p:
        # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
        i += 1

    # b와 기준점인 p 인덱스에 있는 값들을 바꿔준다
    swap_elements(my_list, b, p)
    p = b

    # pivot의 최종 인덱스를 리턴해 준다
    return p

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    # 코드를 작성하세요.   
    change=my_list[index1]
    my_list[index1] = my_list[index2]
    my_list[index2] = change


# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 코드를 작성하세요.
    i=0 # unknown
    b=0 # big
    piviot = my_list[end]

    for i in range(end):
        compare_num = my_list[i]
        # 비교 숫자가 piviot 보다 큰경우
        if compare_num >= piviot :
            i+=1
        else:
            swap_elements(my_list, b , i )
            b+=1
            i+=1
    swap_elements(my_list, b , end)

    return b


# 테스트 1
list1 = [4, 3, 6, 2, 7, 1, 5]
pivot_index1 = partition(list1, 0, len(list1) - 1)
print(list1)
print(pivot_index1)

# 테스트 2
list2 = [6, 1, 2, 6, 3, 5, 4]
pivot_index2 = partition(list2, 0, len(list2) - 1)
print(list2)
print(pivot_index2)

 

위쪽은 모범 답안/ 아래쪽은 직접 작성한코드. 

저번에 알고리즘 풀면서 인덱스 전부를 돌지 않고 시간 복잡도를 줄이기 위해서 o(n) 으로 비교하기 위해서 

index 들을 i와 j 로 지정해두고 비교하면서 i와 j의 숫자를 변경해 갈 때가 있었는데 

이번에 퀵정렬을 배우면서 또 나왔다. 

 

예전에 배운 것들이 이렇게 유사하게 나올 때 마다 이해하기도 쉽고 확실히 공부했던게 도움이 되는 것 같다. 경험치먹는다는게 이런기분이구나.

 

모범답안과 내가 다른점은 나는 for 문을 사용했다는 점이고 모범답안은 while 문을 사용했다는 점이다. 

그리고 강의를 직독직해 하고 쓴지라 i+=1 이 중복된다면 if 문 바깥으로 빼서 하는게 좋다는점 

자주 하는 실수? 같은 것인데 고치기가 쉽지않다. 다 써놓고 한번더 확인 할 때 빼주도록하자. 

이외에는 별다른 실수는 없었던 것 같다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ이제 퀵정렬에서 가장 어렵다고 생각되는 부분인 divide 만 해주면된다. (강의에서 그렇다고한다)