Difference: CodeRecursion (1 vs. 2)

Revision 22017-12-05 - JimSkon

Line: 1 to 1
 
META TOPICPARENT name="WebHome"

Recursion

Merge sort

Line: 6 to 5
  %CODE{"c++"}% #include
Added:
>
>
#include
 using namespace std;
Changed:
<
<
//The merge function void merge(int a[], int startIndex, int endIndex) {

int size = (endIndex - startIndex) + 1; int *b = new int [size]();

int i = startIndex; int mid = (startIndex + endIndex)/2; int k = 0; int j = mid + 1;

while (k < size) { if((i<=mid) && (a[i] < a[j])) { b[k++] = a[i++]; } else { b[k++] = a[j++]; }

>
>
void display(vector a); void merge(vector &a, int s, int e); void merge_sort(vector &iArray, int s, int e);
 
Added:
>
>
//The main function int main() { vector iArray = {2, 5, 6, 4, 7, 2, 8, 3, 9, 10}; merge_sort(iArray, 0, iArray.size() - 1); //Print the sorted array display(iArray); return 0;
 }
Changed:
<
<
for(k=0; k < size; k++) { a[startIndex+k] = b[k];
>
>
// Display a vector of ints void display(vector a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " ";
 }
Changed:
<
<
delete []b;
>
>
cout << endl;
 }
Deleted:
<
<
//The recursive merge sort function void merge_sort(int iArray[], int startIndex, int endIndex) { int midIndex;

//Check for base case if (startIndex >= endIndex) { return; }

//First, divide in half midIndex = (startIndex + endIndex)/2;

//First recursive call merge_sort(iArray, startIndex, midIndex);

//Second recursive call merge_sort(iArray, midIndex+1, endIndex);

 //The merge function
Changed:
<
<
merge(iArray, startIndex, endIndex);
>
>
void merge(vector &a, int s, int e) {
  }
Changed:
<
<
//The main function int main(int argc, char *argv[]) { int iArray[10] = {2,5,6,4,7,2,8,3,9,10};

merge_sort(iArray, 0, 9);

>
>
//The recursive merge sort function void merge_sort(vector &iArray, int s, int e) {
 
Deleted:
<
<
//Print the sorted array for(int i=0; i < 10; i++) { cout << iArray[i] << endl;
 }
Deleted:
<
<
return 0; }
  %ENDCODE% \ No newline at end of file

Revision 12015-12-08 - JimSkon

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="WebHome"

Recursion

Merge sort

<-- SyntaxHighlightingPlugin -->
#include <iostream>
using namespace std;

//The merge function
void merge(int a[], int startIndex, int endIndex)
{

int size = (endIndex - startIndex) + 1;
int *b = new int [size]();

int i = startIndex;
int mid = (startIndex + endIndex)/2;
int k = 0;
int j = mid + 1;

while (k < size)
{   
    if((i<=mid) && (a[i] < a[j]))
    {
        b[k++] = a[i++];
    }
    else
    {
        b[k++] = a[j++];
    }

}

for(k=0; k < size; k++)
{
    a[startIndex+k] = b[k];
}

delete []b;

}

//The recursive merge sort function
void merge_sort(int iArray[], int startIndex, int endIndex)
{
int midIndex;

//Check for base case
if (startIndex >= endIndex)
{
    return;
}   

//First, divide in half
midIndex = (startIndex + endIndex)/2;

//First recursive call 
merge_sort(iArray, startIndex, midIndex);

//Second recursive call 
merge_sort(iArray, midIndex+1, endIndex);

//The merge function
merge(iArray, startIndex, endIndex);

}

//The main function
int main(int argc, char *argv[])
{
int iArray[10] = {2,5,6,4,7,2,8,3,9,10};

merge_sort(iArray, 0, 9);

//Print the sorted array
for(int i=0; i < 10; i++)
{
    cout << iArray[i] << endl;
}

return 0;    
}
<-- end SyntaxHighlightingPlugin -->
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback