Quick Sort - 퀵 정렬

가장 효율적인 정렬이라고 합니다.

https://en.wikipedia.org/wiki/Quicksort

Quicksort - Wikipedia

배열에서 기준이되는 피벗을 잡고 피벗보다 작은것을 왼쪽에 큰것을 오른쪽에 넣으면서 제귀호출합니다.

제귀호출로 입력되는 배열의 길이가 1보다 같거나 작을때까지 계속됩니다.

 

Go로 구현한 코드입니다.

package main

import "fmt"
import "math/rand"

func quickSort(arr []int) []int {

	if len(arr) <= 1 {
		return arr
	}

	median := arr[rand.Intn(len(arr))]

	lowPart := make([]int, 0, len(arr))
	highPart := make([]int, 0, len(arr))
	middlePart := make([]int, 0, len(arr))

	for _, item := range arr {
		switch {
		case item < median:
			lowPart = append(lowPart, item)
		case item == median:
			middlePart = append(middlePart, item)
		case item > median:
			highPart = append(highPart, item)
		}
	}

	lowPart = quickSort(lowPart)
	highPart = quickSort(highPart)

	lowPart = append(lowPart, middlePart...)
	lowPart = append(lowPart, highPart...)

	return lowPart
}

func main() {
	arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")
	fmt.Println("Sorted array is: ", quickSort(arr))
}

각 코드에 대한 설명을 주석으로 달았습니다.

package main

import "fmt"
import "math/rand"

func quickSort(arr []int) []int {

	// quickSort 함수는 재귀호출 함수이기 때문에 탈출 구분이 필요합니다.
	// 입력값으로 받은 배일의 길이가 1보다 작을때까지 재귀호출 됩니다.
	if len(arr) <= 1 {
		return arr
	}

	// median(중간값)이라는 배열 변수를 만듭니다.
	// 전체 배열의 길이 이내의 정수 랜덤값을 받아옵니다.
	// median은 임의의 피벗값이 됩니다.
	median := arr[rand.Intn(len(arr))]

	// lowPart, middlePart, highPhar라는 빈 정수 배열(slice)을 만듭니다.
	// 각 배열은 arr 배열의 길이만큼 값을 가질 수 있습니다.
	lowPart := make([]int, 0, len(arr))
	highPart := make([]int, 0, len(arr))
	middlePart := make([]int, 0, len(arr))

	// arr 배열을 대상으로 Loop를 돌립니다.
	for _, item := range arr {
		switch {
		// 피벗으로 잡은 기준값을 기준으로 작으면 lowPart slice에 넣습니다.
		case item < median:
			lowPart = append(lowPart, item)
		// 피벗으로 잡은 기준값을 기준으로 같으면 middlePart slice에 넣습니다.
		case item == median:
			middlePart = append(middlePart, item)
		// 피벗으로 잡은 기준값을 기준으로 크면 highPart slice에 넣습니다.
		case item > median:
			highPart = append(highPart, item)
		}
	}

	// 제귀호출을 하면서 quickSort()의 입력값으로 받는 배열의 길이가 1보다 작거나 같을때 까지 수행합니다.
	lowPart = quickSort(lowPart)
	highPart = quickSort(highPart)

	// 제귀호출이 끝나고 lowPart 배열에 순차적으로 추가합니다.
	lowPart = append(lowPart, middlePart...)
	lowPart = append(lowPart, highPart...)

	return lowPart
}

func main() {
	arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")
	fmt.Println("Sorted array is: ", quickSort(arr))
}

검색해보니 아래와 같은 형태의 Quick Sort도 확인할 수 있습니다.

제귀호출 할 때 make()로 새로운 slice를 만들지 않고 for loop를 돌려 피벗을 기준으로 위치를 변경합니다.

package main

import "fmt"
import "math/rand"

func quickSort(a []int) []int {

	if len(a) < 2 {
		return a
	}

	left, right := 0, len(a)-1

	pivot := rand.Int() % len(a)

	a[pivot], a[right] = a[right], a[pivot]

	for i, _ := range a {
		if a[i] < a[right] {
			a[left], a[i] = a[i], a[left]
			left++
		}
	}

	a[left], a[right] = a[right], a[left]

	quickSort(a[:left])
	quickSort(a[left+1:])

	return a

}

func main() {
	arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")
	fmt.Println("Sorted array is: ", quickSort(arr))
}