Databases
StackOverflow2013
Postsdbo
POImplementing a sort class using templates
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POImplementing a sort class using templates
    text
    copied!<p>I posted last night about an array class, and now I'm having trouble with a sorting class. About half of the functions are defined, either by the professor or by the algorithms he gave us, but a lot of the definitions are confusing me. I'm not sure what makes them any different from the ones above it.</p> <pre><code>#ifndef SORTS_H #define SORTS_H #include &lt;iostream&gt; #include &lt;string&gt; #include "Array.h" using namespace std; template &lt;class T&gt; void insertionSort(Array&lt;T&gt; &amp;a); template &lt;class T&gt; void selectionSort(Array&lt;T&gt; &amp;a); template &lt;class T&gt; void selectionSort(T a[], int n); template &lt;class T&gt; void mergesort(T *input, int size); template &lt;class T&gt; void mergesort(T *input, int left, int right, T *scratch); template &lt;class T&gt; T less(T x, T y); template &lt;class T&gt; void mergesort(Array&lt;T&gt; &amp;input, int left, int right, Array&lt;T&gt;&amp;scratch); template &lt;class T&gt; void mergesort(Array&lt;T&gt; &amp; input); Array&lt;int&gt; &amp; random(int n); template &lt;class T&gt; void selectionSort(T a[], int n) { int i, j, tmp; int min_idx = 0; for (size_t i = 0; i &lt; n-1; i++) { min_idx = i; for (size_t j = i+1; j &lt; n; j++) { if (a[j] &lt; a[min_idx]) { min_idx = j; } tmp = a[i]; a[i] = a[min_idx]; a[min_idx] = tmp; } } } template &lt;class T&gt; void selectionSort(Array&lt;T&gt; &amp;a) { int tmp; int min_idx = 0; for (int i = 0; i &lt; a.getSize() - 1; i++) { min_idx = i; for (int j = i + 1; j &lt; a.getSize(); j++) { if (a[j] &lt; a[min_idx]) { min_idx = j; } tmp = a[i]; a[i] = a[min_idx]; a[min_idx] = tmp; } } } template &lt;class T&gt; void insertionSort(Array&lt;T&gt; &amp;a) { // put your code here } template &lt;class T&gt; bool sorted(Array&lt;T&gt; a) { for (int i = 1; i &lt; a.getSize(); i++) if (a[i - 1] &gt; a[i]) return false; return true; } Array&lt;int&gt; &amp; random(int n) { Array&lt;int&gt; *tmp = new Array&lt;int&gt;(n); for (int i = 0; i &lt; n; i++) (*tmp)[i] = rand() % 1000; return *tmp; } template &lt;class T&gt; T less(T x, T y) { if (x &lt; y) { return x; } else { return y; } } template &lt;class T&gt; void mergesort(T *input, int left, int right, T *scratch) { if (right == left + 1) { return; } else { int i = 0; int length = right - left; int midpoint_distance = length / 2; int l = left, r = left + midpoint_distance; mergesort(input, left, left + midpoint_distance, scratch); mergesort(input, left + midpoint_distance, right, scratch); /* merge the arrays together using scratch for temporary storage */ for (i = 0; i &lt; length; i++) { /* Check to see if any elements remain in the left array; if so, * we check if there are any elements left in the right array; if * so, we compare them. Otherwise, we know that the merge must * use take the element from the left array */ if (l &lt; left + midpoint_distance &amp;&amp; (r == right || min(input[l], input[r]) == input[l])) { scratch[i] = input[l]; l++; } else { scratch[i] = input[r]; r++; } } /* Copy the sorted subarray back to the input */ for (i = left; i &lt; right; i++) { input[i] = scratch[i - left]; } } } template &lt;class T&gt; void mergesort(T *input, int size) { int *scratch = new int[size]; mergesort(input, 0, size, scratch); delete [] scratch; } template &lt;class T&gt; void mergesort(Array&lt;T&gt; &amp;input, int left, int right, Array&lt;T&gt;&amp;scratch) { if (right == left + 1) { return; } else { int i = 0; int length = right - left; int midpoint_distance = length / 2; int l = left, r = left + midpoint_distance; mergesort(input, left, left + midpoint_distance, scratch); mergesort(input, left + midpoint_distance, right, scratch); /* merge the arrays together using scratch for temporary storage */ for (i = 0; i &lt; length; i++) { /* Check to see if any elements remain in the left array; if so, * we check if there are any elements left in the right array; if * so, we compare them. Otherwise, we know that the merge must * use take the element from the left array */ if (l &lt; left + midpoint_distance &amp;&amp; (r == right || min(input[l], input[r]) == input[l])) { scratch[i] = input[l]; l++; } else { scratch[i] = input[r]; r++; } } /* Copy the sorted subarray back to the input */ for (i = left; i &lt; right; i++) { input[i] = scratch[i - left]; } } } template &lt;class T&gt; void mergesort(Array&lt;T&gt; &amp;input) { // put your code here } #endif </code></pre> <p>I also noticed that there is a <code>void insertionSort(Array&lt;T&gt; &amp;a);</code> function, but the algorithm I was given is:</p> <pre><code>void insertionSort(int a[], int n){ int tmp; int i, j; for (i = 1; i &lt; n; i++) { tmp = a[i]; for (j = i - 1; j &gt;= 0; j--) if (a[j] &gt; tmp) a[j + 1] = a[j]; else break; a[j + 1] = tmp; } } </code></pre> <p>Am I supposed to implement this the same way, just replacing <code>int a[]</code> with, say... <code>&amp;arr</code>? I'm guessing since this includes <code>array.h</code> and the array class has <code>T * arr;</code>, I should be pointing to the address of that array? Would this also work for each definition that has the address operator in its parameter?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

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