 |
Attention | Topic was automatically imported from the old Question2Answer platform. |
 |
Asked By | Xx Void xX |
let’s say that we have a class merge_sorter.gd:
var _data_size : int
var _priority_callback : FuncRef
func setup(data_size : int, priority_callback : FuncRef)
func next_sort() -> Dictionary
setup() takes the size of the array it will be sorting and a callback to compare each index of the array
next_sort() sorts once, and returns a dictionary with “done” representing wether we’re done sorting and “indexes” representing 2 indexes to swap in the array
the idea is that we can repeatedly call merge_sorter.next_sort() and swap 2 indexes based on its return, we do so repeatedly untill the array is sorted, this
way we can display some visuals each time we get data from next_sort(), like sort vertical lines of different sizes one at a time etc…
now I know how to implement merge-sort but I’m really struggling (for the past 3 day to be exact) to implement the next_sort() function so that
we do one sort at a time. here’s what I have so far:
var _data_size : int
var _priority_callback : FuncRef
var _division_array : Array
var _pending_switches : Array # [[idx1, idx2], .. ]
func setup(data_size : int, priority_callback : FuncRef):
_data_size = data_size
_priority_callback = priority_callback
# skip the dividing step in the merge-sort algorithm
# we manualy split the array
_division_array.resize(_data_size)
for i in _data_size: _division_array[i] = [i]
_pending_switches.clear()
func next_step() -> Dictionary:
# merge first 2 nums, then next 2. combine them into 4, then merge another 2 and 2 into 4
# and merge the 4 and 4 into 8 etc.. it's like 2048 the game
# this way we can merge once, keep record of what has changed in that merge (_pending_switches)
# and for each call to this func, return 1 switch from the record, once the record is empty
# we merge the next 2 arrays and so on
var should_skip_to_next : bool = false
if _pending_switches.empty():
var prev_subarrs_size : int = 0 # size of all previous subarrays before _division_array[i-1]
# i.e index of first element in current subarray if _division_array was a 1d array instead of 2d
for i in range(1, _division_array.size()):
if (_division_array[i-1].size() == _division_array[i].size() ||
_division_array.size() == 2):
# combine the two subarrays
_division_array[i-1] = _merge(_division_array[i-1], _division_array[i])
_division_array.remove(i)
for j in _division_array[i-1].size():
var original_index : int = _division_array[i-1][j]
var new_index : int = prev_subarrs_size + j
if original_index == new_index: continue
# get rid of duplicates i.e [ [0,1], [1,0] ]
if (_pending_switches.has([original_index, new_index]) ||
_pending_switches.has([new_index, original_index])) == false:
_pending_switches.append([original_index, new_index])
if _pending_switches.empty() && _division_array.size() > 1:
# arrays merged perfectly without having to change indexes i,e [1,2,3] + [4,5,6]
should_skip_to_next = true
break
else:
prev_subarrs_size += _division_array[i-1].size()
if should_skip_to_next:
return next_step()
elif _pending_switches.empty():
# still empty? we're done
return {"done":true}
else:
var indexes_to_switch : Array
indexes_to_switch.resize(2)
indexes_to_switch[0] = _pending_switches[0][0]
indexes_to_switch[1] = _pending_switches[0][1]
# THIS is where we have a problem
# for example let's say that the array to sort is [7, 6, 3, 4, 0, 2, 1, 9, 5, 8]
# and _pending_switches = [[8, 0], [4, 2], [0, 3], [6, 5], [3, 7], [9, 8], [7, 9]]
# by the time we apply to 4th switch [3, 7], we would have already applied the 2nd switch
# [0, 3] meaning that the index 3 in [3, 7] will not be the same because it was switched with
# something else previously
# WHAT DO I DO HERE?
_pending_switches.remove(0)
return {"done":false, "indexes": [indexes_to_switch[0], indexes_to_switch[1]]}
don’t worry about the _merge() function all it does is merge 2 arrays into 1 sorted array
my appologies for the big function, I have to show to full code for the problem to be understood,
here’s a short description:
at first we skip the dividing part of the merge sort algorithm and manualy split indexes into _division_array in the form of array, each array containing one index
on each call to next_step() we search _division_array for 2 arrays of the same size next to each other, once found we merge them together, now a single
merge can change more than 1 index, but we need to return 1 swap at a time so we use _pending_switches to keep track of all the swaps we need to return, on each
call to next_step() we return 1 of the swaps (or switches) stored into _pending_switches untill it becomes empty, in which case we repeat the process again
untill all subarrays in _division_array are merged into one array, it’s basicaly merge-sort in slow motion I guess
the problem is that as you can read at the bottom of next_step() is how can I return one swap at a time from _pending_switches in the right order?
if this is unclear here is a simplified version of the problem:
var data_array : Array = [7, 6, 3, 4, 0, 2, 1, 9, 5, 8]
var _division_array : Array = [[8,0],[4,2],[0,3],[6,5],[3,7],[9,8],[7,9]]
func next_step():
# _division_array contains all the swaps needed to sort data_array
# but how do I apply them? if I just read each subarray in _division_array
# and swap indexes based on that, some entries in _division_array will become invalid
# for example swaping based on [0,3] will break the entry [3,7] since 3 is now at a different index
??