한빛미디어

(저번에 올린 질문은 해결되어서 삭제했습니다. )

독학하는 중이라 물어볼데도 없어서 올립니다. ( 답변좀 빨리 해주셨으면 하는 바램이 ㅜㅜ)

5장 콩쥐 되보기 해봤는데요 (3만개 정렬하기)

속도차를 보고 싶어서 clock()으로 속도를 재보았는데

버블정렬 퀵정렬 해보니 확연히 속도차이를 알수 있었고

헌데 문제가..

1. 버블정렬은 항시 같은 수의 비교를 한다고 해서 2번 연속 돌려보았는데
(정렬되어 있으면 비교수행하지 않게 하지 않았음에도)
처음 정렬 때보다 그 이후가 훨씬 빨랐습니다. 거의2배정도.
변수에 값을 쓰는 작업을 안하기 때문에 그런것인가요?

2. 퀵정렬은 이미 정렬된 배열에 대해서는 최악의 수행을 한다고 해서
마찬가지로 2번을 연속으로 돌려보니 1번째는 잘되었는데 2번째(정렬된걸또하니) 먹통이 되더군요.
코드가 잘못되었나 싶어 한참을 보았지만 문제를 찾지못했고
데이터 수를 줄여보았더니 그때는 2번연속이 되었습니다.
이것만은 알고 갑시다.에 재귀 호출에 사용되는 스택 크기 때문에 대용량 처리에 부적합하다고 나와있는데
재귀호출은 시스템내부 배열스택을 사용하는데 그 용량을 초과해서 그런것이라고 이해하면 될까요?
링크드스택을 따로 만들어써서 해결하는 것이고요?

--------------------------------------------------------------------
링크드스택+순환문 써서 해결했습니다. 근데 2번째 정렬은 무진장 느리네요..

책에서 퀵소트 개선하기위해서 앞3개의 중간값을 기준값으로 한다고 하였는데
앞3개만 따로 소트하여 두번째껄 젤 앞으로 옮기고 하면 되겄지요?

또 라이브러리 함수 qsort 는 우리가 만든것과는 달리 비교함수를 매개변수로 사용하는데
뭔지는 대충 알겄어요.. 오름차순 내림차순 같은거 설정할수 있는 옵션이죠?
근데 C가 익숙하지가 않아서.. 매개변수 형식

int (__cdecl *compare )(const void *, const void *)

이걸 어떻게 읽어야 할지 ^^;;;  

"함수형 포인터 인데 그 대상 함수는 int 를 반환하고 void형 상수 포인터를 매개변수로 갖는다"

맞을까요?