Half-access sorting is a sorting algorithm that is not eactly an efficiency-based algorithm. It's what i'd call a "theory algorithm". Or something. Basically, it's trying to sort the array, with the following restrictions.
The left half of the array is free to access and modify
The right half can only be read, not accessed
The only Exception here is that you can shift any item from the left half to the last item's spot, like a Radix LSD sort or shove sort or something.
The sort works by moving the n/2 largest items to the first half, binary insertion sorting them, shifting them to the other side and sorting the first half again. Should be sorted. Sorry if my explanation is bad, just look in the video.
How it finds and shifts the largest items to the first half:
Make an auxillary array of exclusions (if not yet), set all to -1
Scan the array for the highest item whose value in the exclusion list is -1
Progressively shift items, moving the shift spot forward if the item being shifted has a value of 0 in the exclusion list. Do the exact same shift for the auxillary array so they line up. Once the selected item we are trying to get reaches the first half, mark it as exclusion 0 in exclusion list. Repeat this n/2 times. Now, sort the first half. We use binary insertion (but since it tends to reverse, this will be changed with the v2). Shift all the items to the end, then sort the half again. This time it's the first half, which should be sorted.
Негізгі бет Half-access Sorting
Пікірлер: 20