Permute Array | Algorithms Notes

Permute Array | Algorithms Notes

Given an array of n numbers and a permutation as a oracle, design an algorithm to permute the array. Solution: Classical solution is to consider the cycle of the permutation. For each cycle, we fix a leader. Then, loop through all elements in the array. If the current element is a leader, than rotate all elements in the same into correct positions. The running time depends on how to determine leader. One way is to define the smallest number in the cycle as the leader of the cycle. Thus, for each element in the array, we can loop through the cycle containing this element and test whether this element is a leader. This algorithm takes O( ) in worst case but O(n lg n) in average [1]. There is an O(n lg n) time O(lg n) bit space algorithm [2]. If the permutation permute the array to a sorted array with distinct elements, then permutation can be done in linear time and O(1) space. [1] Alois Panholzer, Helmut Prodinger, Marko Riedel, "Permuting in place: analysis of two stopping rules,

Read full article from Permute Array | Algorithms Notes