퀵정렬 소스염

SODMaster

2011.10.02 00:21:37

조회 168 추천 0 댓글 4

void QuickSortRecur_in(int* arr, int begin, int end, int& compCnt, int& swapCnt)

{

int left;

int right;

if (begin >= end) return;

left = begin;

right = end + 1;

while (true)

{

while (arr[++left] < arr[begin] && left <= end)

++compCnt;

while (arr[--right] > arr[begin])

++compCnt;

if (left > right) break;

swap(arr[left], arr[right]);

++swapCnt;

}

swap(arr[begin], arr[right]);

++swapCnt;

QuickSortRecur_in(arr, begin, right-1, compCnt, swapCnt);

QuickSortRecur_in(arr, right+1, end, compCnt, swapCnt);

}

void QuickSortRecur(int* arr, int begin, int end)

{

int compCnt = 0;

int swapCnt = 0;

time_t startTime = clock();

QuickSortRecur_in(arr, begin, end, compCnt, swapCnt);

time_t endTime = clock();

cout << "비교횟수 : " << compCnt << endl;

cout << "교환횟수 : " << swapCnt << endl;

cout << "수행시간 : " << endTime - startTime << endl;

}

void QuickSort(int* arr, int begin, int end)

{

int compCnt = 0;

int swapCnt = 0;

time_t startTime = clock();

int paramStack[1024*500];

int top = -1;

int left;

int right;

paramStack[++top] = begin;

paramStack[++top] = end;

while (top > 0)

{

end = paramStack[top--];

begin = paramStack[top--];

if (begin >= end) continue;

left = begin;

right = end + 1;

while (true)

{

while (arr[++left] < arr[begin] && left <= end)

++compCnt;

while (arr[--right] > arr[begin])

++compCnt;

if (left > right) break;

swap(arr[left], arr[right]);

++swapCnt;

}

swap(arr[begin], arr[right]);

++swapCnt;

paramStack[++top] = right+1;

paramStack[++top] = end;

paramStack[++top] = begin;

paramStack[++top] = right-1;

}

time_t endTime = clock();

cout << "비교횟수 : " << compCnt << endl;

cout << "교환횟수 : " << swapCnt << endl;

cout << "수행시간 : " << endTime - startTime << endl;

}

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	모태 솔로도 구제해 줄 것 같은 연애 고수 스타는?	운영자	25/07/21	-	-
AD	곧 휴가!! 홈캉스, 바캉스 SALE	운영자	25/07/21	-	-
276802	try and catch 문 기초적인건데.... [6]	초보초보(130.15)	11.09.29	8069	0
276799	os를 만들자!! +ㅁ+ [5]	거칠게	11.09.29	126	0
276798	SW 없는 죄‥한국IT, '충성 할인' 받아야 하나 [7]	거칠게	11.09.29	121	0
276797	형들 퀵소트 피벗 위치 정하는 좋은 방법이 뭐가 있어? [1]	회색사과	11.09.29	116	0
276795	자기가 주관적으로 이뿌다고 생각하는 여자 어케해야되냐 [4]	.3(124.137)	11.09.29	113	0
276794	제발 대답좀해주라..ㅠㅠ [1]	제발대답좀(14.40)	11.09.29	55	0
276793	lol 있나 [4]	지금,여기	11.09.29	113	0
276792	혹시 여기 벨로시티 쓸줄 아는 형들 있어?	좋은아버지	11.09.29	55	0
276791	배고파 미치겠다 ㅠ	멸자(130.126)	11.09.29	53	0
276787	gg.png [3]	qt^	11.09.29	108	0
276785	어제 아는동생이랑 대화햇는데 [1]	.3(124.137)	11.09.29	79	0
276784	앱 개발해서 마켓이나 앱스토어에 올리려면 돈 많이 들어?? [9]	ㅁㄴㅇㅁㄴㅇ(220.76)	11.09.29	112	0
276783	미클이에요 [5]	미클	11.09.29	101	0
276781	이정도면 귀엽지 않냐? (아스 봅니다.) [4]	blackd	11.09.29	144	0
276780	구글이 특허 쭉정이 모토롤라 인수했잖아 [4]	.3(124.137)	11.09.29	87	0
276778	~ 횽들 임의의 숫자들을 입력하면 패턴 알려주는 프로그램잇나요??~	ㅇ(183.100)	11.09.29	44	0
276777	근데 공식 서비스센터 있는 미국도 애플 디스하는 내용 많던데 [1]	Regi☆	11.09.29	62	0
276776	이번 애플의 2.4$ confidential 공개에 대한 언론의 관점	Deanex	11.09.29	54	0
276774	자사 운영체제 이야기 들으니까 [3]	Regi☆	11.09.29	104	0
276772	ㅋㅋㅋ 형 ㅋㅋ 근데 압축파일 해놓으니깐 250mb 정도라서 하나하나 올 [3]	돌아버리겠네(112.169)	11.09.29	113	0
276770	특허전쟁을 보고 느낀 점 [2]	분당살람	11.09.29	85	0
276769	지뢰기통횽은 봅니다. [6]	blackd	11.09.29	92	0
276767	승질나네... [7]	.3(124.137)	11.09.29	73	0
276766	코딩용으로 젖절한 노트북 추천점 [4]	Cppp	11.09.29	154	0
276765	그런데 진짜 협력 사업은 좋지 않은거 같다.... [1]	좋은아버지	11.09.29	65	0
276764	삼ㅋ성ㅋ 특ㅋ헠 [2]	,.,.(222.121)	11.09.29	116	0
276763	나도 예전부터 올리고 싶었던 짤이 있었지... [2]	blackd	11.09.29	118	0
276762	이럴수가...HP잉크 중에도 불량잉크가 있다니 [4]	분당살람	11.09.29	191	0
276760	삼성 특허 댐시 엿먹을 거 같음 [6]	시불라미	11.09.29	187	0
276756	c++ 도와줄사람 있나 [11]	운지파웡(182.210)	11.09.29	114	0
276755	이거 말하는 건가 -_- [8]	로하로하알로하	11.09.29	129	0
276754	크헠!!! 찾았으욬!!! 진짜가,, 진짜를 찾았으욬!!! [6]	돌아버리겠네(112.169)	11.09.29	141	0
276753	McHello 횽 보긔 [7]	쿄스케	11.09.29	88	0
276752	삼성 만세	Deanex	11.09.29	51	0
276751	삼성은 이미 충실한 고객있다 [1]	로하로하알로하	11.09.29	104	0
276750	내가 생각하는 이직 상황. [10]	좋은아버지	11.09.29	124	0
276748	근데 니들이 [2]	一ㅡ	11.09.29	66	0
276747	오늘의 프갤주제는 삼성임? [2]	1(121.182)	11.09.29	66	0
276746	여기서 봤던 글같은데... 잉여력이 기술 혁신을 가져온다고.... [8]	거칠게	11.09.29	166	0
276744	과제 알려주기 싫다 이유있음.txt [1]	一ㅡ	11.09.29	86	0
276743	한국 IT가 사는 길을 논의해 보자쿠나~!! [28]	거칠게	11.09.29	209	0
276742	그런데 회사에서 나가라고 하면 [8]	좋은아버지	11.09.29	116	0
276740	엑셀 VBA질문해도 돼요??ㅠㅠ [1]	과제하는애(203.255)	11.09.29	149	0
276739	솔까 애플에 비교해서 삼성까는거 별로 공감이 안됨 [3]	-_-)(220.80)	11.09.29	73	0
276738	우리도 애플처럼 자체 os, 단일 기기로 가야 한다!! [2]	거칠게	11.09.29	62	0
276737	IT에서 삼성을 깔게있나..	Regi☆	11.09.29	52	0
276736	논리연산자 오류 질문좀요... [6]	봉제인형포포리	11.09.29	100	0
276735	짤린내친구의 미래 [1]	三didas	11.09.29	107	0
276733	CE 잘하는 형들 도와줘	완전초보(112.216)	11.09.29	52	0
276732	웹 사이트를 분석해야되는데 말이야 '블럭'이란 단어의 뜻이 뭔지좀 알려주 [11]	한시몽(121.139)	11.09.29	125	0
뉴스	최예나, 배우 이도현과 신곡 M/V서 호흡 맞췄다! 청춘 영화 분위기 물씬	디시트렌드	07.22