Databases
StackOverflow2013
Postsdbo
POIs this equivalent to insertion sort?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIs this equivalent to insertion sort?
    primarykey
    data
    text
    <p>Say we have a 0-indexed sequence S, take S[0] and insert it in a place in S where the next value is higher than S[0] and the previous value is lower than S[0]. Formally, S[i] should be placed in such a place where S[i-1] &lt; S[i] &lt; S[i+1]. Continue in order on the list doing the same with every item. Remove the element from the list before putting it in the correct place. After one iteration over the list the list should be ordered. I recently had an exam and I forgot insertion sort (don't laugh) and I did it like this. However, my professor marked it wrong. The algorithm, as far as I know, does produce a sorted list.</p> <p>Works like this on a list:</p> <pre><code>Sorting [2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9] [2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9] [2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9] [2, 5, 4, 7, 0, 6, 1, 8, 10, 3, 9] [2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9] [2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9] [2, 4, 5, 0, 6, 1, 7, 8, 10, 3, 9] [0, 2, 4, 5, 6, 1, 7, 8, 10, 3, 9] [0, 2, 4, 5, 1, 6, 7, 8, 10, 3, 9] [0, 1, 2, 4, 5, 6, 7, 8, 10, 3, 9] [0, 1, 2, 4, 5, 6, 7, 8, 3, 9, 10] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Got [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] </code></pre> <p>Since every time an element is inserted into the list up to (n-1) numbers in the list may be moved and we must do this n times the algorithm should run in O(n^2) time.</p> <p>I had a Python implementation but I misplaced it somehow. I'll try to write it again in a bit, but it's kinda tricky to implement. Any ideas?</p> <p>The Python implementation is here: <a href="http://dpaste.com/hold/522232/" rel="nofollow">http://dpaste.com/hold/522232/</a>. It was written by busy_beaver from reddit.com when it was discussed here <a href="http://www.reddit.com/r/compsci/comments/ejaaz/is_this_equivalent_to_insertion_sort/" rel="nofollow">http://www.reddit.com/r/compsci/comments/ejaaz/is_this_equivalent_to_insertion_sort/</a></p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJuan Pablo Santos
    1. USJuan Pablo Santos
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIs this equivalent to insertion sort?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIs this equivalent to insertion sort?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POIs this equivalent to insertion sort?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIf there are multiple possible positions, which one do you pick?
      singulars
      1. POIs this equivalent to insertion sort?
      1. USaaz
    2. CO@aaz the first you find.
      singulars
      1. POIs this equivalent to insertion sort?
      1. USJuan Pablo Santos
    3. COThis is not insertion sort. A fundamental feature of IS is, after M iterations, the first M elements are in order. The description you have given for the algorithm provides this albeit in a quite convoluted way.
      singulars
      1. POIs this equivalent to insertion sort?
      1. USCaptain Giraffe
 

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