Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If seeks are trivial, then the minimum number of swaps will be determined by the number of cycles. It would follow a principle similar to <a href="http://en.wikipedia.org/wiki/Cuckoo_hashing" rel="nofollow">Cuckoo Hashing</a>. You take the first value in the permutation, and look at the value at the index of the value at the original index. If those match, then swap for a single operation. </p> <p>[<strong>3</strong> 2 1] : Value 3 is at index one, so look at the value at index 3. <br /> [3 2 <strong>1</strong>] : Value 1 is at index 3, so a two index cycle exists. Swap these values.</p> <p>If not, push the first index onto a stack and seek the index for the value of the second index. There will eventually be a cycle. At that point, start swapping by popping values off the stack. This will take a number of swaps equal to n-1, where n is the length of the cycle.</p> <p>[<strong>3</strong> 1 2] : Value 3 is at index one, so look at the value at index 3. <br /> [3 1 <strong>2</strong>] : Value 2 is at index 3, so add 3 to the stack and seek to index 2. Also store 3 as the beginning value of the cycle.<br /> [3 <strong>1</strong> 2] : Value 1 is at index 2, so add 2 to the stack and seek to index 1. <br /> [<strong>3</strong> 1 2] : Value 3 is the beginning of the cycle, so swap pop 2 off the stack and swap values 1 and 2. <br /> [1 3 2] : Pop 3 off the stack and swap 2 and 3, resulting in a sorted list with 2 swaps. <br /> [1 2 3]</p> <p>With this algorithm, the maximum number of swaps will be N-1, where N is the total number of values. This occurs when there is an N length cycle.</p> <p><strong>EDIT :</strong> This algorithm gives the minimum number of swaps, but not necessarily the minimum value using the min(x, y) function. I haven't done the math, but I believe that the only time when swap(x, y) = {swap(1, x), swap(1, y), swap(1, x)} shouldn't be used is when x in {2,3} and n &lt; 2; Should be easy enough to write that as a special case. It may be better to check and place 2 and 3 explicitly, then follow the algorithm mentioned in the comments to achieve sorting in two operations.</p> <p><strong>EDIT 2 :</strong> Pretty sure this will catch all cases.</p> <pre><code>while ( unsorted ) { while ( 1 != index(1) ) swap (1 , index (1) ) if (index(2) == value@(2)) swap (2, value@(2) ) else swap (1 , highest value out of place) } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POSorting a permutation with minimum cost
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USWLPhoenix
    1. USWLPhoenix
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COIt's not letting me edit for some reason, but that if should also have the condition that 2 and value@(2) are the only values out of place.
      singulars
      1. PO
      1. USWLPhoenix
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload