In-place array reordering?

by

With mutating indices :(. Without looks hard (see stable in-place mergesort).

a = [8, 6, 7, 5, 3, 0, 9]
indices = [3, 6, 2, 4, 0, 1, 5]

for i in xrange(len(a)):
    x = a[i]
    j = i
    while True:
        k = indices[j]
        indices[j] = j
        if k == i:
            break
        a[j] = a[k]
        j = k
    a[j] = x

print a

More Related Contents:

  1. Print two-dimensional array in spiral order
  2. How to find max. and min. in array using minimum comparisons?
  3. How to find repeating sequence of characters in a given array?
  4. maximize the top element of the stack after performing exactly K operations
  5. How to sort in-place using the merge sort algorithm?
  6. Searching array reports “not found” even though it’s found
  7. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  8. Finding three elements in an array whose sum is closest to a given number
  9. Given an array of numbers, return array of products of all other numbers (no division)
  10. Array versus linked-list
  11. Algorithm to find k smallest numbers in array of n items
  12. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  13. Can min/max of moving window achieve in O(N)?
  14. Why does cache locality matter for array performance?
  15. Weighted random selection from array
  16. How to find a duplicate element in an array of shuffled consecutive integers?
  17. Binary Search in Array
  18. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  19. Given an array, find out the next smaller element for each element
  20. Finding neighbours in a two-dimensional array
  21. Binary Search algorithm implementations
  22. Find the 2nd largest element in an array with minimum number of comparisons
  23. Algorithm to rotate an array in linear time
  24. Maximum single-sell profit
  25. A data structure supporting O(1) random access and worst-case O(1) append?
  26. Median of 5 sorted arrays
  27. find pair of numbers in array that add to given sum
  28. Regarding in-place merge in an array
  29. Finding kth smallest number from n sorted arrays
  30. Algorithm to apply permutation in constant memory space

Leave a Comment