![]()
Selection 이번에는 '선택'과 관련한 문제입니다. 만약 어떤 배열에서 '최소/최대'의 값을 구해야 한다면 배열을 한 번만 쭉 훑으면서 최소/최대의 값을 저장하면 되기 때문에 선형 시간이 필요할 것입니다. 즉, N만큼의 시간이 소요되죠. 하지만 배열에서 k번째의 값을 구하려면 이는 단순히 한 번 훑어보는 것으로 판단할 수 있는 문제가 아니게 됩니다. 정렬 후 k번째 값을 가져오면 되지만 이는 linearithmic, 즉 NlogN만큼의 시간이 필요한 작업입니다. 뭔가 비슷한듯 비슷하지 않은 두 방식에 대해서, 후자도 선형 시간으로 처리할 수 있지 않을까? 라는게 과거 학자들의 궁금증이었습니다. Quick-select import random def partition(a, lo, hi): i, j =..
![]()
Quicksort 퀵정렬의 기본 개념은 다음과 같습니다. 우선 배열을 무작위로 섞고, 좌우 구간으로 나눕니다. 하나(i)는 왼쪽에서 오른쪽으로 이동하고, 나머지(j)는 오른쪽에서 왼쪽으로 이동합니다. i는 기준(partitioning element)보다 큰 값이 나오면, j는 기준보다 작은 값이 나오면 이동을 멈춥니다. 두 값을 교환합니다. 위 과정을 반복합니다. 퀵정렬은 합병 정렬이 그 자체로 수행되기 전에 분할하는 것과 달리, 퀵정렬은 분할마다 정렬이 수행된다는 차이점이 있습니다. Quicksort partitioning demo Quicksort: Java code for partitioning, Java implementation def partition(a, lo, hi): i, j = lo, ..
