1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#include "LinkedList.h"
/** Merges two sorted array segments theArray[first..mid] and
* theArray[mid+1..last] into one sorted array.
* @pre first <= mid <= last. The subarrays theArray[first..mid]
* and theArray[mid+1..last] are each sorted in increasing order.
* @post theArray[first..last] is sorted.
* @param theArray The given array.
* @param first The beginning of the first segment in theArray.
* @param mid The end of the first segement in theArray. mid + 1
* marks the beginning of the second segment.
* @param last The last element in the second segment in theArray.
* @note This function merges the two subarrays into a temporary
* array and copies the result into the original array theArray. */
void Merge(LinkedList theArray,
int first, int mid, int last)
{
//DataType tempArray[MAX_SIZE]; // temporary array
LinkedList tempArray;
// initialize the local indexes to indicate the subarrays
int first1 = first; // beginning of first subarray
int last1 = mid; // end of first subarray
int first2 = mid + 1; // beginning of second subarray
int last2 = last; // end of second subarray
cout<<"first1,l1,f2,l2: "<<first1<<" "<<last1<<" "<<first2<<" "<<last2<<" "<<endl;
// while both subarrays are not empty, copy the
// smaller item into the temporary array
int index = first1; // next available location in
// tempArray
for (; (first1 <= last1) && (first2 <= last2); ++index)
{ // Invariant: tempArray[first..index-1] is in order
// if ((theArray.getNodeAt(first1)).item < (theArray.getNodeAt(first2)).item)
if ((theArray.getItemAt(first1)) < (theArray.getItemAt(first2)) )
{ //tempArray[index] = theArray[first1];
tempArray.insertItemAt(index, theArray.getItemAt(first1));
++first1;
}
else
{ // tempArray[index] = theArray[first2];
tempArray.insertItemAt(index, theArray.getItemAt(first2));
++first2;
} // end if
} // end for
// finish off the nonempty subarray
// finish off the first subarray, if necessary
for (; first1 <= last1; ++first1, ++index){
// Invariant: tempArray[first..index-1] is in order
// tempArray[index] = theArray[first1];
tempArray.insertItemAt(index, theArray.getItemAt(first1));
}
// finish off the second subarray, if necessary
for (; first2 <= last2; ++first2, ++index){
// Invariant: tempArray[first..index-1] is in order
//tempArray[index] = theArray[first2];
tempArray.insertItemAt(index, theArray.getItemAt(first2));
}
// copy the result back into the original array
for (index = first; index <= last; ++index)
// theArray[index] = tempArray[index];
theArray.insertItemAt(index, tempArray.getItemAt(index));
} // end merge
/** Sorts the items in an array into ascending order.
* @pre theArray[first..last] is an array.
* @post theArray[first..last] is sorted in ascending order.
* @param theArray The given array.
* @param first The first element to consider in theArray.
* @param last The last element to consider in theArray. */
void MergeSort(LinkedList theArray, int first, int last)
{ cout<<"first: "<<first<<endl;
cout<<"last: "<<last<<endl;
cout<<"I am MErgeSort"<<endl;
if (first < last)
{ // sort each half
cout<<"entered first<last"<<endl;
int mid = (first + last)/2; // index of midpoint
cout<<"mid: "<<mid<<endl;
// sort left half theArray[first..mid]
MergeSort(theArray, first, mid);
//segmentfault here I think
cout<<"2nd mergeSort:"<<endl;
cout<<"mid+1: "<<mid+1<<endl;
cout<<"last: "<<last<<endl;
// sort right half theArray[mid+1..last]
MergeSort(theArray, mid+1, last);
// merge the two halves
Merge(theArray, first, mid, last);
} // end if
cout<<"end of MErgeSort"<<endl;
} // end mergesort
| |
