Sorting_Algorithms/tim_sort.gd at main · ADOGamedev/Sorting_Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
extends Node

var acumulated_delay = 0

func tim_sort(arr : Array, hash : Dictionary, bars_cont : HBoxContainer):
	var r = get_run_size(arr)
	var runs = []
	for i in range(0, len(arr), r):
		var start = i
		var end = min(i + r, len(arr))
		runs.append([start, end])
		for j in range(start, end):
			var k = j
			while k > start and arr[k] < arr[k - 1]:

				owner.owner.comparisons += 1
				owner.owner.array_accesses += 2

				swap(k, k - 1, arr, hash, bars_cont)
				await delay()

				hash[arr[k]].unselect()
				hash[arr[k - 1]].unselect()
				k -= 1

	await merge_sort(arr, hash, bars_cont, runs)
	owner.owner.finish_sorting()

func merge_sort(arr : Array, hash : Dictionary, bars_cont : HBoxContainer, runs : Array):
	if len(runs) == 1:
		return

	var new_runs = []
	var new_arr = []
	for i in range(0, len(runs) - 1, 2):
		var start1 = runs[i][0]
		var end1 = runs[i][1]
		var end2 = runs[i + 1][1]
		var left = arr.slice(start1, end1)
		var right = arr.slice(end1, end2)
		new_runs.append([start1, end2])
		new_arr.append_array(await merge(left, right, start1, hash, bars_cont))

	await merge_sort(new_arr, hash, bars_cont, new_runs)

func merge(left : Array, right : Array, start : int, hash : Dictionary, bars_cont : HBoxContainer):
	var l = 0
	var r = 0
	var res = []

	while l < len(left) and r < len(right):
		owner.owner.comparisons += 1
		owner.owner.array_accesses += 3

		if left[l] <= right[r]:
			await add(res, left, l, start, hash, bars_cont)
			hash[res[l]].select()
			await delay()
			hash[res[l]].unselect()
			l += 1
		else:
			await add(res, right, r, start, hash, bars_cont)
			hash[res[r]].select()
			await delay()
			hash[res[r]].unselect()
			r += 1

	while l < len(left):
		await add(res, left, l, start, hash, bars_cont)
		hash[res[l]].select()
		await delay()
		hash[res[l]].unselect()
		l += 1

	while r < len(right):
		await add(res, right, r, start, hash, bars_cont)
		hash[res[r]].select()
		await delay()
		hash[res[r]].unselect()
		r += 1

	return res

func add(res : Array, arr : Array, i : int, start : int, hash : Dictionary, bars_cont : HBoxContainer):
	owner.owner.array_accesses += 1

	res.append(arr[i])

	owner.owner.play_pop(hash[arr[i]].num)
	bars_cont.move_child(hash[arr[i]], start + len(res) - 1)

func get_run_size(arr : Array):
	var n = len(arr)
	var r = 0
	while n >= 64:
		r |= n % 2
		n /= int(2)
	return n + r

func delay():
	acumulated_delay += owner.owner.delay / 2000.0
	if acumulated_delay > (1.0 / Engine.get_frames_per_second()):
		await get_tree().create_timer(acumulated_delay).timeout
		acumulated_delay = 0

func swap(i : int, j : int, arr : Array, hash : Dictionary, bars_cont : HBoxContainer):
	hash[arr[i]].select()

	owner.owner.play_pop(hash[arr[i]].num)
	owner.owner.play_pop(hash[arr[j]].num)
	owner.owner.array_accesses += 4

	var tmp = arr[i]

	bars_cont.move_child(hash[arr[j]], i)
	hash[arr[j]].select()
	arr[i] = arr[j]

	bars_cont.move_child(hash[tmp], j)
	hash[tmp].select()
	arr[j] = tmp