| [ QuizWit ] in KIDS 글 쓴 이(By): lunaris (+가짜집시+) 날 짜 (Date): 2000년 6월 29일 목요일 오전 10시 23분 21초 제 목(Title): Re: 퀵 소트보다 빠른 알고리듬이 있나요? comparison based sorting은 information boundary O(nlogn)을 넘어갈 수 없습 니다. non-comparison based sorting은 O(n)이 한계가 되겠죠..(일반적인 von Neumann architecture를 이용한 경우에 한함. Optical Hardware를 이용하여 O(1)로 sorting이 된다는 논문은 읽은 적이 있음) quick sorting 보다 빠른 sorting이라고 주장하는 sorting은 전에 좀 찾아본적 이 있는데, k-sort라는 넘이 있는것 같습니다. 이게 complexity가 O(nlogn)이 라고도 하고 O(n) 이라고도 하는데 아마도 전자일 가능성이 높은듯. O(n) 짜리 로는 radix sorting이 대표주자이고 (짜서 실험해봤는데 32bit integer 500만 개 짜리를 sorting하는데 한 두배정도 빠르더군요) flash-sort라는 넘이 역시 O(n)입니다. 원리는 자세히 안 읽어봤는데 소스는 무진장 간단합니다. 뭔가 학문적인 욕심이 아니시라면야 quick sorting이 가장 무난한듯 합니다. 운명을 따라 영원의 종족들은 스러져가고 일루바타르의 어린 자식들은 별빛 속을 헤엄쳐 내일로 향한다 내 이름은 가짜집시, Silda-raano Lunaris |