1. 적당한 크기의 테이블을 준비함  table[10000] , search[]



2. 링크드리스트에서 노드(또는 튜플)가 가지고있는 원소는 몫,count  두개고, count는 0으로 초기화


3. 들어온  value 를  10000으로 나눈 뒤에 그 나머지를 키값으로 하는 위치에 몫을 추가하고 count에 1을 더함


4. 만약 해당 위치에 이미 값이 있다면 링크드리스트로 collision을 해결하는데, 이 때 몫의 크기순서대로 정렬하면서 추가함.


5. 만약 몫이  search array에 없는 새로운 몫이라면 search array에 몫을 크기순서대로 정렬하면서 추가함


6. 모든 수를 다 기준에 맞춰 테이블에 넣은 뒤에 search array의 길이만큼  table array 를 순회하는데,   몫이  search array에 있는 경우만 순회함.


7. 예를들어 search array에 0 3 5 7이 있다고 하면 몫이 0,3,5,7인 경우에서만 탐색을 수행함




이런식으로 되었다면


table의 키 10000개에 대해


head를 돌면서


값을 input과 동일한 크기의 array에 추가함.


키가 150이고 몫이 0이고 count가 2이므로, 150두개를 결과에 추가함


키가 371이고 몫이 0이고 count가 1이므로, 371하나를 결과에 추가함


만약  count가 0이면 head를 pop한다.


이런식으로 몫이 0, 3, 5, 7인 경우에 대해 순회하므로


150 150 371 30150 35555 50150 70150 순서대로 정렬함.




이런 정렬의 경우 Table의 크기를 k라고 하면


ideal한 경우 O(k*n) == O(n)만큼의 복잡도가 나옴. (몫이 모두 0인 경우) / 계수정렬과 동일


하지만 모든 값이 서로 다른 몫을 가지는 경우라면(최악의 경우)


O((k+1/2)*n^2+n/2)==O(n^2)만큼의 복잡도가 나옴.(n개의 값이 서로 다른 n개의 몫을 가지면 + k를 n번 순회하므로)


근데 실제로 그냥 계산해보면 최악의 경우에는  O(sizeof(search)*k+n)임.


가장 최악의 경우는 int형식의 입력만 주어졌는데


key하나당 단 하나의 값만 들어와서 213000개의 값을 받은 경우 result에 결과를 넣기위한 탐색을 sizeof(search)*k만큼 수행함 최대값은 21억임.


해시의 원리를 이용하기 때문에, 대부분의 연산이 독립적으로 이루어지고, 오로지 key와 collision횟수, search의 size가 연산속도에 영향을 미치는 정렬임


대신 공간을 매우매우매우 많이 씀



이런방식의 정렬있음?