Library sort: Difference between revisions

Revision as of 13:40, 17 December 2019

Revision as of 13:42, 17 December 2019

Line 24:

===Algorithm ===

Let us say we have an array of n elements. We choose the gap we intend to give. Then we would have a final array of size (1 + ε)n. The algorithm works in log n rounds. In each round we insert as many elements as there are in the final array already, before re-balancing the array. For finding the position of inserting, we apply Binary Search in the final array and then swap the following elements till we hit an empty space. Once the round is over, we re-balance the final array by inserting spaces between each element.

Let us say we have an array of n elements. We choose the gap we intend to

give. Then we would have a final array of size (1 + ε)n. The algorithm works

in log n rounds. In each round we insert as many elements as there are in

the final array already, before re-balancing the array. For finding the position

of inserting, we apply Binary Search in the final array and then swap the

following elements till we hit an empty space. Once the round is over, we

re-balance the final array by inserting spaces between each element.

Following are three important steps of the algorithm:

# '''Binary Search''': Finding the position of insertion by applying binary search within the already inserted elements. This can be done by linearly moving towards left or right side of the array if you hit an empty space in the middle element.

1. Binary Search:

# '''Insertion''': Inserting the element in the position found and swapping the following elements by 1 position till an empty space is hit.

Finding the position of insertion by applying binary search within the

# '''Re-Balancing''': Inserting spaces between each pair of elements in the array. This takes linear time, and because there are log n rounds in the algorithm, total re-balancing takes O(n log n) time only.

already inserted elements. This can be done by linearly moving towards

left or right side of the array if you hit an empty space in the middle

element.

2. Insertion:

Inserting the element in the position found and swapping the following

elements by 1 position till an empty space is hit.

3. Re-Balancing:

Inserting spaces between each pair of elements in the array. This takes linear time, and

because there are log n rounds in the algorithm, total re-balancing takes

O(n log n) time only.

===Pseudocode===