Golang Algorithm - quickSort

퀵 정렬이란?

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬 - 위키백과, 우리 모두의 백과사전

다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속하고 n개의 데이터를 정렬할 때 최악의 경우에는  O(n^2)번의 비교를 수행하고 평균적으로 O(n log n)번의 비교를 수행한다. 

 

 

go로 구현하는 quickSort

 

이번 quickSort에서도 지난번 bubbleSort2와 마찬가지로 난수를 생성해서 배열에 넣고 그 배열을 가지고 퀵정렬을 수행했다.

 

 

각 함수의 역할

 

 

main() : 20개의 난수 배열을 생성하는 함수 generateSlice를 호출한 뒤 quicksort 함수를 호출하는 메인 함수

generateSlice() : slice를 초기화한뒤 slice 배열에 1부터 999까지의 난수 -  1부터 999까지의 난수를 계산한 원소를 삽인한 배열(slice)을 리턴한다. 

quicksort() : 소스코드 순서는 다음과 같다. 

• 배열의 길이가 2미만이면 배열 반환
• left, right, pivot 변수로 인덱스 위치 지정 
• right와 pivot 위치 교환
• 배열 a의 길이만큼 반복순회하면서 right 인덱스 값이 i보다 크면 left와 i 인덱스 교환
  left 변수에서 ++를 수행 
• left 변수와 right 위치 교환
• 재귀호출로 left 인덱스를 기준으로 왼쪽, 오른쪽 quicksort 함수 호출

 

 

Go 소스 코드

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
    //배열 무작위 생성 
	slice := generateSlice(20)
    //정렬 전 배열 
	fmt.Println("\n--- Unsorted --- \n\n", slice) 
    //퀵정렬 함수 호출 
	quicksort(slice)
    //정렬 후 배열 
	fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}

// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
    //slice 초기화 
	slice := make([]int, size, size)
    //유닉스시간 나노초 
	rand.Seed(time.Now().UnixNano())
	
    //1부터 999 난수 - 1부터 999난수를 원소로하는 배열 생성 
    for i := 0; i < size; i++ {
		slice[i] = rand.Intn(999) - rand.Intn(999)
	}
	return slice
}
 
func quicksort(a []int) []int {

    //배열 길이가 2 미만이면 a를 리턴 
    if len(a) < 2 {
        return a
    }
     
    //left는 0, right는 배열 길이 - 1 
    left, right := 0, len(a)-1
     
    //pivot은 랜덤난수를 a 길이로 나눈 나머지 
    pivot := rand.Int() % len(a)
     
    //right와 pivot 위치 바꾸기 
    a[pivot], a[right] = a[right], a[pivot]
     
    //a의 길이만큼 반복  right 인덱스가 i보다 크면  left와 i 원소 위치 교환, 이후 left에 ++를 대입 
    for i, _ := range a {
        if a[i] < a[right] {
            //i요소가 right보다 작으면 
            //a left와 a i의 위치를 교환 
            a[left], a[i] = a[i], a[left]
            //left ++ 
            left++
        }
    }
     
    //left와 right 위치 교환 
    a[left], a[right] = a[right], a[left]
     
    //재귀호출 
    quicksort(a[:left])
    quicksort(a[left+1:])
     
    return a
}

 

 

출력 값

go run quick_Sort.go 

--- Unsorted --- 

 [291 377 604 -127 -212 419 -26 -318 -525 391 229 -564 -335 242 68 -288 -242 -84 343 188]

--- Sorted ---

 [-564 -525 -335 -318 -288 -242 -212 -127 -84 -26 68 188 229 242 291 343 377 391 419 604]