Geek Answers Handbook

Improving Mergesort. Improvement 3). Use one smaller copy between input and temporary arrays

I am currently working on a project for my class of algorithms, and I am a bit stalled. We were instructed to make improvements to sort the mergers that were in the book, by making certain changes. I did a great job with the first two changes, but the 3rd part is a killer.

Combining the sort that we are improving, copies the contents of the input array to a temporary array and then copies the temporary array back to the input array. Therefore, it recursively sorts the input array by placing two sorted halves in a temporary array. And then it concatenates the two halves in the temporary array together, placing the sorted sequence in the input array as it goes through.

The improvement is that this duplication can wastefully be done without. His hint is this: we can make every merge call copy in only one direction, but Merge calls alternate direction.

This is supposedly done by blurring the lines between the source and the temporary array.

I'm really not looking for code, as I'm sure I can code it. I just have no idea what I should do. The professor left for the day, so I can’t ask him until next week, when I will have my course again.

Has anyone done something like this before? Or you can decrypt and put it in the conditions for me: P

The first improvement, it just uses it when pasting, whenever the array gets small enough, and it will be very useful, because of this.

(2 , ) 1 n, , . , . :

//#include "InsertionSort.h"
#define INSERTION_CUTOFF 250
#include <limits.h>  // needed for INT_MAX (the sentinel)
void merge3(int* inputArray, int p, int q, int r, int* tempArray)
{
  int i,j,k;
  for (i = p; i <= r; i++)
  {
    tempArray[i] = inputArray[i];
  }
  i = p;
  j = q+1;
  k = p;
  while (i <= q && j <= r)
  {
    if (tempArray[i] <= tempArray[j])
    {
      inputArray[k++] = tempArray[i++];
    }
    else
    {
      inputArray[k++] = tempArray[j++];
    }
  }
}//merge3()

void mergeSort3Helper(int* inputArray, int p, int r, int* tempArray)
{
  if (r - p < INSERTION_CUTOFF)
  {
    insertionSort(inputArray,p,r);
    return;
  }
  int q = (p+r-1)/2;
  mergeSort3Helper(inputArray,p,q,tempArray);
  mergeSort3Helper(inputArray,q+1,r,tempArray);
  merge3(inputArray,p,q,r,tempArray);
}//mergeSort3Helper()

void mergeSort3(int* inputArray, int p, int r)
{
  if (r-p < 1)
  {
    return;
  }
  if (r - p < INSERTION_CUTOFF)
  {
    insertionSort(inputArray,p,r);
    return;
  }
  int* tempArray = malloc((r-p)+1*sizeof(int));
  tempArray[r+1] = INT_MAX;
  mergeSort3Helper(inputArray,p,r,tempArray);
//  This version of merge sort should allocate all the extra space
//  needed for merging just once, at the very beginning, instead of
//  within each call to merge3().
}//mergeSort3()
+5
2

:
A1: 7 0 2 9 5 1 4 3
A2: ()

1:
A1:
A2: 0 7 2 9 1 5 3 4

2:
A1: 0 2 7 9 1 3 4 5
A2:

3:
A1:
A2: 0 1 2 3 4 5 7 9

, mergesort. , , , .

+3

, , , . , .

merge3(inputArray, p,q,r, tempArray) , ; tempArray . , merge4(inputArray, p,q,r, outputArray), , .

mergeSort3Helper(), . , mergeSort4Helper(inputArray, p,q,r, outputArray), . ( ) mergeSort4(), , , . .

mergeSort4Helper(), , . , .

. ; , , .

0

More articles:


All Articles