1

I have an array like this:

$a = [2, 1, 1, 2, 3, 1, 3, 2];

I need to sort it, by using an external variable. But I need the following output:

$output = [
    [0, s],  // Move $a[0] to storage
    [5, 0],  // Move $a[5] to $[0]
    [s, 5],  // Move storage to $a[5]
    [4, s],  // Move $a[4] to storage
    [7, 4],  // Move $a[7] to $a[4]
    [s, 7]   // Move storage to $[7]
];

I need an algorithm to make an array, a delimitered string, or any kind of output, containing the steps to sort the array.

Mainly in PHP but I can implement it from any lang.

Zoltán Fekete
  • 504
  • 1
  • 6
  • 22
  • What is `s`? Is that supposed to be a character string `'s'`? – Barmar Aug 29 '14 at 10:04
  • So, basically, you want to produce an assembly-language-like program that would sort the given array? – georg Aug 29 '14 at 10:04
  • 2
    Write your own sort function, using an algorithm like bubble sort or quicksort. Whenever it swaps a pair of elements, it should add what it's doing to `$output`. – Barmar Aug 29 '14 at 10:06
  • The 's' means as the comment tells. 's' means a variable like $s – Zoltán Fekete Aug 29 '14 at 10:07
  • See also http://stackoverflow.com/questions/21452645/finding-minimal-distance-between-unsorted-and-sorted-lists – georg Aug 29 '14 at 11:22

3 Answers3

2

A fun if perhaps not that efficient idea:

Determine the count and sorted offset of each element:

$a = [2, 1, 1, 2, 3, 1, 3, 2];
$count_and_offset = [1 => [3,0], 2 => [3,3], 3 => [2,6]]

Determine the permutation,

$a_permutation = [5, 2, 3, 4, 8, 1, 7, 6];

Enumerate the cycles (http://en.wikipedia.org/wiki/Cyclic_permutation),

(1586)(2)(3)(4)(7)

Make a list (example is not zero-based),

[[6, s]
,[8, 6]
,[5, 8]
,[1, 5]
,[s, 1]]
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
1

You can use insertion sort (or do similar thing for other sorting algorithm like bubble sort or quicksort)

Pseudo code (which I took from wiki)

for i ← 1 to length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1

So for the each swap step, you just need to print

[j , s]
[j - 1,j]
[s , j - 1]
Pham Trung
  • 11,204
  • 2
  • 24
  • 43
0

You are looking for array_map : http://php.net/manual/fr/function.array-map.php (old answer : usort : http://php.net/manual/fr/function.usort.php) : create a custom function which make what you are looking for, and call it with array_map.

Kevin
  • 1,000
  • 2
  • 10
  • 31