MESSAGE
| DATE | 2016-11-10 |
| FROM | Ruben Safir
|
| SUBJECT | Re: [Learn] merge sort parallel hw
|
From learn-bounces-at-nylxs.com Thu Nov 10 08:12:00 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id 04142161312;
Thu, 10 Nov 2016 08:12:00 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id 3DA78160E77
for ; Thu, 10 Nov 2016 08:11:56 -0500 (EST)
Received: from [10.0.0.62] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id C77C3133E1
for ; Thu, 10 Nov 2016 08:11:56 -0500 (EST)
To: learn-at-nylxs.com
References: <6714100a-3ebd-8129-b8bc-6d1db3ae59be-at-mrbrklyn.com>
<877f8ccf4h.fsf-at-contrapunctus.net>
<4cc3c62e-0920-4ebd-ad7d-7ebee6432f22.maildroid-at-localhost>
From: Ruben Safir
Message-ID: <7c24c78a-f82b-3e6c-9c16-3d62ae034bf3-at-panix.com>
Date: Thu, 10 Nov 2016 08:11:56 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
MIME-Version: 1.0
In-Reply-To: <4cc3c62e-0920-4ebd-ad7d-7ebee6432f22.maildroid-at-localhost>
Subject: Re: [Learn] merge sort parallel hw
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: quoted-printable
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
On 11/09/2016 09:34 PM, Christopher League wrote:
> Hm, okay. Will it help if I bring insulated bag and cold packs? =
I can but return them to me. They are more expensive than people thing
> =
> CL
> =
> -----Original Message-----
> From: Ruben Safir
> To: learn-at-nylxs.com
> Sent: Wed, 09 Nov 2016 21:19
> Subject: Re: [Learn] merge sort parallel hw
> =
> I have fish for you tomorrow
> =
> =
> On 11/09/2016 08:12 PM, Christopher League wrote:
>>
>> Maybe you shouldn't have renamed the variables. That introduced a bug.
>> Here's the diff:
>>
>> ~~~~ {.diff}
>> -at--at- -34,7 +34,7 -at--at- void track(int* in, int left, int right, int* space)
>> track(in, pos2, pos3, space);
>> for(i =3D 0; i < length; i++)
>> {
>> - if(pos1 < pos2 && ( pos2 =3D=3D pos3 || max(in[pos1], in[pos2]) =
=3D=3D in[pos1]))
>> + if(pos1 < left+mpt && ( pos2 =3D=3D right || max(in[pos1], in[po=
s2]) =3D=3D in[pos1]))
>> {
>> space[i] =3D in[pos1];
>> pos1++;
>> ~~~~
>>
>> Indeed, at the starting point, `pos2 =3D=3D left+mpt` and `pos3 =3D=3D r=
ight`,
>> but `pos2` and `pos3` *change* throughout the merge loop. What you're
>> comparing them to is supposed to stay fixed.
>>
>> With that change, it works.
>>
>> (Unclear to me why `pos1` and `pos2` are more "sensible" names than `l`,
>> `r` but okay...)
>>
>> I can make further suggestions about logging and about a much better
>> data structure that actually takes advantage of C++. Instead of managing
>> all this left/right/mid stuff manually, write a small `array_slice`
>> class that defines the `operator[]` to look up in a given array using an
>> offset. Then you can write a 0-based merge much more cleanly.
>>
>> CL
>>
>> Ruben Safir writes:
>>
>>> I can't finish by tonight. I borrowed a mergesort algorithm from the
>>> net at here
>>>
>>> http://www.cprogramming.com/tutorial/computersciencetheory/merge.html
>>>
>>> I ported it to C++ and it failed to work. I changed the name of the
>>> vars to more sensible names, and converged some of his math because what
>>> was there just seemed to sloppy. I mocked it and merged the last
>>> subroutine directly in main and it just failed to work. So I then
>>> copied and pasted his work and altered it to make it a complete c
>>> program and it does work :(
>>>
>>> I can't find what I did wrong. I might have just been better off
>>> writing it by myself but I wanted to finish before class tonight, and to
>>> focus on the thread library.
>>>
>>> Its 4PM and I'm out of time. Attached at the cpp files and the c files
>>>
>>> They are all part of the C++ code accept for the one with the c sufix.
>>> That one is the copy and paste version. This will take another day at
>>> least.
>>>
>>> Reuvain
>>>
>>>
>>> -- =
>>> So many immigrant groups have swept through our town
>>> that Brooklyn, like Atlantis, reaches mythological
>>> proportions in the mind of the world - RI Safir 1998
>>> http://www.mrbrklyn.com
>>>
>>> DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
>>> http://www.nylxs.com - Leadership Development in Free Software
>>> http://www2.mrbrklyn.com/resources - Unpublished Archive
>>> http://www.coinhangout.com - coins!
>>> http://www.brooklyn-living.com
>>>
>>> Being so tracked is for FARM ANIMALS and and extermination camps,
>>> but incompatible with living as a free human being. -RI Safir 2013
>>> /*
>>> * =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>>> *
>>> * Filename: main.cpp
>>> *
>>> * Description: merge sort main
>>> *
>>> * Version: 1.0
>>> * Created: 11/09/2016 09:33:20 AM
>>> * Revision: none
>>> * Compiler: gcc
>>> *
>>> * Author: Dr. Fritz Mehner (mn), mehner-at-fh-swf.de
>>> * Company: FH S=FCdwestfalen, Iserlohn
>>> *
>>> * =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>>> */
>>> #include
>>> #include "msort.h"
>>> #include
>>> #include
>>>
>>> #define SIZE 20
>>>
>>> int main(int argv, char **argc)
>>> {
>>> using namespace std;
>>>
>>> int *data =3D new int[SIZE];
>>> int *cache =3D new int[SIZE];
>>> struct timespec now;
>>> clock_gettime(CLOCK_REALTIME, &now);
>>> long seed =3D now.tv_nsec;
>>> srand( (unsigned int) seed);
>>> for(int i =3D 0; i < SIZE; i++){
>>> data[i] =3D rand() % 1000;
>>> cout << data[i] << "\t";
>>> }
>>> cout << endl;
>>>
>>> cout << "________________________________________________________" << =
endl;
>>>
>>> for(int i =3D 0; i < SIZE; i++){
>>> cout << "Before: " << i << " =3D=3D> " << data[i] << "\t" << endl;
>>> }
>>> merge::track(data, 0, SIZE, cache);
>>> for(int i =3D 0; i < SIZE; i++){
>>> cout << "After: " << i << "=3D=3D> " << data[i] << "\t" << endl;
>>> }
>>>
>>> return 0;
>>>
>>> }
>>>
>>> CXX:=3Dg++ =
>>> CXXFLAGS:=3D-Wall -ggdb =
>>>
>>> LDFLAGS:=3D-L/usr/local/lib/mysql -lmysqlpp -lmysqlclient
>>>
>>> msort : msort.o main.o
>>> ${CXX} ${CXXFLAGS} -o msort msort.o main.o
>>>
>>> main.o : main.cpp
>>> ${CXX} ${CXXFLAGS} -o main.o -c main.cpp =
>>>
>>> msort.o : msort.cpp msort.h
>>> ${CXX} ${CXXFLAGS} -c msort.cpp
>>>
>>> clean : =
>>> rm nodes *.o make.deps
>>> touch *.cpp *.h
>>>
>>> include make.deps
>>> make.deps: *.cpp ; gcc -M *.cpp >$-at-
>>> #include "msort.h"
>>> #include
>>>
>>> namespace merge{
>>>
>>> int max(int x, int y){
>>> int ret;
>>> x>y ? ret=3Dx : ret=3Dy;
>>> std::cout << x << ":" << y << "=3D=3D>" << ret << std::endl;
>>> return ret;
>>> }
>>>
>>> void track(int* in, int left, int right, int* space)
>>> {
>>> int i =3D 0;
>>> =
>>> if(right =3D=3D left + 1){
>>> std::cout << "BACKUP" << std::endl;
>>> return;
>>> }
>>> =
>>> int length =3D right - left;
>>> std::cout << "length =3D>" << length << std::endl;
>>> int mpt =3D length/2;
>>> std::cout << "mpt =3D>" << mpt << std::endl;
>>> int pos1 =3D left;
>>> int pos2 =3D left + mpt;
>>> int pos3 =3D right;
>>> std::cout << "pos1 =3D>" << pos1 << " pos2=3D=3D>" << pos2 << " pos3=
=3D=3D>" << pos3 << std::endl;
>>> //do the recursion now on the left and right branches
>>> std::cout << "LEFT <<=3D=3D" << std::endl;
>>> track(in, pos1, pos2, space);
>>> std::cout << "RIGHT =3D=3D>>" << std::endl;
>>> track(in, pos2, pos3, space);
>>> for(i =3D 0; i < length; i++)
>>> {
>>> if(pos1 < pos2 && ( pos2 =3D=3D pos3 || max(in[pos1], in[pos2]) =3D=
=3D in[pos1]))
>>> {
>>> space[i] =3D in[pos1];
>>> pos1++;
>>> }
>>> else{
>>> space[i] =3D in[pos2];
>>> pos2++;
>>> }
>>> }
>>> /* transfer array segment */
>>> for(i =3D left; i < right; i++)
>>> {
>>> in[i] =3D space[i - left];
>>> }
>>> }
>>>
>>> }//end namespace
>>> /*
>>> * =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>>> *
>>> * Filename: msort.h
>>> *
>>> * Description: Header File for Parrell Msort algorthm
>>> *
>>> * Version: 1.0
>>> * Created: 11/09/2016 04:28:51 AM
>>> * Revision: none
>>> * Compiler: gcc
>>> *
>>> * Author: Ruben Safir
>>> * Company: NYLXS Inc
>>> *
>>> * =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>>> */
>>> #ifndef MSORT_INC
>>> #define MSORT_INC
>>>
>>> namespace merge{
>>>
>>>
>>> int max(int x, int y);
>>> void track(int* , int , int , int* );
>>> //int sort(int &input , int size); =
>>>
>>> }
>>> #endif /* ----- #ifndef MSORT_INC ----- */
>>>
>>> 119 480 914 629 352 111 923 92 636 152 286 104 244 432 617 669 367 309 =
174 474 =
>>> ________________________________________________________
>>> Before: 0 =3D=3D> 119 =
>>> Before: 1 =3D=3D> 480 =
>>> Before: 2 =3D=3D> 914 =
>>> Before: 3 =3D=3D> 629 =
>>> Before: 4 =3D=3D> 352 =
>>> Before: 5 =3D=3D> 111 =
>>> Before: 6 =3D=3D> 923 =
>>> Before: 7 =3D=3D> 92 =
>>> Before: 8 =3D=3D> 636 =
>>> Before: 9 =3D=3D> 152 =
>>> Before: 10 =3D=3D> 286 =
>>> Before: 11 =3D=3D> 104 =
>>> Before: 12 =3D=3D> 244 =
>>> Before: 13 =3D=3D> 432 =
>>> Before: 14 =3D=3D> 617 =
>>> Before: 15 =3D=3D> 669 =
>>> Before: 16 =3D=3D> 367 =
>>> Before: 17 =3D=3D> 309 =
>>> Before: 18 =3D=3D> 174 =
>>> Before: 19 =3D=3D> 474 =
>>> length =3D>20
>>> mpt =3D>10
>>> pos1 =3D>0 pos2=3D=3D>10 pos3=3D=3D>20
>>> LEFT <<=3D=3D
>>> length =3D>10
>>> mpt =3D>5
>>> pos1 =3D>0 pos2=3D=3D>5 pos3=3D=3D>10
>>> LEFT <<=3D=3D
>>> length =3D>5
>>> mpt =3D>2
>>> pos1 =3D>0 pos2=3D=3D>2 pos3=3D=3D>5
>>> LEFT <<=3D=3D
>>> length =3D>2
>>> mpt =3D>1
>>> pos1 =3D>0 pos2=3D=3D>1 pos3=3D=3D>2
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> BACKUP
>>> 119:480=3D=3D>480
>>> RIGHT =3D=3D>>
>>> length =3D>3
>>> mpt =3D>1
>>> pos1 =3D>2 pos2=3D=3D>3 pos3=3D=3D>5
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> length =3D>2
>>> mpt =3D>1
>>> pos1 =3D>3 pos2=3D=3D>4 pos3=3D=3D>5
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> BACKUP
>>> 629:352=3D=3D>629
>>> 914:629=3D=3D>914
>>> 629:352=3D=3D>629
>>> 480:914=3D=3D>914
>>> 480:629=3D=3D>629
>>> 480:629=3D=3D>629
>>> RIGHT =3D=3D>>
>>> length =3D>5
>>> mpt =3D>2
>>> pos1 =3D>5 pos2=3D=3D>7 pos3=3D=3D>10
>>> LEFT <<=3D=3D
>>> length =3D>2
>>> mpt =3D>1
>>> pos1 =3D>5 pos2=3D=3D>6 pos3=3D=3D>7
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> BACKUP
>>> 111:923=3D=3D>923
>>> RIGHT =3D=3D>>
>>> length =3D>3
>>> mpt =3D>1
>>> pos1 =3D>7 pos2=3D=3D>8 pos3=3D=3D>10
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> length =3D>2
>>> mpt =3D>1
>>> pos1 =3D>8 pos2=3D=3D>9 pos3=3D=3D>10
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> BACKUP
>>> 636:152=3D=3D>636
>>> 92:636=3D=3D>636
>>> 92:152=3D=3D>152
>>> 923:636=3D=3D>923
>>> 111:636=3D=3D>636
>>> 111:152=3D=3D>152
>>> 111:92=3D=3D>111
>>> 636:92=3D=3D>636
>>> 914:923=3D=3D>923
>>> 914:636=3D=3D>914
>>> 629:636=3D=3D>636
>>> 629:152=3D=3D>629
>>> 629:152=3D=3D>629
>>> 480:152=3D=3D>480
>>> 119:152=3D=3D>152
>>> 119:111=3D=3D>119
>>> 923:111=3D=3D>923
>>> 636:111=3D=3D>636
>>> RIGHT =3D=3D>>
>>> length =3D>10
>>> mpt =3D>5
>>> pos1 =3D>10 pos2=3D=3D>15 pos3=3D=3D>20
>>> LEFT <<=3D=3D
>>> length =3D>5
>>> mpt =3D>2
>>> pos1 =3D>10 pos2=3D=3D>12 pos3=3D=3D>15
>>> LEFT <<=3D=3D
>>> length =3D>2
>>> mpt =3D>1
>>> pos1 =3D>10 pos2=3D=3D>11 pos3=3D=3D>12
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> BACKUP
>>> 286:104=3D=3D>286
>>> RIGHT =3D=3D>>
>>> length =3D>3
>>> mpt =3D>1
>>> pos1 =3D>12 pos2=3D=3D>13 pos3=3D=3D>15
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> length =3D>2
>>> mpt =3D>1
>>> pos1 =3D>13 pos2=3D=3D>14 pos3=3D=3D>15
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> BACKUP
>>> 432:617=3D=3D>617
>>> 244:617=3D=3D>617
>>> 244:432=3D=3D>432
>>> 286:617=3D=3D>617
>>> 286:432=3D=3D>432
>>> 286:244=3D=3D>286
>>> 104:244=3D=3D>244
>>> RIGHT =3D=3D>>
>>> length =3D>5
>>> mpt =3D>2
>>> pos1 =3D>15 pos2=3D=3D>17 pos3=3D=3D>20
>>> LEFT <<=3D=3D
>>> length =3D>2
>>> mpt =3D>1
>>> pos1 =3D>15 pos2=3D=3D>16 pos3=3D=3D>17
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> BACKUP
>>> 669:367=3D=3D>669
>>> RIGHT =3D=3D>>
>>> length =3D>3
>>> mpt =3D>1
>>> pos1 =3D>17 pos2=3D=3D>18 pos3=3D=3D>20
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> length =3D>2
>>> mpt =3D>1
>>> pos1 =3D>18 pos2=3D=3D>19 pos3=3D=3D>20
>>> LEFT <<=3D=3D
>>> BACKUP
>>> RIGHT =3D=3D>>
>>> BACKUP
>>> 174:474=3D=3D>474
>>> 309:474=3D=3D>474
>>> 309:174=3D=3D>309
>>> 474:174=3D=3D>474
>>> 669:474=3D=3D>669
>>> 367:474=3D=3D>474
>>> 367:309=3D=3D>367
>>> 474:309=3D=3D>474
>>> 617:669=3D=3D>669
>>> 617:474=3D=3D>617
>>> 432:474=3D=3D>474
>>> 432:367=3D=3D>432
>>> 286:367=3D=3D>367
>>> 286:474=3D=3D>474
>>> 286:309=3D=3D>309
>>> 923:669=3D=3D>923
>>> 914:669=3D=3D>914
>>> 636:669=3D=3D>669
>>> 636:617=3D=3D>636
>>> 629:617=3D=3D>629
>>> 629:617=3D=3D>629
>>> 480:617=3D=3D>617
>>> 480:474=3D=3D>480
>>> 152:474=3D=3D>474
>>> 152:432=3D=3D>432
>>> 152:367=3D=3D>367
>>> 152:474=3D=3D>474
>>> 152:309=3D=3D>309
>>> 152:286=3D=3D>286
>>> 152:244=3D=3D>244
>>> 152:104=3D=3D>152
>>> 119:104=3D=3D>119
>>> 923:104=3D=3D>923
>>> 636:104=3D=3D>636
>>> 669:104=3D=3D>669
>>> After: 0=3D=3D> 923 =
>>> After: 1=3D=3D> 914 =
>>> After: 2=3D=3D> 669 =
>>> After: 3=3D=3D> 636 =
>>> After: 4=3D=3D> 629 =
>>> After: 5=3D=3D> 629 =
>>> After: 6=3D=3D> 617 =
>>> After: 7=3D=3D> 480 =
>>> After: 8=3D=3D> 474 =
>>> After: 9=3D=3D> 432 =
>>> After: 10=3D=3D> 367 =
>>> After: 11=3D=3D> 474 =
>>> After: 12=3D=3D> 309 =
>>> After: 13=3D=3D> 286 =
>>> After: 14=3D=3D> 244 =
>>> After: 15=3D=3D> 152 =
>>> After: 16=3D=3D> 119 =
>>> After: 17=3D=3D> 923 =
>>> After: 18=3D=3D> 636 =
>>> After: 19=3D=3D> 669 =
>>> #include "stdlib.h"
>>> #include "time.h"
>>> #include "stdio.h"
>>>
>>> #define SIZE 500
>>>
>>> /* Helper function for finding the max of two numbers */
>>> int max(int x, int y)
>>> {
>>> if(x > y)
>>> {
>>> return x;
>>> }
>>> else
>>> {
>>> return y;
>>> }
>>> }
>>>
>>> /* left is the index of the leftmost element of the subarray; right is =
one
>>> * past the index of the rightmost element */
>>> void merge_helper(int *input, int left, int right, int *scratch)
>>> {
>>> /* base case: one element */
>>> if(right =3D=3D left + 1)
>>> {
>>> return;
>>> }
>>> else
>>> {
>>> int i =3D 0;
>>> int length =3D right - left;
>>> int midpoint_distance =3D length/2;
>>> /* l and r are to the positions in the left and right subarrays=
*/
>>> int l =3D left, r =3D left + midpoint_distance;
>>>
>>> /* sort each subarray */
>>> merge_helper(input, left, left + midpoint_distance, scratch);
>>> merge_helper(input, left + midpoint_distance, right, scratch);
>>>
>>> /* merge the arrays together using scratch for temporary storag=
e */ =
>>> for(i =3D 0; i < length; i++)
>>> {
>>> /* Check to see if any elements remain in the left array; i=
f so,
>>> * we check if there are any elements left in the right arr=
ay; if
>>> * so, we compare them. Otherwise, we know that the merge =
must
>>> * use take the element from the left array */
>>> if(l < left + midpoint_distance && =
>>> (r =3D=3D right || max(input[l], input[r]) =3D=3D i=
nput[l]))
>>> {
>>> scratch[i] =3D input[l];
>>> l++;
>>> }
>>> else
>>> {
>>> scratch[i] =3D input[r];
>>> r++;
>>> }
>>> }
>>> /* Copy the sorted subarray back to the input */
>>> for(i =3D left; i < right; i++)
>>> {
>>> input[i] =3D scratch[i - left];
>>> }
>>> }
>>> }
>>>
>>> /* mergesort returns true on success. Note that in C++, you could also
>>> * replace malloc with new and if memory allocation fails, an exception=
will
>>> * be thrown. If we don't allocate a scratch array here, what happens? =
>>> *
>>> * Elements are sorted in reverse order -- greatest to least */
>>>
>>> int mergesort(int *input, int size)
>>> {
>>> int *scratch =3D (int *)malloc(size * sizeof(int));
>>> if(scratch !=3D NULL)
>>> {
>>> merge_helper(input, 0, size, scratch);
>>> free(scratch);
>>> return 1;
>>> }
>>> else
>>> {
>>> return 0;
>>> }
>>> }
>>>
>>> int main(int argc, char** argv)
>>> {
>>> int *data =3D (int *)malloc(SIZE * sizeof(int ));
>>> struct timespec now;
>>> clock_gettime(CLOCK_REALTIME, &now);
>>> long seed =3D now.tv_nsec;
>>> srand( (unsigned int) seed);
>>> for(int i =3D 0; i < SIZE; i++){
>>> data[i] =3D rand() % 1000;
>>> printf("%i \t", data[i] );
>>> }
>>> printf("\n");
>>>
>>> printf ("________________________________________________________\n"); =
>>> mergesort(data, SIZE);
>>> for(int i =3D 0; i < SIZE; i++){
>>> printf("%i \t", data[i] );
>>> }
>>> printf("\n");
>>> return 0;
>>> }
>>>
>>>
>>> _______________________________________________
>>> Learn mailing list
>>> Learn-at-nylxs.com
>>> http://lists.mrbrklyn.com/mailman/listinfo/learn
>>
>>
>>
>> _______________________________________________
>> Learn mailing list
>> Learn-at-nylxs.com
>> http://lists.mrbrklyn.com/mailman/listinfo/learn
>>
> =
> =
> =
> =
> _______________________________________________
> Learn mailing list
> Learn-at-nylxs.com
> http://lists.mrbrklyn.com/mailman/listinfo/learn
> =
-- =
So many immigrant groups have swept through our town
that Brooklyn, like Atlantis, reaches mythological
proportions in the mind of the world - RI Safir 1998
http://www.mrbrklyn.com
DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
http://www.nylxs.com - Leadership Development in Free Software
http://www2.mrbrklyn.com/resources - Unpublished Archive
http://www.coinhangout.com - coins!
http://www.brooklyn-living.com
Being so tracked is for FARM ANIMALS and and extermination camps,
but incompatible with living as a free human being. -RI Safir 2013
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
|
|
