Commit d0f1555

committed

Add quick sort.rs

1 parent 8444fda commit d0f1555Copy full SHA for d0f1555

File tree

+49

-0

lines changed

+49

-0

lines changed

Lines changed: 15 additions & 0 deletions

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -78,3 +78,37 @@ pub fn merge_sort(nums: &[isize]) -> Vec<isize> {`
`78`	`78`	`let right = merge_sort(&nums[midpoint..]);`
`79`	`79`	`merge(&left, &right)`
`80`	`80`	`}`
	`81`	`+`
	`82`	`+fn pivot_helper(nums: &mut [isize], start: usize, end: usize) -> usize {`
	`83`	`+ /* selects a pivot and arranges all nums less than it to the left of it,`
	`84`	`+ and greater than it to the right of it */`
	`85`	`+ let pivot_idx = start;`
	`86`	`+ let mut offset = start;`
	`87`	`+ for i in start+1..=end {`
	`88`	`+ if nums[i] < nums[pivot_idx] {`
	`89`	`+ offset += 1;`
	`90`	`+ nums.swap(i, offset);`
	`91`	`+ }`
	`92`	`+ }`
	`93`	`+ nums.swap(pivot_idx, offset);`
	`94`	`+ offset`
	`95`	`+}`
	`96`	`+`
	`97`	`+pub fn quick_sort(nums: &mut [isize]) -> &mut [isize] {`
	`98`	`+ fn sort(nums: &mut [isize], left: usize, right: usize) -> &mut [isize] {`
	`99`	`+ if left < right {`
	`100`	`+ let pivot_idx = pivot_helper(nums, left, right);`
	`101`	`+ // left`
	`102`	`+ if pivot_idx > 0 {`
	`103`	`+ sort(nums, left, pivot_idx - 1);`
	`104`	`+ }`
	`105`	`+ // right`
	`106`	`+ sort(nums, pivot_idx+1, right);`
	`107`	`+ }`
	`108`	`+ nums`
	`109`	`+ }`
	`110`	`+ if nums.len() > 0 {`
	`111`	`+ sort(nums, 0, nums.len() - 1);`
	`112`	`+ }`
	`113`	`+ nums`
	`114`	`+}`

Comments

(0)