;============================================================
;  アルゴリズム 11〜15: ソート
;    11. QuickSort
;    12. MergeSort
;    13. HeapSort
;    14. RadixSort (LSD)
;    15. CountingSort
;============================================================

#include "hsp3cl_net_64.as"

; ----- 11. QuickSort (in-place) -----
#module
#deffunc quicksort array _a, int _lo, int _hi, \
	local _i, local _j, local _pivot, local _t
	if _lo >= _hi : return
	_pivot = _a(_hi)
	_i = _lo - 1
	repeat _hi - _lo
		_j = _lo + cnt
		if _a(_j) <= _pivot {
			_i++
			_t = _a(_i) : _a(_i) = _a(_j) : _a(_j) = _t
		}
	loop
	_t = _a(_i + 1) : _a(_i + 1) = _a(_hi) : _a(_hi) = _t
	quicksort _a, _lo, _i
	quicksort _a, _i + 2, _hi
	return
#global

; ----- 12. MergeSort -----
#module
#deffunc mergesort array _a, int _lo, int _hi, \
	local _mid, local _i, local _j, local _k, local _n
	if _lo >= _hi : return
	_mid = (_lo + _hi) / 2
	mergesort _a, _lo, _mid
	mergesort _a, _mid + 1, _hi
	_n = _hi - _lo + 1
	dim _tmp, _n
	_i = _lo : _j = _mid + 1 : _k = 0
	repeat
		if _i > _mid : break
		if _j > _hi : break
		if _a(_i) <= _a(_j) {
			_tmp(_k) = _a(_i) : _i++
		} else {
			_tmp(_k) = _a(_j) : _j++
		}
		_k++
	loop
	repeat
		if _i > _mid : break
		_tmp(_k) = _a(_i) : _i++ : _k++
	loop
	repeat
		if _j > _hi : break
		_tmp(_k) = _a(_j) : _j++ : _k++
	loop
	repeat _n
		_a(_lo + cnt) = _tmp(cnt)
	loop
	return
#global

; ----- 13. HeapSort -----
#module
#deffunc heap_fix array _a, int _n, int _i, \
	local _largest, local _l, local _r, local _t
	_largest = _i
	_l = 2 * _i + 1
	_r = 2 * _i + 2
	if _l < _n : if _a(_l) > _a(_largest) : _largest = _l
	if _r < _n : if _a(_r) > _a(_largest) : _largest = _r
	if _largest != _i {
		_t = _a(_i) : _a(_i) = _a(_largest) : _a(_largest) = _t
		heap_fix _a, _n, _largest
	}
	return

#deffunc heapsort array _a, int _n, \
	local _i, local _t
	repeat _n / 2
		_i = _n / 2 - 1 - cnt
		heap_fix _a, _n, _i
	loop
	repeat _n - 1
		_i = _n - 1 - cnt
		_t = _a(0) : _a(0) = _a(_i) : _a(_i) = _t
		heap_fix _a, _i, 0
	loop
	return
#global

; ----- 14. RadixSort (LSD、32bit 非負整数) -----
#module
#deffunc radixsort array _a, int _n, \
	local _pass, local _shift, local _i, local _b
	if _n <= 1 : return
	dim _tmp, _n
	repeat 4
		_pass = cnt
		_shift = _pass * 8
		dim _cntbuf, 256
		repeat _n
			_b = (_a(cnt) >> _shift) & 0xFF
			_cntbuf(_b)++
		loop
		repeat 255
			_cntbuf(cnt + 1) += _cntbuf(cnt)
		loop
		repeat _n
			_i = _n - 1 - cnt
			_b = (_a(_i) >> _shift) & 0xFF
			_cntbuf(_b)--
			_tmp(_cntbuf(_b)) = _a(_i)
		loop
		repeat _n : _a(cnt) = _tmp(cnt) : loop
	loop
	return
#global

; ----- 15. CountingSort (非負整数、最大値 K) -----
#module
#deffunc counting_sort array _a, int _n, int _k, \
	local _i, local _idx
	dim _cntarr, _k + 1
	repeat _n : _cntarr(_a(cnt))++ : loop
	_idx = 0
	repeat _k + 1
		_i = cnt
		repeat _cntarr(_i) : _a(_idx) = _i : _idx++ : loop
	loop
	return
#global

#module
#deffunc print_arr str _label, array _a, int _n, local _line
	sdim _line, 256
	_line = _label + ": ["
	repeat _n
		_line += "" + _a(cnt)
		if cnt < _n - 1 : _line += ", "
	loop
	_line += "]"
	mes _line
	return
#global

; ===== デモ =====
	mes "=== Sorting algorithms ==="
	N = 10
	dim data, N
	data = 64, 34, 25, 12, 22, 11, 90, 50, 3, 77

	dim a, N : repeat N : a(cnt) = data(cnt) : loop
	print_arr "Input    ", a, N

	repeat N : a(cnt) = data(cnt) : loop
	quicksort a, 0, N - 1
	print_arr "QuickSort", a, N

	repeat N : a(cnt) = data(cnt) : loop
	mergesort a, 0, N - 1
	print_arr "MergeSort", a, N

	repeat N : a(cnt) = data(cnt) : loop
	heapsort a, N
	print_arr "HeapSort ", a, N

	repeat N : a(cnt) = data(cnt) : loop
	radixsort a, N
	print_arr "RadixSort", a, N

	repeat N : a(cnt) = data(cnt) : loop
	counting_sort a, N, 100
	print_arr "Counting ", a, N
	end 0