퀵 정렬은 피벗 하나를 고른 뒤 그보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 배치합니다. 양쪽 부분 배열에 같은 과정을 재귀적으로 적용합니다.
분할이 균형 잡히면 평균 O(n log n)이지만, 피벗 선택이 계속 나쁘면 O(n²)까지 악화할 수 있습니다. 데모는 분할 경계가 생기는 순간을 보여줍니다.
언제 쓰나
정렬 메모리를 적게 쓰는 분할 방식을 이해할 때 유용합니다.
퀵 정렬
Quicksort
피벗을 기준으로 작은 값과 큰 값을 나눠 각 부분을 정렬합니다.
···
<div class="v"><header><b>QUICKSORT</b><span id="state"></span></header><main><div class="bars" id="bars"></div><div class="axis">smaller <span>pivot</span> larger</div></main><footer>partition by pivot</footer></div>.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .bars{height:75%;display:flex;align-items:end;justify-content:center;gap:6px}.bar{width:12%;max-width:42px;min-width:16px;border-radius:5px 5px 0 0;background:var(--muted);display:grid;place-items:end center;color:var(--bg);font:700 1em ui-monospace,monospace;transition:height .4s,order .4s,background .4s}.bar.pivot{background:var(--accent)}.axis{display:flex;justify-content:space-around;color:var(--muted);font-size:.8em}.axis span{color:var(--accent)}const orders=[[7,2,6,4,1,8,3],[2,1,3,4,7,8,6],[1,2,3,4,6,7,8]];let n=0;function draw(){document.getElementById("bars").innerHTML=orders[n].map(v=>"<div class=\"bar "+(v===4?"pivot":"")+"\" style=\"height:"+(18+v*8)+"%\">"+v+"</div>").join("");document.getElementById("state").textContent=["choose 4","partition","sort sides"][n];n=(n+1)%3}draw();setInterval(draw,1000)