2018-02-07
Feb 7 In-Class Exercise Thread.
Post Your Solutions to the Feb 7 In-class exercise to this thread.
Best,
Chris
Post Your Solutions to the Feb 7 In-class exercise to this thread.
Best,
Chris
mergesort(arr[],n,r){
middle m = (1+r)/2;
spawn mergesort(arr,1,m);
mergesort(arr, m+1,r);
sync;
merge(arr, 1,m,r);
}
(Edited: 2018-02-07) <pre>
mergesort(arr[],n,r){
middle m = (1+r)/2;
spawn mergesort(arr,1,m);
mergesort(arr, m+1,r);
sync;
merge(arr, 1,m,r);
}
</pre>
if p < r then
q = (p + r)/2 spawn Merge-Sort(A, p, q) Merge-Sort(A, q + 1, r) sync Merge(A, p, q, r)end if
if p < r then
q = (p + r)/2
spawn Merge-Sort(A, p, q)
Merge-Sort(A, q + 1, r)
sync
Merge(A, p, q, r)
end if
// Array A[] has the items to sort; array B[] is a work array.
TopDownMergeSort(A[], B[], n)
{
CopyArray(A, 0, n, B); // duplicate array A[] into B[]
TopDownSplitMerge(B, 0, n, A); // sort data from B[] into A[]
}
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
if(iEnd - iBegin < 2) // if run size == 1
return; // consider it sorted
// split the run longer than 1 item into halves
iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
// recursively sort both runs from array A[] into B[]
spawn <===========================================================
TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
sync <============================================================
// merge the resulting runs from array B[] into A[]
TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}
// Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1 ].
// Result is B[ iBegin:iEnd-1 ].
TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
i = iBegin, j = iMiddle;
// While there are elements in the left or right runs...
for (k = iBegin; k < iEnd; k++) {
// If left run head exists and is <= existing right run head.
if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
B[k] = A[i];
i = i + 1;
} else {
B[k] = A[j];
j = j + 1;
}
}
}
CopyArray(A[], iBegin, iEnd, B[])
{
(Edited: 2018-02-07)
for(k = iBegin; k < iEnd; k++)
B[k] = A[k];
}
// Array A[] has the items to sort; array B[] is a work array.
TopDownMergeSort(A[], B[], n)
{
CopyArray(A, 0, n, B); // duplicate array A[] into B[]
TopDownSplitMerge(B, 0, n, A); // sort data from B[] into A[]
}
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
if(iEnd - iBegin < 2) // if run size == 1
return; // consider it sorted
// split the run longer than 1 item into halves
iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
// recursively sort both runs from array A[] into B[]
spawn <===========================================================
TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
sync <============================================================
// merge the resulting runs from array B[] into A[]
TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}
// Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1 ].
// Result is B[ iBegin:iEnd-1 ].
TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
i = iBegin, j = iMiddle;
// While there are elements in the left or right runs...
for (k = iBegin; k < iEnd; k++) {
// If left run head exists and is <= existing right run head.
if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
B[k] = A[i];
i = i + 1;
} else {
B[k] = A[j];
j = j + 1;
}
}
}
CopyArray(A[], iBegin, iEnd, B[])
{
for(k = iBegin; k < iEnd; k++)
B[k] = A[k];
}
mergesort(arr[],n,r)
{
int mid = (1+r)/2;
spawn mergesort(arr,1,mid);
mergesort(arr, mid+1,r);
sync;
merge(arr, 1,mid,r);
}
(Edited: 2018-02-07) <pre>
mergesort(arr[],n,r)
{
int mid = (1+r)/2;
spawn mergesort(arr,1,mid);
mergesort(arr, mid+1,r);
sync;
merge(arr, 1,mid,r);
}
</pre>
array : 1 to n
left = 1
right = n
merge_sort(left, right)
{
while(left < right)
{
mid = (left + right)/2
spawn merge_sort(left,mid)
merge_sort(mid + 1, right)
sync
merge(left,right)
}
(Edited: 2018-02-07) array : 1 to n
left = 1
right = n
merge_sort(left, right)
{
while(left < right)
{
mid = (left + right)/2
'''spawn''' merge_sort(left,mid)
merge_sort(mid + 1, right)
'''sync'''
merge(left,right)
}
mergeSort()
return divide(arr,0,arr.length)
divide(arr, first, last)
mid = (first+last)/2 arrLeft = spawn divide(arr, first, mid) arrRight = divide(arr, mid+1, last) sync return merge(arrLeft, arrRight)merge(arrLeft, arrRight) mergedList = []
while i<len(arrLeft) and j<len(arrRight) if arrLeft[i] < arrRight[i] mergedList[i]=arrLeft[i++] else mergedList[j]=arrRight[j++] while i<len(arrLeft) mergedList[i]=arrLeft[i++] while j<len(arrRight) mergedList[j]=arrRight[j++]
return mergedList
mergeSort()
return divide(arr,0,arr.length)
divide(arr, first, last)
mid = (first+last)/2
arrLeft = spawn divide(arr, first, mid)
arrRight = divide(arr, mid+1, last)
sync
return merge(arrLeft, arrRight)
merge(arrLeft, arrRight)
mergedList = []
while i<len(arrLeft) and j<len(arrRight)
if arrLeft[i] < arrRight[i]
mergedList[i]=arrLeft[i++]
else
mergedList[j]=arrRight[j++]
while i<len(arrLeft)
mergedList[i]=arrLeft[i++]
while j<len(arrRight)
mergedList[j]=arrRight[j++]
return mergedList
Merge_Sort(A,p,r) if p<r q = floor((p+r)/2) Merge_Sort(A,p,q) Merge_Sort(A,q+1,r) Merge(A,p,q,r)
Using Multithreading
Merge_Sort(A,p,r)
(Edited: 2018-02-07) if p<r q = floor((p+r)/2) Spawn Merge_Sort(A,p,q) Merge_Sort(A,q+1,r) Sync Merge(A,p,q,r)
<pre>
Merge_Sort(A,p,r)
if p<r
q = floor((p+r)/2)
Merge_Sort(A,p,q)
Merge_Sort(A,q+1,r)
Merge(A,p,q,r)
</pre>
Using Multithreading
Merge_Sort(A,p,r)
<pre>if p<r
q = floor((p+r)/2)
Spawn Merge_Sort(A,p,q)
Merge_Sort(A,q+1,r)
Sync
Merge(A,p,q,r)
</pre>
void merge(list& l1, list& l2, list& l){
while(l1.size>0 && l2.size>0){
if(l1.next_val()>l2.next_val()){
l.addnoden(l2.head);
l2.removehead();
}
else if(l1.next_val()<l2.next_val()){
l.addnoden(l1.head);
l1.removehead();
}
}
while(l1.size>0){
l.addnoden(l1.head);
l1.removehead();
}
while(l2.size>0){
l.addnoden(l2.head);
l2.removehead();
}
}
void sort(list& l){
if(l.size<2) return;
list l1;
list l2;
l.split(l1,l2);
spawn split(l1);
split(l2);
sync ;
l.clear();
merge(l1,l2,l);
}
void merge(list& l1, list& l2, list& l){
while(l1.size>0 && l2.size>0){
if(l1.next_val()>l2.next_val()){
l.addnoden(l2.head);
l2.removehead();
}
else if(l1.next_val()<l2.next_val()){
l.addnoden(l1.head);
l1.removehead();
}
}
while(l1.size>0){
l.addnoden(l1.head);
l1.removehead();
}
while(l2.size>0){
l.addnoden(l2.head);
l2.removehead();
}
}
void sort(list& l){
if(l.size<2) return;
list l1;
list l2;
l.split(l1,l2);
'''spawn''' split(l1);
split(l2);
'''sync''';
l.clear();
merge(l1,l2,l);
}
Merge Sort Pseudocode:
mergeSort(arr[],l,r)
m=(l+r)/2
spawn mergeSort(arr,l,m)
mergeSort(arr,m+1,r)
sync
merge(arr,l,m,r)
i, j, k;
n1 = m - l + 1;
n2 = r - m;
L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
while (i < n1 && j < n2)
if (L[i]
(Edited: 2018-02-07) '''Merge Sort Pseudocode:'''
<nowiki>mergeSort(arr[],l,r)
m=(l+r)/2
spawn mergeSort(arr,l,m)
mergeSort(arr,m+1,r)
sync
merge(arr,l,m,r)
i, j, k;
n1 = m - l + 1;
n2 = r - m;
L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
while (i < n1 && j < n2)
if (L[i] <= R[j])
arr[k] = L[i];
i++;
else
arr[k] = R[j];
j++;
k++;
while (i < n1)
arr[k] = L[i];
i++;
k++;
while (j < n2)
arr[k] = R[j];
j++;
k++;
</nowiki>
(c) 2025 Yioop - PHP Search Engine