Databases
StackOverflow2013
Postsdbo
POQuicksort with insertion Sort finish - where am I going wrong?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POQuicksort with insertion Sort finish - where am I going wrong?
    primarykey
    data
    text
    <p>I am working on a project for a class. We are to write a quick-sort that transitions to a insertion sort at the specified value. Thats no problem, where I am now having difficulty is figuring out why I am not getting the performance I expect.</p> <p>One of the requirements is that it must sort an array of 5,00,000 ints in under 1,300 ms (this is on standard machines, so CPU speed is not an issue). First of all, I can't get it to work on 5,000,000 because of a stack overflow error (too many recursive calls...). If I increase the heap size, I am still getting a lot slower than that.</p> <p>Below is the code. Any hints anyone?</p> <p>Thanks in advance </p> <pre><code>public class MyQuickSort { public static void sort(int [] toSort, int moveToInsertion) { sort(toSort, 0, toSort.length - 1, moveToInsertion); } private static void sort(int[] toSort, int first, int last, int moveToInsertion) { if (first &lt; last) { if ((last - first) &lt; moveToInsertion) { insertionSort(toSort, first, last); } else { int split = quickHelper(toSort, first, last); sort(toSort, first, split - 1, moveToInsertion); sort(toSort, split + 1, last, moveToInsertion); } } } private static int quickHelper(int[] toSort, int first, int last) { sortPivot(toSort, first, last); swap(toSort, first, first + (last - first)/2); int left = first; int right = last; int pivotVal = toSort[first]; do { while ( (left &lt; last) &amp;&amp; (toSort[left] &lt;= pivotVal)) { left++; } while (toSort[right] &gt; pivotVal) { right--; } if (left &lt; right) { swap(toSort, left, right); } } while (left &lt; right); swap(toSort, first, right); return right; } private static void sortPivot(int[] toSort, int first, int last) { int middle = first + (last - first)/2; if (toSort[middle] &lt; toSort[first]) swap(toSort, first, middle); if (toSort[last] &lt; toSort[middle]) swap(toSort, middle, last); if (toSort[middle] &lt; toSort[first]) swap(toSort, first, middle); } private static void insertionSort(int [] toSort, int first, int last) { for (int nextVal = first + 1; nextVal &lt;= last; nextVal++) { int toInsert = toSort[nextVal]; int j = nextVal - 1; while (j &gt;= 0 &amp;&amp; toInsert &lt; toSort[j]) { toSort[j + 1] = toSort[j]; j--; } toSort[j + 1] = toInsert; } } private static void swap(int[] toSort, int i, int j) { int temp = toSort[i]; toSort[i] = toSort[j]; toSort[j] = temp; } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USReese Moore
    1. USaddisonj
    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. This table or related slice is empty.
    1. COWhat class is this? highschool/college? I'm curious
      singulars
      1. POQuicksort with insertion Sort finish - where am I going wrong?
      1. USCarlo del Mundo
    2. COCollege, 2nd year, so I don't imagine its anything TO complex... I think I may just have a small error...
      singulars
      1. POQuicksort with insertion Sort finish - where am I going wrong?
      1. USaddisonj
    3. COWhat's `moveToInsertion`?
      singulars
      1. POQuicksort with insertion Sort finish - where am I going wrong?
      1. UShelpermethod
 

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