V language : Introspective Sort

Introspective Sort

IntroSort (Introspective Sort) 인트로 정렬은, Quick Sort의 장점을 유지하면서,

최악 시나리오 O(n^2)를 해결하려 만들어진 (Quick Sort + Heap Sort + Insertion Sort) 하이브리드 알고리즘이다.

(C++ 기본 정렬 알고리즘, std::sort)

 

모든 상황에서 시간 복잡도 : O(nlogn), 공간 복잡도는 O(logn)이며, inplace, not stable한 알고리즘이다.

(in-place란, 보조 데이터 구조를 사용하지 않고, 작동하는 알고리즘)

 

 Quick Sort로 시작해서, Recursion max-depth (log(len(array)) 에 도달하면 Heap Sort로 정렬하고,

그리고, 파티션 크기가 보통 16보다 작으면 Insertion Sort로 정렬한다.

(Quick Sort (max-depth 도달)-> Heap Sort / (파티션 크기 작을 때)Insertion Sort)

 

※ 현재 V는 C처럼 수정된 Quick Sort를 사용 중이다.

 

1. Psuedo Code

 # Intro Sort 주요 특징
 /*
 1. 3개의 요소들에게서 중간값(median) 구하기
 2. 크기가 작은 (보통 16) 파티션들은 Insertion Sort
 3. Quick Sort 하다가 max recursion depth 도달하면 Heap Sort
 */
 
procedure sort(A : array):
    let maxdepth = ⌊log(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    size ← endIdx - startIdx
    if n ≤ 1:
        return  // base case
    else if maxdepth = 0:
        heapsort(A)
    else if size < 16:
        insertsort(A)
    else:
    	// pivot, p
        p ← partition(A)  
        introsort(A[0:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)
        

 

2. V 소스

import math

fn main() {
    mut test_arr := [1,2,3,4,5,4,3,2,-1,0,0,13]
    
    // Introspective Sort
    mut max_depth := 2 * (math.log2(test_arr.len) - 1)
    threshold := 16
    introsort_helper(mut test_arr, 0, test_arr.len, threshold, int(max_depth))
}

// Time Complexity O(nlogn) | Space Complexity O(logn) | not stable
[direct_array_access]
fn introsort_helper(mut array []int, start int, end_ int, threshold int, max_depth_ int) []int {
    mut max_depth := max_depth_
    mut end := end_

    for end - start > threshold {
        if max_depth == 0 {
            return heap_sort(mut array)
        }
        max_depth--

        median := median_of_three(mut array, start, start + ((end - start) / 2) + 1, end - 1)
        p := partition(mut array, start, end, median)
        introsort_helper(mut array, p, end, threshold, max_depth)
        end = p
    }
    return insertion_sort(mut array, start, end)
}

[direct_array_access]
fn partition(mut array []int, low int, high int, pivot int) int {
    mut i := low
    mut j := high
    for true {
        for array[i] < pivot {
            i++
        }
        j--
        for pivot < array[j] {
            j--
        }
        if i>= j {
            return i
        }
        array[i], array[j] = array[j], array[i]
        i++
    }
    return i
}

fn median_of_three(mut array []int, lowIdx int, midIdx int, highIdx int) int {
    if (array[lowIdx] - array[midIdx]) * (array[highIdx] - array[lowIdx]) >= 0{
        return array[lowIdx]
    }
    else if (array[midIdx] - array[lowIdx]) * (array[highIdx] - array[midIdx]) >= 0{
        return array[midIdx]
    }
    else {
        return array[highIdx]
    }    
}

/* 	Insertion Sort
    Best O(n) Time | O(1) Space
    Average O(n^2) Time | O(1) Space
    Worst (On^2) Time | O(1) Space
*/
[direct_array_access]
fn insertion_sort(mut array []int, start int, end int) []int {
    for i in start..end {  // range(1, len(array))
        mut j := i
        key := array[i]

        for j != start && array[j - 1] > key {
            array[j] = array[j - 1]
            j--
        }
        array[j] = key
    }
    return *array
}

/*  Heap Sort
    Time Complexity O(nlogn) | Space Complexity O(1)
*/
[direct_array_access]
fn heap_sort(mut array []int) []int {
    n := array.len
    
    for i := n/2; i > -1; i-- {
        heapify(mut array, n, i)  // Max-heapify
    }
    
    for i := n - 1; i > 0; i-- {
        array[i], array[0] = array[0], array[i]
        heapify(mut array, i, 0)
    }
    
    return *array
}

[direct_array_access]
fn heapify(mut array []int, n int, i int) {
    mut largest := i
    left := 2 * i + 1
    right := 2 * i + 2

    if left < n && array[i] < array[left] {
        largest = left
    }

    if right < n && array[largest] < array[right] {
        largest = right
    }

    if largest != i {
        array[i], array[largest] = array[largest], array[i]
        heapify(mut array, n, largest)
    }
}

 

3. 결과

test_arr = 10_000 len of random array

Count Sort: 0.417ms

Introspective Sort: 0.981ms

Quick Sort: 2ms

Heap Sort: 3ms

Insertion Sort: 63ms

Bubble Sort: 420ms

Merge Sort: 831ms

 

4. 참고

Python Introspective Sort : https://choiseokwon.tistory.com/209

파이썬 Introspective Sort (내성 정렬) 알고리즘

Github Algorithms in V language : https://github.com/Alfex4936/V-algorithms

Alfex4936/V-algorithms