Partition
-
#퀵정렬 #Quick_sort_1단계 #Divide하기Data miner 2019. 7. 11. 14:56
퀵 정렬의 핵심 아이디어? 파티션(partition)이란 리스트를 나누는 것을 의미한다. 퀵 정렬을 리스트에 있는 특정값을 기준으로 좌, 우 파티션 한다. 이후 좌, 우에 놓인 값들을 각각 정렬하여 합치게 되면 전체적으로 정렬이 된 리스트를 얻을 수 있다. 이 방식을 재귀적으로 적용한다. 즉, 좌, 우로 나뉜 부분들을 더 이상 나눌 수 없을 때까지 나눈다. 어떤 값 기준으로 나누고자할 때, 나누고자 하는 부분의 개수가 1개일 때 더이상 나눌 수 없는 상태가 된다. 퀵 정렬에서 가장 어려운 것이 파티션부분(Divide)이다. 리스트에서 나눠야할 그룹에 속한 숫자들을 차례로 기준점(pivot)과 비교하면서 작으면 작은 그룹에, 크면 큰 그룹에 넣도록한다. 이 때, 각 그룹에 속한 숫자들은 정렬되어 있지 않다..