여러가지 Sorting 알고리즘들에서 가장 최근에 발표된것
글쓴이: rgbi3307 / 작성시간: 금, 2010/12/03 - 2:58오후
위키피디아(www.wikipedia.org)에서 Sorting에 관한 정보를 검색해보니,
아래와 같이 다양한 종류들이 나오는데, 이들중 가장 최근에 발표된 Sorting 알고리즘이
Library sort라고 하는군요(2004년~2006년에 발표).
이 알고리즘의 프로그램 코드(혹은 슈도코드)는 찾지를 못했는데, 어디 나와있는 곳이 있을까요?
Bubble sort
Selection sort
Insertion sort
Shell sort
Comb sort
Merge sort
Heapsort
Quicksort
Library sort
...
Counting Sort
Bucket sort
Radix sort
Distribution sort
Forums:
뭔가 재미있는 정렬 방법 같아서 찾아보았습니다. 아래
뭔가 재미있는 정렬 방법 같아서 찾아보았습니다.
아래 사이트 보면, Library Sort의 pseudo code와 논문을 볼 수 있네요.
http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm
논문은 FUN04 컨퍼런스에서 발표되고, 06년도에 Theory of Computing Systems 저널에도 올랐나 보네요.
06년도 논문을 보려면 구입하셔야 할 것 같습니다.
너무 감사합니다.
공유해 주신 링크를 들어가 봤는데, Sorting에 관한 내용들이 소스코드와 함께 많이 정리되어 있더군요.
특히, Library Sort에 관한 코드도 있어서 봤는데, 생각보다 길이가 길더군요.
단순히 Insertion Sort의 단점을 보완한 것이라 생각했는데, 복잡한듯합니다.
그런데, Library Sort 저자들의
(Michael A Bender, Martin Farach-Colton, Miguel Mosteiro 2004)
의도를 100% 반영하지 못했고, 안정화(stable)하지 못한 코드라는 언급도 있는듯합니다.
저자들의 논문을 잠깐 봤는데, 수학수식으로 가득차 있어서 난해합니다(^^).
알고리즘은 이해하고 나면 별것이 아닌데,
설명하는 과정들이 수학수식으로 되어 있어 더 어렵게 느껴지는듯 합니다.
암튼, 학계에서는 수학을 잘하면 많은 도움이 될듯합니다.
자기가 연구한 내용을 수학식으로 논리적으로 설명하고 증명도 해야 하니까요.
공부는 끝이 없는듯...
공유해 주신것 감사합니다. 즐거운 통신시간 되세요~
From 알지비(rgbi3307(at)nate.com) in the www.kernel.bz
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))