ThinkerQAQ

NOTE

3.14 Quick Sort

Quick sort, its characteristics, partitions, and implementations.

Data Structures & AlgorithmsCreated Updated 1 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

1. Quick Sort

It uses the divide-and-conquer idea: divide a large problem into smaller problems and solve them recursively. Quick sort selects a pivot, moves values smaller than it to the left and values larger than it to the right, and then performs the same processing on the smaller arrays on the left and right. If the key to merge sort is merging, the key to quick sort is partitioning.

2. Efficiency

  • Stability: unstable
  • In-place sorting: yes
  • Complexity
    • Time: average O(nlogn), worst O(n²)
    • Space: O(logn)

3. Process

4. Implementation

4.1. One-Way Quick Sort

//O(NlogN)
func QuickSort(data []model.Comparable) {
	quickSort(data, 0, len(data)-1)
}

func quickSort(data []model.Comparable, left int, right int) {
	if left >= right {
		return
	}

	p := partition(data, left, right)
	quickSort(data, left, p-1)
	quickSort(data, p+1, right)
}

func partition(data []model.Comparable, left int, right int) int {
	// data[left+1...j] < v; data[j+1...i] >= v
	j := left
	for i := left + 1; i <= right; i++ {
		if data[i].CompareTo(data[left]) < 0 {
			j++
			util.Swap(data, i, j)
		}
	}
	util.Swap(data, left, j)
	return j
}

4.1.1. Test

func TestQuickSort(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	QuickSort(data)
	fmt.Println(data)
}

4.1.2. Optimization

  • For a sorted array, each partition splits off only one element, so efficiency drops to O(N²)
  • Add randomization
func partition(data []model.Comparable, left int, right int) int {
	// Generate a random index in [l, r]
	p := left + util.RandInt(0, right-left)
	util.Swap(data, left, p)

	// data[left+1...j] < v; data[j+1...i] >= v
	j := left
	for i := left + 1; i <= right; i++ {
		if data[i].CompareTo(data[left]) < 0 {
			j++
			util.Swap(data, i, j)
		}
	}
	util.Swap(data, left, j)
	return j
}

4.2. Two-Way Quick Sort

//O(NlogN)
func QuickSort2(data []model.Comparable) {
	quickSort2(data, 0, len(data)-1)
}

func quickSort2(data []model.Comparable, left int, right int) {
	if left >= right {
		return
	}

	p := partition2(data, left, right)
	quickSort2(data, left, p-1)
	quickSort2(data, p+1, right)
}

func partition2(data []model.Comparable, left int, right int) int {
	// Generate a random index in [l, r]
	p := left + util.RandInt(0, right-left)
	util.Swap(data, left, p)

	// data[left+1...j] <= v; data[j+1...i] >= v
	i := left + 1
	j := right
	for {
		for i <= j && data[i].CompareTo(data[left]) < 0 {
			i++
		}
		for j >= i && data[j].CompareTo(data[left]) > 0 {
			j--
		}
		if i >= j {
			break
		}

		util.Swap(data, i, j)
		i++
		j--
	}

	util.Swap(data, left, j)
	return j
}

4.2.1. Test

func TestQuickSort2(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	QuickSort2(data)
	fmt.Println(data)
}

4.3. Three-Way Quick Sort


//O(NlogN)
func QuickSort3(data []model.Comparable) {
	quickSort3(data, 0, len(data)-1)
}

func quickSort3(data []model.Comparable, left int, right int) {
	if left >= right {
		return
	}
	// Generate a random index in [l, r]
	p := left + util.RandInt(0, right-left)
	util.Swap(data, left, p)

	// data[l+1, lt] < v, data[lt+1, i-1] == v, data[gt, r] > v
	lt := left
	i := left + 1
	gt := right + 1
	for i < gt {
		if data[i].CompareTo(data[left]) < 0 {
			lt++
			util.Swap(data, i, lt)
			i++
		} else if data[i].CompareTo(data[left]) > 0 {
			gt--
			util.Swap(data, i, gt)
		} else {
			i++
		}
	}

	util.Swap(data, left, lt)

	quickSort3(data, left, lt-1)
	quickSort3(data, gt, right)
}

4.3.1. Test

func TestQuickSort3(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e3}
	fmt.Println(data)

	QuickSort3(data)
	fmt.Println(data)
}

4.4. Common Implementation

package sort

import (
	"my_algorithm/model"
)

//O(NlogN)
func QuickSort2Again(data []model.Comparable) {
	quickSort2Again(data, 0, len(data)-1)
}

func quickSort2Again(data []model.Comparable, left int, right int) {
	if left >= right {
		return
	}

	p := partition2Again(data, left, right)
	quickSort2Again(data, left, p-1)
	quickSort2Again(data, p+1, right)
}

func partition2Again(data []model.Comparable, left int, right int) int {
	pivot := data[left]
	for left < right {
		for left < right && data[right].CompareTo(pivot) >= 0 {
			right--
		}
		data[left] = data[right]
		for left < right && data[left].CompareTo(pivot) <= 0 {
			left++
		}
		data[right] = data[left]
	}
	data[left] = pivot
	return right
}

4.4.1. Test

func TestQuickSort2Again(t *testing.T) {
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	data := []model.Comparable{e2, e1, e1, e3}
	fmt.Println(data)

	QuickSort2Again(data)
	fmt.Println(data)
}

5. References

Discussion

Sign in with GitHub to comment. Discussions are stored as GitHub Issues.View on GitHub