[알고리즘 일기] 15. 퀵 정렬(2)

문제 15. (2021-05-15)

 

퀵 정렬(2)

Divide and Conquer 방식으로 quicksort 함수를 써 보세요. quicksort는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 인덱스 start와 인덱스 end를 받습니다.

merge_sort 함수와 달리 quicksort 함수는 정렬된 새로운 리스트를 리턴하는 게 아니라, 파라미터로 받는 리스트 자체를 정렬시키는 것입니다.

 

 

❧ 테스트 셋

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 fuction
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

# quicksort function
def quicksort(my_list, start, end):
	# Code

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

 

❧ 출력 예시

[1, 3, 5, 7, 9, 11, 11, 13]

 

---

❧ 정답

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 fuction
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

# quicksort function
def quicksort(my_list, start, end):
    if start == end:
        return my_list
    divide = partition(my_list, start, end)
    return quicksort(my_list, start, divide - 1) + quicksort(my_list, divide, end)

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