Twinparadox Factory

외부정렬(External Sort)은 입력 크기가 매우 커 읽고 쓰기가 오래 걸리는 보조 기억 장치에저장할 수밖에 없는 상태에서 수행되는 정렬이다.통상적으로 주기억장치에서 다룰 수 있는 크기의 데이터를 다루던기존의 정렬은 내부정렬(Internal Sort)로 분류한다. 예를 들어, 주기억 장치 용량이 1GB라면, 데이터의 크기가 극단적으로 128GB라고 하자.이런 경우에는 주기억 장치에 데이터를 모두 올릴 수는 없는 상황이라어떤 내부 정렬 알고리즘으로도 직접 정렬할 수는 없어 보조기억장치(HDD,SDD)를 이용해야 한다. 그렇다면 이제 입력을 분할해 주기억 장치가 수용 가능한 만큼의 데이터에 대해내부 정렬을 수행하고 다시 이를 저장하는 방법을 반복하여,점진적으로 크기를 늘려나가는 방식을 고려해야 한다.내..

Algorithm] Quick Select(K번째 숫자 탐색) 정렬되지 않은 숫자들을 입력 받고 K번째로 작은 숫자를 찾는 방법을 떠올리자면,가장 먼저 떠오르는 것이 정렬한 후에 바로 접근하는 것을 생각해볼 수 있다. 통상 퀵 정렬이나 합병 정렬을 통해서 정렬을 수행하면 시간 복잡도가 O(nlogn)이고,이후 탐색에서의 시간 복잡도는 O(1)로 결과적으로 O(nlogn)의 시간 복잡도를 예상해볼 수 있다.이보다 좀 더 효율적인 것을 찾아볼 수는 없을까? 정렬 중에서 가장 빠른 성능을 보이는, 퀵정렬을 한 번 살펴볼 필요가 있다.퀵정렬은 피봇(pivot)을 선정하여 피봇을 기준으로 분할한 정보를 또 다시 피봇으로 나누는분할 정복 과정을 통해서 정렬을 이루는 방법이다. 여기서 이 피봇에 주목할 필요가 있다...

대학교 때 과제로 제출했던 기억이 있다.퀵 정렬을 진행하면서 정렬의 매 패스마다 high, low를 출력하도록 하는 거였다.혹여 자료구조 과제를 하면서 골치 아파할 대학생들을 위해 올려놓는다.생능출판에서 나온 'C언어로 쉽게 풀어쓴 자료 구조(개정판)'라는 책이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #define SWAP(a,b) {int t; t=a; a=b; b=t;}// 배열의 크기int n;void PrintSit(int list[], int high, ..