Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This looks suspiciously similar to <a href="http://en.wikipedia.org/wiki/Bubble_sort" rel="nofollow">bubble sort</a>, in which you need up to n^2 movements.</p> <p>And the interesting fact is that, simple bubble sort actually achieves your goal to find the minimum number of switches! (proof below)</p> <p>In that case, we don't need to further improve algorithms using double loops, and it's actually possible using double loops (in C++):</p> <pre><code>int switch = 0; for(int repeat=0; repeat&lt;n; repeat++){ for(int j=0; j&lt;n-repeat; j++){ if(arr[j]&gt;arr[j+1]){ int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; switch = switch + 1 } } } </code></pre> <p>The <code>switch</code> is the result.<br> <code>arr</code> is the array containing the numbers.<br> <code>n</code> is the length of the array.</p> <p>Prove that this produces minimum number of switch:</p> <p>First, we note that the bubble sort essentially moves the highest element into the rightmost position in the array at each iteration (outer loop)</p> <p>Note that switching the highest element with any other element in the process does not change the relative order of other elements. And also any other switch operations done in between our attempt to move the highest element to its position will not change the number of switch required to move the highest element to place. And so we can interchange the switch operations such that the highest element is always switched first until it gets into position. Therefore switching the highest element into its position one at a time is optimum.</p>
    singulars
    1. This table or related slice is empty.
    1. POminimum switch to sorted permutation
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USjusthalf
    1. USjusthalf
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POminimum switch to sorted permutation
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COHave you run this for my test case? Does switch = 7?
      singulars
      1. PO
      1. USShane Hsu
    2. COYes, it is. What programming language do you normally use?
      singulars
      1. PO
      1. USjusthalf
    3. CONo, I'm wrong. It should be 6.
      singulars
      1. PO
      1. USShane Hsu
 

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