Quick sort algorithm

ํ€ต ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜

ํ€ต ์ •๋ ฌ์€ ํ”ผ๋ฒ—์„ ๊ธฐ์ค€์œผ๋กœ ์ขŒ/์šฐ์— ์ž์‹ ๋ณด๋‹ค ํฐ/์ž‘์€ ๊ฐ’์„ ๋ชฐ๊ณ , ๋ฌธ์ œ๋ฅผ ์กฐ๊ธˆ์”ฉ ๋‚˜๋ˆ ๊ฐ€๋ฉฐ ์ •๋ ฌ์„ ํ•˜๊ฒŒ ๋œ๋‹ค. ์ตœ์•…์˜ ๊ฒฝ์šฐ(ํ•ญ์ƒ ํ”ผ๋ฒ—์ด ๋ชจ๋“  ๊ฐ’ ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ๊ฒฝ์šฐ) O(n^2)๋ฅผ ๊ฐ€์ง€๋Š” ์ƒํ™ฉ์ด ๋‚˜์˜ฌ ์ˆ˜ ์žˆ์ง€๋งŒ, ํ™•๋ฅ ์ ์œผ๋กœ ๊ทธ๋Ÿด ์ผ์€ ์ ๊ธฐ์— ํ‰๊ท ์ ์œผ๋กœ O(NlogN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

๊ตฌํ˜„

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
fn main() {
let mut myarr = MyArray::new();
myarr.values.extend_from_slice(&[9, 8, 7, 6, 5, 2, 1, 2, 3, 1]);
myarr.sort();

for value in &myarr.values {
print!("{} ", value);
}
}

struct MyArray {
values: Vec<usize>,
}

impl MyArray {
pub fn new() -> MyArray {
MyArray { values: Vec::new() }
}

pub fn sort(&mut self) {
self.quick_sort(0, self.values.len() - 1);
}

fn quick_sort(&mut self, left: usize, right: usize) {
if left < right {
let pivot = self.partition(left, right);
self.quick_sort(left, pivot - 1);
self.quick_sort(pivot + 1, right);
}
}

fn partition(&mut self, left: usize, right: usize) -> usize {
let mut is_swap = false;
let mut swap_pos = left;
for x in left..right {
if self.values[x] <= self.values[right] {
self.values.swap(swap_pos, x);
swap_pos += 1;
is_swap = true;
}
}
if is_swap // ์ด๋ฏธ ์ •๋ ฌ๋œ ์ƒํƒœ์˜€์„ ๊ฒฝ์šฐ๋Š” ์ œ์™ธ
|| (!is_swap && (self.values[swap_pos] > self.values[right])) // ํ”ผ๋ด‡๋ณด๋‹ค ๊ฐ’๋“ค์ด ๋ชจ๋‘ ํฐ ๊ฒฝ์šฐ ํ”ผ๋ด‡์„ ๊ฐ€์žฅ ์•ž์œผ๋กœ ์ด๋™.
{
self.values.swap(swap_pos, right);
}

swap_pos
}
}

ํ•„๊ธฐ๋…ธํŠธ

Quick sort 1

Quick sort 2

๋ ˆํผ๋Ÿฐ์Šค

[์ž๋ฃŒ๊ตฌ์กฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜] ํ€ต์ •๋ ฌ(Quicksort)์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ณ  ์ž๋ฐ”๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ

ํ€ต์†ŒํŠธ / ํ€ต์ •๋ ฌ 5๋ถ„๋งŒ์— ์ดํ•ดํ•˜๊ธฐ - Gunny

Share