[알고리즘]퀵 정렬(Quick Sort)

슈와이

· 9년 전 · 조회 387 387

링크

http://terms.naver.com/entry.nhn?docId=2270444&cid=51173&categoryId=51173 (15) https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC (15)

// 퀵 정렬(Quick Sort)

function Swap(&$arr, $idx1, $idx2) {

$temp = $arr[$idx1];

$arr[$idx1] = $arr[$idx2];

$arr[$idx2] = $temp;

}

// 중간값 찾기

function MedianOfThree($arr, $left, $right) {

$samples = array($left, floor(($left+$right)/2), $right);

if ($arr[$samples[0]] > $arr[$samples[1]])

Swap($samples, 0, 1);

if ($arr[$samples[1]] > $arr[$samples[2]])

Swap($samples, 1, 2);

if ($arr[$samples[0]] > $arr[$samples[1]])

Swap($samples, 0, 1);

return $samples[1];

}

function Partition(&$arr, $left, $right) {

$pIdx = MedianOfThree($arr, $left, $right); // 중간값으로 피벗 선택

$pivot = $arr[$pIdx];

$low = $left + 1;

$high = $right;

Swap($arr, $left, $pIdx); // 피벗을 가장 왼쪽으로 이동

while ($low <= $high) { // 교차되지 않을 때까지 반복

// 피벗보다 큰 값을 찾는 과정

while ($low <= $right && $pivot >= $arr[$low])

$low++;

// 피벗보다 작은 값을 찾는 과정

while ($high >= ($left+1) && $pivot <= $arr[$high])

$high--;

// 교차되지 않는 상태라면 Swap 실행

if ($low <= $high)

Swap($arr, $low, $high);

}

Swap($arr, $left, $high); // 피벗과 high 가 가리키는 대상 교환

return $high; // 옮겨진 피벗의 위치정보 교환

}

function QuickSort(&$arr, $left, $right) {

if ($left < $right) {

$pivot = Partition($arr, $left, $right);

QuickSort($arr, $left, $pivot-1);

QuickSort($arr, $pivot+1, $right);

}

$arr = array(3, 2, 4, 1, 7, 6, 5);

$len = count($arr);

QuickSort($arr, 0, $len-1);

print_r($arr);

댓글 작성

댓글을 작성하시려면 로그인이 필요합니다.

로그인하기

게시판 목록

프로그램

글쓰기

번호	제목	글쓴이	날짜	조회
7630	버튼 클릭 시 왼쪽에서 나오는 토글에 관련한 질문입니다. [3] #퍼블리셔톡 #퍼블리셔	완소주환 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	652
7629	css가 충돌이 됬을때 [4] #퍼블리셔팁 #퍼블리셔 #팁자료실 #css	돼지코구뇽 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2391
7628	계층형 댓글 [4] #개발자톡 #개발자	리자 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	793
7627	멀티업로더.... #개발자톡 #개발자	RINIX 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1031
7626	풀스크린 스크립트 #개발자팁 #개발자 #팁자료실 #javascript	RINIX 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1788
7625	윈도우XP 이용자들에게 호소하는 글 [4] #개발자톡 #개발자	고기조아 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	711
7624	영카트1 --> 영카트 5 변환 후기 [6] #개발자톡 #개발자	벤지 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	725
7623	HTML Canvas 2D Context #퍼블리셔팁 #퍼블리셔 #팁자료실 #html	RINIX 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	3094
7622	이곳에 css질문 해도 되나요? 조심히 여쭙니다~ [3] #퍼블리셔톡 #퍼블리셔	이경민 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	728
7621	gps 사용하는 기업들 [4] #개발자톡 #개발자	leeleeleelee 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	586
7620	댓글, 댓글의 답글, 그 답글의 답글, 그리고 또 답글 ... @@ [2] #개발자톡 #개발자	관리자 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	540
7619	여기에 글을 올려도 될지 모르겠지만 그누4 오류같은데 한번 봐 주세요 [5] #개발자톡 #개발자	관점 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	489
7618	게시판별 테이블 vs 통합 테이블 [5] #개발자톡 #개발자	관리자 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1025
7617	더 빠른 게시판을 위하여 3 [2] #개발자톡 #개발자	리자 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	726
7616	더 빠른 게시판을 위하여 2 [3] #개발자톡 #개발자	리자 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	650
7615	더 빠른 게시판을 위하여 [5] #개발자톡 #개발자	리자 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	726
7614	vi 온라인 학습장 [1] #개발자팁 #개발자 #팁자료실 #웹서버	신리 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1264
7613	강력한 무료 멀티 업로더... [1] #개발자팁 #개발자 #팁자료실 #jquery	RINIX 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2085
7612	가상서버 이용 팁.. .html확장자내 php코드 인식이 안될 때 [2] #개발자팁 #개발자 #팁자료실 #웹서버	신리 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1146
7611	가상서버 셋팅 팁 - ftp접속시 계정사용자 내용만 보여주기 #개발자팁 #개발자 #팁자료실 #웹서버	신리 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1418
7610	HTML5 자바스크립트 API [1] #퍼블리셔팁 #퍼블리셔 #팁자료실 #html	RINIX 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1904
7609	P3P 규약의 이해 [6] #개발자팁 #개발자 #팁자료실 #기타	JRevirthuum 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1345
7608	퍼블리셔및디자인 일거리 찾고있습니다~ [2] #퍼블리셔톡 #퍼블리셔	mwdkim 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1131
7607	워드프레스 템플릿 아키텍쳐 [1] #개발자팁 #개발자 #팁자료실 #기타	JRevirthuum 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1054
7606	퍼블리셔가 전망이잇나요??진짜 궁금해서요 ㅜㅜ ㅎ [5] #퍼블리셔톡 #퍼블리셔	mwdkim 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	3927
7605	사내 업무용은 원도우 응용이 최고가 맞는듯 [1] #개발자톡 #개발자	벤지 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	692
7604	브라우져 메모리 사용률 확인하는 프로그램 ... 꽁수 [1] #개발자팁 #개발자 #팁자료실 #기타	벤지 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1028
7603	작업하다 발견한 꿀팁 공유 [19] #퍼블리셔톡 #퍼블리셔	허정권 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1654
7602	아래 어떤 분이 남기신 CSS스프라이트 기법에 관한 토론... [14] #퍼블리셔톡 #퍼블리셔	nanati 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1078
7601	빠르게 웹사이트로 안드로이드 앱 만들기 [4] #개발자팁 #개발자 #팁자료실 #기타	AniNest 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2793
7600	코딩 컨벤션은 이젠 선택이 아닌 필수라고 생각이 됩니다. (PSR) [7] #개발자톡 #개발자	port443 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1034
7599	브라우져 테스트 할 때 VM 돌리지 마시고.. [3] #개발자톡 #개발자	라엘 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	947
7598	개발자에게 괜찮은 도서 추천 [7] #개발자톡 #개발자	뽁스 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1021
7597	국내 가상서버호스팅 비교(Virtual Private Server Review) [11] #개발자톡 #개발자	라엘 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	4577
7596	다들 메뉴 등 하실때 background-position 많이 쓰세요? [14] #퍼블리셔톡 #퍼블리셔	SeungYeon 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	892
7595	외부이미지 썸네일 만들기 [5] #개발자팁 #개발자 #팁자료실 #php	untitled 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2426
7594	퍼미션 계산기-아주 좋습니다. #개발자팁 #개발자 #팁자료실 #웹서버	프로그래머7 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1728
7593	화면전체에 눈 내리는 효과 [1] #개발자팁 #개발자 #팁자료실 #javascript	untitled 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2366
7592	외부이미지 서버에 저장하기 [1] #개발자팁 #개발자 #팁자료실 #php	untitled 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1944
7591	유튜브 api 사용하기 #개발자팁 #개발자 #팁자료실 #php	untitled 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2677
7590	PC버전을 모바일에서 볼수있게 어떻게 하나여 [4] #퍼블리셔톡 #퍼블리셔	아리마2001 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	854
7589	구글 대신 사용할 수 있는 Map 사이트가 있군요.^^ [2] #개발자톡 #개발자	써맨 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1111
7588	ShadowDOM Visualizer #퍼블리셔팁 #퍼블리셔 #팁자료실 #기타	JRevirthuum 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2920
7587	이제 ie6 는 고려하지 않아도 되겠네요. [11] #개발자톡 #개발자	관리자 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1305
7586	꼭 index를 통해서 들어가게 하는방법있을가요. [3] #개발자톡 #개발자	홍영석 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	672
7585	어플을 개발해줬는데........ [13] #개발자톡 #개발자	유보 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1695
7584	Free PHP Clone Scripts [1] #개발자팁 #개발자 #팁자료실 #기타	묵공 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1414
7583	네이버, 다음과 같은 지도 만들기.. [4] #개발자톡 #개발자	leeleeleelee 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1164
7582	fancybox 사용해보신분계시나요? #개발자톡 #개발자	별을따는소년 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1114
7581	CJK 검색에 어울리는 fulltext 검색엔진 Mroonga를 테스트 해봤습니다. [1] #개발자톡 #개발자	키키2 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1350
7580	벽돌실 무한스크롤 도와주세요!! 스크롤 하면 새로 불러오게 되는데 작동이 안되요 ㅠ #개발자톡 #개발자	비트블루 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	996
7579	풀스크린이미지 관련하여서요.. #개발자톡 #개발자	별을따는소년 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	610
7578	이게 왜이러는지 모르겠네요.....ㅠㅠ [16] #개발자톡 #개발자	亞波治 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1430
7577	숫자를 한글로 변환코드 짜다 이런단위도 있구나 싶네요. #개발자팁 #개발자 #팁자료실 #php	RINIX 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1872
7576	기본 썸네일 함수 보정 하려 합니다 #개발자팁 #개발자 #팁자료실 #php	아길이 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1386
7575	Ubuntu 설치 후 vi 방향키 에러 #개발자팁 #개발자 #팁자료실 #os	멋진남자임 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1465
7574	다음 우편번호 api [2] #프로그램강좌 #프로그램 #강좌 #도로명주소	마뇽 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2123
7573	2015 년 프레임워크 순위 [5] #개발자팁 #개발자 #팁자료실 #php	벤지 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	3258
7572	rewrite 관련 질문은 어디로 올려야 할지....? [5] #개발자톡 #개발자	승희아빠 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	761
7571	홈페이지 접속시에 자동으로 즐겨찾기 가능할까요? [4] #개발자톡 #개발자	별을따는소년 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	784
7570	[안드로이드] 영상채팅 앱 필요하신 분 말씀주세요. 만들어드립니다. [8] #개발자톡 #개발자	카카오툴즈 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1318
7569	자바스크립트로 오버로딩 구현하기 [1] #개발자팁 #개발자 #팁자료실 #javascript	바보천사 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1552
7568	[질문]curl로 타서버와 통신중 딜레이주는법없나요? [2] #개발자톡 #개발자	this1mg 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1052
7567	모바일에서홈페이지접속후 pc바로가기누른후... [5] #퍼블리셔톡 #퍼블리셔	내사랑내사랑 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	763
7566	대구지역 웹개발자 프로젝트같이 해보실분? #개발자톡 #개발자	야상곡 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	918
7565	웹개발자가 꿈입니다 [2] #개발자톡 #개발자	Angel하늘 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1010
7564	이 정도 게시판수정이라면 견적은 얼마정도?ㅠ [5] #개발자톡 #개발자	seoldi 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1241
7563	웹프로그램 PHP를 배워볼려고하는데요!! 완전 초짜가 볼수있는 책 추천좀요!! [7] #개발자톡 #개발자	별을따는소년 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1385
7562	무료 팩스 이거 대단함 [3] #개발자팁 #개발자 #팁자료실 #기타	멋진남자임 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2086
7561	파일질라 맥 overwrite dialog 없애기 [1] #개발자톡 #개발자	박긍정 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	714
7560	웹호스팅이용시 각 언어별 적용 방법 [4] #개발자톡 #개발자	leeleeleelee 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	905
7559	CentOS7 + httpd 2.4.12 + mariadb 10.0.16 + php 5.6.6 설치 [20] #개발자팁 #개발자 #팁자료실 #웹서버	亞波治 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	5048
7558	버전문제는 어떻게해결하세요?ㅜ #개발자톡 #개발자	RinaP 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	786
7557	프로그래머는 역시 힘드네요 [5] #개발자톡 #개발자	성격파탄자 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1246
7556	젤 아래에 있는 테이블 마크업 어떻게 하나요? [4] #퍼블리셔톡 #퍼블리셔	김워프 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1194
7555	웹사이트 사이즈 ㅜㅜ [4] #퍼블리셔톡 #퍼블리셔	hyohyojj1234 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1666
7554	동창회 싸이트에 필요한 요구사항을 정리해봅니다. [8] #개발자톡 #개발자	차동박 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1094
7553	서브도메인 세션공유 [3] #개발자톡 #개발자	senseme 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1339
7552	모달팝업 질문입니다. [3] #퍼블리셔톡 #퍼블리셔	ehdltdoit 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1437
7551	푸시우시 전송 클래스 [17] #개발자톡 #개발자	Terrorboy 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1825
7550	어떤 IT 언어를 공부해야 하나요? [11] #개발자톡 #개발자	leeleeleelee 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1593
7549	신입퍼블리셔..4주짼데요 [13] #퍼블리셔톡 #퍼블리셔	로자리아 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2426
7548	KCP 가상계좌 취소시 6003에러 #개발자팁 #개발자 #팁자료실 #php	박쥐12 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1845
7547	사이트 관리자 비밀번호 재설정하기 #개발자팁 #개발자 #팁자료실 #mysql	멋진남자임 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1963
7546	그누보드 5 초보입니다. 오류 및 기능 질문드리니다. [1] #개발자톡 #개발자	마신 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1006
7545	jQuery를 처음 접해봅니다. [4] #퍼블리셔톡 #퍼블리셔	ILMare1003 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1290
7544	에디트플러스에서.... [7] #퍼블리셔톡 #퍼블리셔	내사랑내사랑 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1252
7543	자바스크립트에서...IE5,6에서 팝업창의 위치를 보이는화면 중앙쯤에 위치하게끔 어떻게 하나요..? [2] #개발자톡 #개발자	김코튼 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	885
7542	썸네일수정 명령어구문에 질문이있습니다. [2] #퍼블리셔톡 #퍼블리셔	녀비여비 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	657
7541	코스피를 홈페이지에 삽입할수 있나요? [3] #개발자톡 #개발자	울라라라우 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	865
7540	제이쿼리 최신 버전 호출 적용시 LIVE 함수 오류 [4] #개발자팁 #개발자 #팁자료실 #jquery	라펜타 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1600
7539	javascript 공부를 하는데 어렵네요 [4] #개발자톡 #개발자	키키2 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	936
7538	회원가입 및 로그인 아이디 이메일 사용하기 #개발자팁 #개발자 #팁자료실 #php	Romancia 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1834
7537	혹시 기획자가 봤을 때 도움이 되는 책이 있나요? #기획자톡 #기획자	진한량 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	3611
7536	IE8이 사람 여럿 환장하게 만드는군요 [5] #퍼블리셔톡 #퍼블리셔	Gaumi 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1416
7535	혹시 kboard 아시는분 계신가요? [12] #개발자톡 #개발자	프로그램은어려워 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1274
7534	php만으로도 브라우저 화면 크기를 구할 수 있을까요? [9] #개발자톡 #개발자	senseme 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1207
7533	워드프레스 마크업 어떻게하시나요? [1] #퍼블리셔톡 #퍼블리셔	김워프 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	1198
7532	그누보드로 사이트 제작할려고 하는데.. [1] #퍼블리셔톡 #퍼블리셔	레아님 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	859
7531	안드로이드 4.4 킷캣(kitkat) 버전 웹뷰에서 파일첨부 안되는 현상. [2] #개발자톡 #개발자	위토즈 프로필 보기 이 회원 글보기 이 회원의 댓글보기	10년 전	2057