๐ฉํผ๋ฒ : ๋ณดํต ์ฃผ์ด์ง ๋ฐฐ์ด์ ์ฒซ ๋ฒ์งธ ๋ฐ์ดํฐ๋ก ์ง์
๊ธฐ์ค์ด ๋๋ ์(pivot)๋ฅผ ์์ด ์์์ ์์๋ก ํ๋ ์ ํํ์ฌ ํผ๋ด ์ด์ธ์ ์๋ฅผ ํผ๋ด๋ณด๋ค ์์ ์, ํฐ ์๋ก ๋๋๋ค.
์์ ์ < ํผ๋ด <= ํฐ์๋ก ๋ฐฐ์น
๊ทธ๋ฆฌ๊ณ ๋ ๊ทธ๋ฃน์ ์ ๋ ฌํ๋ฉด ๋๋ค. ์ด ๋๋ ํต ์ ๋ ฌ์ ์ด์ฉ
์์์ด ํ๋๋ง ๋จ์ผ๋ฉด ๋
๐ฉ ๊ทธ๋ฃน ๋๋๊ธฐ ํจ์, ๊ทธ ํจ์๋ก ์ ๋ ฌ์ ์ํํ๋ ํจ์๋ฅผ ์ค๋นํ๋ฉด ํต ์ ๋ ฌ ํ๋ก๊ทธ๋จ ์์ฑ์ด ๋งค์ฐ ๊ฐ๋จํด์ง๋ค.
QuickSort(A[ ], n){
if (n > 1) {
// โ ํผ๋ฒ์ ๊ธฐ์ค์ผ๋ก ๋ ๋ถ๋ถ๋ฐฐ์ด๋ก ๋ถํ
// pivot์ ์ ์๋ฆฌ๋ฅผ ์ก์ ํผ๋ฒ์ ์์น(์ธ๋ฑ์ค)๋ฅผ ํ์
pivot = Partition(A[0..n-1], n);
// โก์ผ์ชฝ ๋ถ๋ถ๋ฐฐ์ด์ ๋ํ ํต ์ ๋ ฌ์ ์ํ ํธ์ถ
QuickSort(A[0..pivot-1], pivot);
// โข์ค๋ฅธ์ชฝ ๋ถ๋ถ๋ฐฐ์ด์ ๋ํ ํต ์ ๋ ฌ์ ์ํ ํธ์ถ
QuickSort(A[pivot+1..n-1], n-pivot-1);
}
}
int Partition (A[ ], n){
Left = 1; Right = n-1;
while (Left < Right) {
while (Left < n && A[Left] < A[0]) Left++;
while (Right > 0 && A[Right] >= A[0]) Right--;
if (Left < Right)
A[Left]์ A[Right]์ ์์น ๊ตํ
else
ํผ๋ฒ A[0]์ A[Right]์ ์์น ๊ตํ
}
return (Right);
}
๐ฉ ์๊ฐ ๋ณต์ก๋
๋ฐ์ดํฐ๋ฅผ ์ ๋ฐ์ฉ ๋ถํ ํ๋ฉด์ ์ค์ฌ๋๊ฐ๊ธฐ ๋๋ฌธ์ logn๋งํผ์ ๋ถํ ์ด ์ด๋ค์ง๊ฒ ๋๊ณ
๊ฐ ๋ถํ ์์ n๋ฒ์ ๊ฐ ๋น๊ต๋ฅผ ํตํด ์์น๋ฅผ ์ฐพ์๊ฐ๊ธฐ ๋๋ฌธ์ O(nlogn)
๐ ํต ์ ๋ ฌ์ด ๋น ๋ฅธ ์ด์
์ ํ ์ ๋ ฌ : ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ ํ ๋ฒ ํ์ธํ์ ๋, ๊ฐ์ฅ ์์ ๋ฐ์ดํฐ์ ์์น๊ฐ ํ์ ๋ ๋ฟ, ๋๋จธ์ง ๋ฐ์ดํฐ๋ ๊ทธ๋๋ก ๋ด๋ฒ๋ ค๋๋ค.
๋ฐ๋ฉด์, ํต ์ ๋ ฌ์ ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ ํ ๋ฒ ํ์ธํ์ ๋, ๊ธฐ์ค๊ฐ์ด ๋๋ ๋ฐ์ดํฐ์ ์์น๊ฐ ํ์ ๋๊ณ , ๋๋จธ์ง ๋ฐ์ดํฐ๋ 2๊ฐ์ ๊ทธ๋ฃน์ผ๋ก ๋๋๋ค. ์ด '๋๋จธ์ง ๋ฐ์ดํฐ๊ฐ ๋ ๊ทธ๋ฃน์ผ๋ก ๋๋๋'๋งํผ, ์ดํ ์ฒ๋ฆฌ๊ฐ ํจ์จ์ ์ด๋ค. ์ด๊ฒ์ด ํต ์ ๋ ฌ์ด ๋น ๋ฅธ ์ด์
'๐ฉโ๐ป ํ๋ก๊ทธ๋๋ฐ > ๐ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
ํ ์ ๋ ฌ(Heap Sort) (0) | 2024.04.13 |
---|---|
ํฉ๋ณ ์ ๋ ฌ(Merge Sort) (0) | 2024.04.12 |
์ ธ ์ ๋ ฌ(Shell Sort) (0) | 2024.04.12 |
์ฝ์ ์ ๋ ฌ(Insertion Sort) (1) | 2024.04.12 |
๋ฒ๋ธ ์ ๋ ฌ(Bubble Sort) (0) | 2024.04.12 |