[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / r / s / t / u / v / vg / vm / vmg / vr / vrpg / vst / w / wg] [i / ic] [r9k / s4s / vip / qa] [cm / hm / lgbt / y] [3 / aco / adv / an / asp / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / qst / sci / soc / sp / tg / toy / trv / tv / vp / wsg / wsr / x] [Settings] [Search] [Mobile] [Home]
Board
Settings Mobile Home
/wsr/ - Worksafe Requests

[Advertise on 4chan]


Thread archived.
You cannot reply anymore.


[Advertise on 4chan]


File: confuse.jpg (38 KB, 362x346)
38 KB
38 KB JPG
Say you have some hardware that finds the minimum of k or fewer elements in one comparison step; design an efficent algo based on Merge sort to sort n elements using this cool hardware.

I know I must separate the array into k sized chunks, but I am not so sure where to go from there.
>>
>>926198
t[] sort_things(t[] a)
if (a.length <= k) {
for 1 to k {
find_lowest_thing_in_a_and_move_it_to_b()}
return b;}

if (a.length > k) {
t[][] divided_a;

divide_a_into_divided_a;
for b in divided_a: sort_things(b)

t[] c
while true {
if all_elements_are_empty_arrays break;
// consider lowest value of each (now sorted) array in divided_a
// pop lowest lowest value into c
}
return c;
}



Delete Post: [File Only] Style:
[Disable Mobile View / Use Desktop Site]

[Enable Mobile View / Use Mobile Site]

All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.