feat: add sort module to stdlib

[HuangHongkai]

related issue: https://github.com/d5/tengo/issues/398 sort module source code

_sort := func(arr, left, right, less) {
	if right-left <= 0 {
		return arr
	}
	i := left

	for j := left; j < right; j++ {
		if less(j, right) {
			if i != j {
				tmp := arr[i]
				arr[i] = arr[j]
				arr[j] = tmp
			}
			i++
		}
	}

	if i != right {
		tmp := arr[i]
		arr[i] = arr[right]
		arr[right] = tmp
	}

	_sort(arr, left, i-1, less)
	_sort(arr, i+1, right, less)
	return arr
}

export {
	sort: func(arr, less) {
		return _sort(arr, 0, len(arr)-1, less)
	}
}

[geseq]

Thanks for the PR.

Can you please add a well formatted .tengo file similar to https://github.com/d5/tengo/blob/82b543fd980aaacab9f24c7705878df260d261f6/stdlib/srcmod_enum.tengo

and then code generate using https://github.com/d5/tengo/blob/82b543fd980aaacab9f24c7705878df260d261f6/stdlib/gensrcmods.go

[NAICOLAS]

@geseq Any updates on this? :)

[NAICOLAS]

@HuangHongkai

[NAICOLAS]

// Quicksort
_swap := func(arr, i, j) {
	tmp := arr[i]
	arr[i] = arr[j]
	arr[j] = tmp
}

_partition := func(arr, low, high, less) {
	pivot := arr[high]
	i := low - 1
	
	for j := low; j < high; j++ {
		if less(arr[j], pivot) {
			i++
			_swap(arr, i, j)
		}
	}
	
	_swap(arr, i+1, high)
	
	return i + 1
}

_quicksort := func(arr, low, high, less) {
	if low < high {
		pivotIndex := _partition(arr, low, high, less)
		_quicksort(arr, low, pivotIndex-1, less)
		_quicksort(arr, pivotIndex+1, high, less)
	}
}

qsort := func(arr, less) {
	_quicksort(arr, 0, len(arr)-1, less)
	
	return arr
}

[HuangHongkai]

@geseq hello, I updated my code, please help to review

[HuangHongkai]

Inline the swap function to reduce function calls

[huixiaohuang]

hi @HuangHongkai, I am afraid some of the unit test cases in your commit won't work. would you like to try the sorting code below and request another PR? I believe it should work. let me know if any questions :)

_swap := func(arr, left, right) {
    if arr == undefined || len(arr) <= 1 || left < 0 || left >= len(arr) || right < 0 || right >= len(arr) || left >= right {
        return
    }
    temp := arr[right]
    arr[right] = arr[left]
    arr[left] = temp
}

_sort := func(arr, left, right, less) {
    if arr == undefined || len(arr) <= 1 || left < 0 || left >= len(arr) || right < 0 || right >= len(arr) || left >= right {
        return arr
    }
    idx := left
    for i := left; i < right; i++ {
        if less(i, right) {
            _swap(arr, idx, i)
            idx++
        }
    }
    _swap(arr, idx, right)
    _sort(arr, left, idx-1, less)
    _sort(arr, idx+1, right, less)
    return arr
}

export {
    sort: func(arr, less) {
        if arr == undefined || len(arr) <= 1 {
            return arr
        }
        return _sort(arr, 0, len(arr)-1, less)
    }
}