STL의 sort, stable_sort 알고리즘 분석 및 고찰(왜 이렇게 복잡한 걸까??) 2009/06/11 16:35 [Construction/C++ & STL] STL에 구현된 sort()와 stable_sort()을 알아보기 전에 간략하게 sort의 종류와 시간복잡도에 대해서 설명을 해보도록 하겠다. sort 알고리즘에는 insertion sort, bubble sort, quick sort,... 등 다양한 종류가 있다. 일반적으로 sort 알고리즘을 구분하면 아래와 같이 시간복잡도로 구분을 할 수 있다. O(n^2): insertion sort, bubble sort, selection sort, ... O(nlogn): quick sort, merge sort ... O(n): radix ..

보통 알고리즘 강의에서 NlogN 이런식으로 얼버무리는 경우가 많은 데,,, 이런 부분들을 자세히 밝혔다. 물론 수학을 좀 알아야 수월하게 이해할 것이다.

위키디피아에서 두 링크가 있는데, 하나는 Intro Sort 고안한 사람의 발표 논문이고 다른 하나는 아래의 자료인 데 대학교 연구자료인 듯 하다. ralph unden .net home bio flickr twitter misc A guide to Introsort My university, BA Stuttgart, has every IT student do a student research project spanning over the 5th and 6th semester. I applied for a topic that is close to basic informatics. The topic I chose and luckily was assigned to, is the implementation a..

아래는 기존 퀵소트 핵심 코드 중의 일부분이다. while(TRUE){ while(arr[left] pv) --right; //

// 재귀함수 void __stdcall QuickSort(int *arr, int n) { int left, right; int pv, t; // 갯수가 2 이상이면 if(n > 1){ // 피벗 결정 pv=arr[n-1]; // 좌우 인덱스 설정 및 비교, 교환 left=0; right=n-2; while(TRUE){ while(arr[left] pv) --right; // 시작 인덱스보다 작거나 같으면 값 조사 필요 없다. if(left >= right) break; t=arr[left]; arr[left]=arr[right]; arr[right]=t; ++left; --right; } // 피벗 자리와 left 자리 교환 ..

스택이나 큐를 사용하면 재귀함수를 non재귀함수로 만들 수 있다. 이전에는 스택을 이용하여 html 소스를 추출하는 것을 만들어 보았다. 이번에는 큐를 사용하여 파일을 찾는 함수를 작성해 보았다. (이재규 c++ 알고리즘도 좀 참고했다.) 연결리스트 자체가 이미 큐로서 충분히 기능할 수 있으므로 별도의 큐 클래스를 만들지 않았다. 큐 클래스로 별도로 구성하면 아무래도 쓸데없는 부분까지 구성해야 하므로 더 번거로운 작업이 될 수 있다. 단순 연결리스트를 생성하고 큐의 put, get 등 기본적 개념을 이용하였다. // 큐를 이용해 Non Recursive 함수로 구성해 봄. // 큐의 경우 FIFO 구조이므로 상위디렉부터 검사하고 하위로 차근차근 검사해나가는 파일탐색에 적용할 수 있다. // 트리의 lev..

자료구조, 알고리즘 둘러보다가 퍼뜩 떠올라서 구성해 보았다. 스택을 이용하니 노재귀형태로 구성할 수 있었다. 재귀의 오버플로우는 뭐 요즘같이 스레드에 할당되는 기본 스택이 1메가? 정도되는 상태에서 웬만큼 흘리는 코딩을 하지 않으면 거의 발생할 일이 없겠지만서두,,, 이와 별도로 하나의 함수에서 기타 처리를 모두 할 수 있으니 깔끔해진 듯 하다. 이전에 재귀 형태로 돌리는 경우 기타 처리를 하려면 보통 재귀함수 + 기타처리를 하는 함수,,, 2개로 구성하는 경우가 많았다. // 재귀함수 사용하지 않고 스택으로 해결 // 연결리스트 스택으로 구성한다. // 이 함수 성공시 호출부에서는 사용하고 난 후 결과값을 잊지말고 free해줘야 된다. LPWSTR __stdcall GetHtmlSourceNoRecur..