[알고리즘 일기] 14. 퀵 정렬(1)

문제 14. (2021-05-14)

 

퀵 정렬(1)

퀵 정렬의 partition 함수를 작성하세요. partition 함수는 리스트 my_list, 그리고 partition할 범위를 나타내는 인덱스 start와 인덱스 end를 파라미터로 받습니다. my_list의 값들을 pivot 기준으로 재배치한 후, pivot의 최종 위치 인덱스를 리턴해야 합니다.

 

 

❧ 테스트 셋

# 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 function
def partition(my_list, start, end):
   # Code



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

 

❧ 출력 예시

[4, 3, 2, 1, 5, 6, 7]
4

 

---

❧ 정답

# 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 function
def partition(my_list, start, end):
   p = end
   b = start
   for i in range(start, end):
      if my_list[i] <= my_list[p]:
         swap_elements(my_list, b, i)
         b += 1
   swap_elements(my_list, b, p)
   return b



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