1. ์ ์ ๐จ๐
ํต ์ ๋ ฌ(Quick Sort)์ ๋ถํ ์ ๋ณต ๋ฐฉ๋ฒ์ ์ด์ฉํ๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ํต ์ ๋ ฌ์ ํผ๋ฒ(Pivot)์ ๊ธฐ์ค์ผ๋ก ๋ถํ ๊ณผ ์ ๋ณต์ด ์ด๋ฃจ์ด์ง๊ฒ ๋๋ค.
ํต ์ ๋ ฌ์ 'ํผ๋ฒ์ ์ ํํ๋ ๋ฐฉ์'๊ณผ '์ฌ๊ท ๋๋ ๋น์ฌ๊ท ๋ฐฉ์'์ ์ ํ์ ๋ฐ๋ผ ๋ค์ํ ๊ตฌํ ๋ฐฉ๋ฒ์ด ์กด์ฌํ๋ค. ์ด๋ฒ ๊ธ์์๋ '์ผ์ชฝ ํผ๋ฒ์ ์ ํํ๋ ๋ฐฉ์'๊ณผ '์ฌ๊ท ๋ฐฉ์'์ ํตํ ํต ์ ๋ ฌ์ ์์๋ณด๋๋ก ํ์.
2. ๋์ ๋ฐฉ์ ๐ฆธโ๏ธ
๊ธฐ๋ณธ์ ์ธ ๋์ ๋ฐฉ์์ ์๋์ ๊ฐ๋ค.
- ๋ฐฐ์ด์์ ์์์ ์์์ธ pivot์ ์ ํํ๋ค. (ํด๋น ๊ธ์์๋ ๋ฐฐ์ด์์ ์ ์ผ ์ผ์ชฝ ์์๋ฅผ pivot์ผ๋ก ์ ํํ๋ค.)
- pivot์ ๊ธฐ์ค์ผ๋ก pivot๋ณด๋ค ์์ ์์๋ ์ผ์ชฝ์ผ๋ก, pivot๋ณด๋ค ํฐ ์์๋ ์ค๋ฅธ์ชฝ์ ์ค๋๋ก ๋ฐฐ์ด์ ๋ฐฐ์นํ๋ค.
- pivot์ ๊ธฐ์ค์ผ๋ก ๋๋์ด์ง ์ผ์ชฝ ๋ฐฐ์ด๊ณผ ์ค๋ฅธ์ชฝ ๋ฐฐ์ด์ 1~2๋ฒ์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค. (์ฌ๊ท ๋ฐฉ์์ ์ฌ์ฉ)
pivot์ ๊ธฐ์ค์ผ๋ก '์ด๋ป๊ฒ pivot๋ณด๋ค ์์ ์์๋ ์ผ์ชฝ์, pivot๋ณด๋ค ํฐ ์์๋ ์ค๋ฅธ์ชฝ์' ์์นํ๋๋ก ํ๋์ง ์์ธํ ์์๋ณด์. ์ผ์ชฝ์์ ์์ํ๋ ํฌ์ธํฐ(lo)์ ์ค๋ฅธ์ชฝ์์ ์์ํ๋ ํฌ์ธํฐ(hi)๋ฅผ ์ด์ฉํ์ฌ pivot์ ๊ธฐ์ค์ผ๋ก ์์๋ค์ ๋๋๊ฒ ๋๋ค.
- hi์ lo๋ผ๋ ์ธ๋ฑ์ค๋ฅผ ๊ฐ๋ฆฌํค๋ ํฌ์ธํฐ๋ฅผ ์ค์ ํ๋ค. (ํํ ์๊ณ ์๋ ์ค์ ํฌ์ธํฐ๊ฐ ์๋๋ค.)
- hi๋ pivot๋ณด๋ค ์์ ๊ฐ์ ๋ง๋ ๋๊น์ง ์ผ์ชฝ์ผ๋ก ์ด๋ํ๋ค.
- lo๋ pivot๋ณด๋ค ํฐ ๊ฐ์ ๋ง๋ ๋๊น์ง ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ํ๋ค.
- ๋ ๊ฐ์ ํฌ์ธํฐ๊ฐ ๊ฐ๋ฆฌํค๋ ๊ฐ์ ๋ฐ๊พผ๋ค.
- lo๊ฐ hi๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๋๊น์ง 2~5๋ฒ์ ๋ฐ๋ณตํ๋ค.
- pivot๊ณผ lo๋ฅผ ๋ฐ๊ฟ์ค๋ค.
{5, 3, 7, 8, 2, 4, 6}์ ๋ฐฐ์ด์ด pivot์ ๊ธฐ์ค์ผ๋ก ์ด๋ป๊ฒ ์ ๋ ฌ๋๋์ง ๊ทธ๋ฆผ์ ํตํด์ ์์๋ณด์.
๋ง์ง๋ง์ pivot์ธ 5์ lo์ธ 2๋ฅผ ๋ฐ๊ฟ์ฃผ๋ฉด pivot์ธ 5๋ ์์ ์ ์๋ฆฌ์ ์ฐพ์๊ฐ ๊ฒ์ด ๋๋ค. ๊ทธ๋ฌ๋ฉด pivot์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ์๋ pivot๋ณด๋ค ์์ ์์๋ค์ด ์ค๋ฅธ์ชฝ์๋ pivot๋ณด๋ค ํฐ ์์๋ค์ด ์์นํ๊ฒ ๋๋ค.
๊ณ์ํด์ pivot์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ ์์ญ๊ณผ ์ค๋ฅธ์ชฝ ์์ญ์ ์ ๋ ฌํด ๋ณด์.
์ ๋ ฌ์ด ์ด๋ฃจ์ด์ง๋ ๊ณผ์ ์์ 3๊ฐ์ง๋ง ์ฃผ๋ชฉํ๋ฉด ์ฝ๊ฒ ์ดํดํ ์ ์๋ค.
- hi์ lo๊ฐ pivot๋ณด๋ค ์์ ๊ฒ์ ์ฐพ์ ๋๊น์ง, pivot๋ณด๋ค ํฐ ๊ฐ์ ์ฐพ์ ๋๊น์ง ์ด๋ํ๋ค.
- lo๋ hi๋ณด๋ค ํฐ ์ธ๋ฑ์ค๋ฅผ ๊ฐ๋ฆฌํค์ง ์๋๋ค.
- ๋ ์ด์ ์์ง์ผ ์ ์์ผ๋ฉด pivot๊ณผ lo๋ฅผ ๊ต์ฒดํ๋ค.
์ด๋ ๊ฒ ๋๋์ด์ง ๋ฐฐ์ด๋ค์ ํฉ์น๊ฒ ๋๋ฉด ์ ๋ ฌ๋ ๋ฐฐ์ด์ด ๋๋ค.
3. ๊ตฌํ(JAVA) ๐งโ๏ธ
public static void main(String[] args) {
int[] array = {5, 3, 7, 8, 2, 4, 6};
quickSort(array, 0, array.length - 1);
}
static void quickSort(int[] array, int left, int right) {
if(left >= right)
return;
// pivot์ ๊ธฐ์ค์ผ๋ก
// ์ผ์ชฝ์๋ pivot๋ณด๋ค ์์ ๊ฒ๋ค์ด
// ์ค๋ฅธ์ชฝ์๋ pivot๋ณด๋ค ํฐ ๊ฒ๋ค์ด
// ์์นํ๋๋ก ํ๋ ๊ฒ
int pivot = partition(array, left, right);
// ์ผ์ชฝ ์์ญ์ ๋ํด์ ๋ค์ ์ ๋ ฌ
quickSort(array, left, pivot - 1);
// ์ค๋ฅธ์ชฝ ์์ญ์ ๋ํด์ ๋ค์ ์ ๋ ฌ
quickSort(array, pivot + 1, right);
}
static int partition(int[] array, int left, int right) {
int pivot = array[left];
int lo = left, hi = right;
while(lo < hi) {
// hi๊ฐ pivot๋ณด๋ค ์์ ๊ฒ์ ์ฐพ์ ๋๊น์ง ์ผ์ชฝ์ผ๋ก ์ด๋
while(pivot < array[hi]) {
hi--;
}
// lo๊ฐ pivot๋ณด๋ค ํฐ ๊ฒ์ ์ฐพ์ ๋๊น์ง ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋
// lo๋ hi๋ณด๋ค ํฐ ์ธ๋ฑ์ค ๊ฐ์ ๊ฐ์ง ์ ์๋ค!!
while(lo < hi && pivot >= array[lo]) {
lo++;
}
// lo๊ฐ ๊ฐ๋ฅดํค๋ ๊ฒ๊ณผ hi๊ฐ ๊ฐ๋ฅดํค๋ ๊ฒ์ ๊ต์ฒด
swap(array, lo, hi);
}
// pivot๊ณผ lo๋ฅผ ๊ต์ฒด
// ๊ต์ฒดํ๊ฒ ๋๋ฉด pivot์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ์๋ ์์ ๊ฐ
// ์ค๋ฅธ์ชฝ์๋ ํฐ ๊ฐ๋ค์ด ์์นํจ.
array[left] = array[lo];
array[lo] = pivot;
// pivot์ ์์น๋ฅผ return
return lo;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
4. ์๊ฐ๋ณต์ก๋ & ๊ณต๊ฐ๋ณต์ก๋ ๐ฆนโ๏ธ
1. ์๊ฐ๋ณต์ก๋
ํต ์ ๋ ฌ์ ์๊ฐ๋ณต์ก๋๋ pivot์ด ์ด๋ป๊ฒ ์ ํ๋๋์ง์ ๋ฐ๋ผ์ ๋ฌ๋ผ์ง๋ค.
์ผ๋ฐ์ ์ผ๋ก N๊ฐ์ ๋ ธ๋์ ๋ํ์ฌ ์ด์งํธ๋ฆฌ์ ๋์ด๋ logN์ด ๋๊ณ ๊ฐ ๋ ๋ฒจ์์ N๋ฒ์ ๋น๊ต์ ์ ๋ ฌ์ด ์ผ์ด๋๋ค. (๋ณํฉ ์ ๋ ฌ ์ฐธ๊ณ ) ๊ทธ๋ ๊ธฐ ๋๋ฌธ์ ์ผ๋ฐ์ ์ธ ์ํฉ์์์ ์๊ฐ๋ณต์ก๋๋ O(N logN)์ด ๋๋ค.
ํ์ง๋ง ์ต์ ์ ๊ฒฝ์ฐ๋ ์๊ธฐ๊ฐ ๋ฌ๋ผ์ง๋ค. pivot์ด ๊ณ์ํด์ ๊ฐ์ฅ ์์ ๊ฐ์ด๋ ํฐ ๊ฐ์ด ๋๋ฉด(์ด๋ฏธ ์ค๋ฆ์ฐจ์์ด๋ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌ์ด ๋์ด ์๋ ๊ฒฝ์ฐ) ํธ๋ฆฌ์ ๋์ด logN์ด ์๋ N์ด ๋๊ฒ ๋๋ค. ๊ทธ๋ฌ๋ฏ๋ก ์ต์ ์ ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋๋ O(N^2)๊ฐ ๋๋ค.
์ต์ (BEST) | ํ๊ท (AVERAGE) | ์ต์ (WORST) | |
์๊ฐ๋ณต์ก๋ | O(N logN) | O(N logN) | O(N^2) |
2. ๊ณต๊ฐ๋ณต์ก๋
๊ณต๊ฐ๋ณต์ก๋์ ๊ฒฝ์ฐ ์ฃผ์ด์ง ๋ฐฐ์ด ์์์ ๊ตํ(swap)์ด ์ผ์ด๋๋ฏ๋ก O(N)์ด๋ค.
5. ์ฅ์ & ๋จ์ ๐จ๐ฌ
1. ์ฅ์
- ์๊ฐ๋ณต์ก๋๊ฐ O(N logN)์ธ ๋ค๋ฅธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋นํด ์๋์ ์ผ๋ก ๋น ๋ฅด๋ค. (ํ๋ฒ ๊ฒฐ์ ๋ pivot์ด ๋ค์ ์ฐ์ฐ์์ ์ ์ธ๋๋ค๋ ํน์ฑ ๋๋ฌธ)
- ์ถ๊ฐ์ ์ธ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ํ์๋ก ํ์ง ์๋๋ค.
2. ๋จ์
- ํน์ ์กฐ๊ฑด์์ ์ฑ๋ฅ์ด ๊ธ๊ฒฉํ ๋จ์ด์ง๋ค.
pivot์ ๊ฐ์ฅ ์์ ๊ฐ์ ์ ํํ๊ฑฐ๋ ํฐ ๊ฐ์ ๊ณ์ํด์ ์ ํํ์ฌ ๋ถ๊ท ํ ๋ถํ ์ด ์ด๋ฃจ์ด์ง๋ ๊ฒฝ์ฐ - ์ฌ๊ท๋ฅผ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ ์ผ์ ํ์ ์ด์์ด๋ฉด ์ฌ์ฉํ์ง ๋ชปํ๋ค. (์ฌ๊ท๋ฅผ ์ฌ์ฉํ์ง ์๊ณ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ด ์๊ธด ํ๋ฐ ๋ณต์กํ๋ค.)
ํด๋น ๊ธ์
Gyoogle๋์ ํต ์ ๋ ฌ(Quick Sort),
Stranger๋์ ์๋ฐ-ํต ์ ๋ ฌ(Quick Sort)
๋ฅผ ์ฐธ๊ณ ํ์์ต๋๋ค.
'๐ ์๋ฃ๊ตฌ์กฐ > ์ ๋ ฌ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์นด์ดํ ์ ๋ ฌ (Counting Sort) (0) | 2023.04.12 |
---|---|
ํ ์ ๋ ฌ (Heap Sort) (0) | 2023.03.12 |
์์ ์ ๋ ฌ(Topology Sort) (2) | 2023.03.07 |
๋ณํฉ ์ ๋ ฌ(Merge Sort) (0) | 2023.03.07 |
์ฝ์ ์ ๋ ฌ(Insertion Sort) (0) | 2023.03.06 |