Thu Nov 21 23:34:10 2024 EVENTS FREE SOFTWARE INSTITUTE POLITICS JOBS MEMBERS' CORNER MAILING LIST NYLXS Members have a lot to say and share but we don't keep many secrets. Join the Hangout Mailing List and say your peice. DATE 2016-11-01 LEARN 2024-11-21 | 2024-10-21 | 2024-09-21 | 2024-08-21 | 2024-07-21 | 2024-06-21 | 2024-05-21 | 2024-04-21 | 2024-03-21 | 2024-02-21 | 2024-01-21 | 2023-12-21 | 2023-11-21 | 2023-10-21 | 2023-09-21 | 2023-08-21 | 2023-07-21 | 2023-06-21 | 2023-05-21 | 2023-04-21 | 2023-03-21 | 2023-02-21 | 2023-01-21 | 2022-12-21 | 2022-11-21 | 2022-10-21 | 2022-09-21 | 2022-08-21 | 2022-07-21 | 2022-06-21 | 2022-05-21 | 2022-04-21 | 2022-03-21 | 2022-02-21 | 2022-01-21 | 2021-12-21 | 2021-11-21 | 2021-10-21 | 2021-09-21 | 2021-08-21 | 2021-07-21 | 2021-06-21 | 2021-05-21 | 2021-04-21 | 2021-03-21 | 2021-02-21 | 2021-01-21 | 2020-12-21 | 2020-11-21 | 2020-10-21 | 2020-09-21 | 2020-08-21 | 2020-07-21 | 2020-06-21 | 2020-05-21 | 2020-04-21 | 2020-03-21 | 2020-02-21 | 2020-01-21 | 2019-12-21 | 2019-11-21 | 2019-10-21 | 2019-09-21 | 2019-08-21 | 2019-07-21 | 2019-06-21 | 2019-05-21 | 2019-04-21 | 2019-03-21 | 2019-02-21 | 2019-01-21 | 2018-12-21 | 2018-11-21 | 2018-10-21 | 2018-09-21 | 2018-08-21 | 2018-07-21 | 2018-06-21 | 2018-05-21 | 2018-04-21 | 2018-03-21 | 2018-02-21 | 2018-01-21 | 2017-12-21 | 2017-11-21 | 2017-10-21 | 2017-09-21 | 2017-08-21 | 2017-07-21 | 2017-06-21 | 2017-05-21 | 2017-04-21 | 2017-03-21 | 2017-02-21 | 2017-01-21 | 2016-12-21 | 2016-11-21 | 2016-10-21 | 2016-09-21 | 2016-08-21 | 2016-07-21 | 2016-06-21 | 2016-05-21 | 2016-04-21 | 2016-03-21 | 2016-02-21 | 2016-01-21 | 2015-12-21 | 2015-11-21 | 2015-10-21 | 2015-09-21 | 2015-08-21 | 2015-07-21 | 2015-06-21 | 2015-05-21 | 2015-04-21 | 2015-03-21 | 2015-02-21 | 2015-01-21 | 2014-12-21 | 2014-11-21 | 2014-10-21 Key: Value: Key: Value: 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 2016-11-01 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] how is it indexing in cuda 2016-11-01 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] not adequately speced of explained 2016-11-01 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] how is it indexing in cuda 2016-11-01 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] not adequately speced of explained 2016-11-02 Christopher League <league-at-contrapunctus.net> Re: [Learn] Fitch Algorithm - C++ 2016-11-02 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fitch Algorithm - C++ 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] how is it indexing in cuda 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fitch Algorithm - C++ 2016-11-02 IEEE Computer Society <csconnection-at-computer.org> Subject: [Learn] Hear Google's John Martinis Take on Quantum Computing at 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] opencl 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] scheduled for tommorw 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] threads tutorial 2016-11-03 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fitch Algorithm - C++ 2016-11-03 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fitch Algorithm - C++ 2016-11-03 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fitch Algorithm - C++ 2016-11-03 Christopher League <league-at-contrapunctus.net> Re: [Learn] huffman code 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] huffman code 2016-11-03 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] huffman code 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fitch algorithm from the beginning 2016-11-03 From: <mrbrklyn-at-panix.com> Subject: [Learn] huffman code 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Phenology meeting 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] relevant hackathon 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] relevant hackathon 2016-11-04 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] huffman code 2016-11-04 Christopher League <league-at-contrapunctus.net> Subject: [Learn] Fitch/Sankoff 2016-11-05 Christopher League <league-at-contrapunctus.net> Re: [Learn] Fwd: templates within templates 2016-11-05 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Re: const T vs T const 2016-11-05 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Template Library files and Header linking troubles 2016-11-05 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: templates within templates 2016-11-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fwd: templates within templates 2016-11-06 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Fwd: templates within templates 2016-11-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fwd: templates within templates 2016-11-06 Christopher League <league-at-contrapunctus.net> Re: [Learn] Fwd: templates within templates 2016-11-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fwd: templates within templates 2016-11-06 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Fwd: templates within templates 2016-11-06 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Fwd: templates within templates 2016-11-06 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] GNU Parallel 20161022 ('Matthew') released [stable] 2016-11-07 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] templates and ostream for future reference 2016-11-08 Christopher League <league-at-contrapunctus.net> Re: [Learn] C++ signature ambiguity 2016-11-08 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] C++ signature ambiguity 2016-11-08 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] C++ signature ambiguity 2016-11-08 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Invitation: Phylogeny meeting -at- Weekly from 10:15 to 2016-11-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] Fwd: [nylug-talk] RSVP open: Wed Nov 16, 2016-11-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort parallel hw 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] merge sort parallel hw 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] merge sort parallel hw 2016-11-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort parallel hw 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] mergesort tutorial 2016-11-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] mergesort tutorial 2016-11-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] namespace and external files confusion 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] namespace and external files confusion 2016-11-09 From: "Carlos R. Mafra" <crmafra-at-gmail.com> Re: [Learn] Question about a small change 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] =?utf-8?q?C++_call_of_overloaded_=E2=80=98track=28int*=26?= 2016-11-09 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: lost arguments 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Dating origins of dinosaurs, 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] merge sort parallel hw 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] mergesort tutorial 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] namespace and external files confusion 2016-11-10 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort parallel hw 2016-11-10 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] merge sort parallel hw 2016-11-10 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] merge sort parallel hw 2016-11-10 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] merge sort parallel hw 2016-11-10 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] [Hangout-NYLXS] mergesort tutorial 2016-11-10 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] Fwd: [Hangout-NYLXS] ease your mind- everything in the 2016-11-10 Ruben Safir <ruben.safir-at-my.liu.edu> Subject: [Learn] Fwd: [Hangout-NYLXS] R Programming Workshop 2016-11-10 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Paleocast phenogenetic tree building 2016-11-11 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort parallel hw 2016-11-12 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] HW of mergesort in parallel 2016-11-13 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] merge sort in parallel assignment 2016-11-14 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort in parallel assignment 2016-11-14 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] merge sort in parallel assignment 2016-11-14 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] merge sort parallel hw 2016-11-14 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] CUDA and video 2016-11-14 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] PNG Graphic formats and CRCs 2016-11-15 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: PNG coding 2016-11-15 ruben safir <ruben.safir-at-my.liu.edu> Subject: [Learn] Fwd: PNG Coding 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Fwd: lost arguments 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] relevant hackathon 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] C++ Workshop Announcement 2016-11-16 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] Fwd: Re: ref use 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] ref use 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] why use a reference wrapper int his example 2016-11-17 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] [Hangout-NYLXS] at K&R now 2016-11-17 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [Hangout-NYLXS] Fwd: PNG Coding 2016-11-18 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] C++ workshop and usenet responses 2016-11-19 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: ref use 2016-11-20 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] when is the constructor called for an object 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: creating a binary tree 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: hidden static 2016-11-21 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: ISBI 2017 Call for Abstracts and Non-Author 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: PNG coding 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Re: the new {} syntax 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: when is the constructor called for an object 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: when is the constructor called for an object 2016-11-21 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Eoconfuciusornis feather keratin and 2016-11-21 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] look what I found 2016-11-22 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Cuccuency book 2016-11-22 ruben safir <ruben.safir-at-my.liu.edu> Subject: [Learn] declare a func or call an object 2016-11-22 Ruben Safir <ruben.safir-at-my.liu.edu> Subject: [Learn] Fwd: Re: Using CLIPS as a library 2016-11-23 Ruben Safir <ruben.safir-at-my.liu.edu> Subject: [Learn] Fwd: Simple C++11 Wrapper for CLIPS 6.30 2016-11-23 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Parrelel Programming HW2 with maxpath 2016-11-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] great research news for big data 2016-11-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] mapping algorithms 2016-11-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Todays meeting 2016-11-25 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Flightless theropod phylogenetic variation 2016-11-26 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Note to self for Thursday 2016-11-26 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fitch etc 2016-11-26 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Note to self for Thursday 2016-11-26 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] operator<<() overloading details and friend 2016-11-27 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] 130 year old feathers analysis 2016-11-27 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: ACM/SPEC ICPE 2017 - Call for Tutorial Proposals 2016-11-27 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: ACM/SPEC ICPE 2017 - Call for Workshop Proposals 2016-11-27 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: CfP 22nd Conf. Reliable Software Technologies, 2016-11-27 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Seeking contributors for psyche-c 2016-11-29 Christopher League <league-at-contrapunctus.net> Re: [Learn] Look at this exciting output by my test program 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Look at this exciting output by my test program 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Look at this exciting output by my test program 2016-11-29 Christopher League <league-at-contrapunctus.net> Re: [Learn] Quantum Entanglement 2016-11-29 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Quantum Entanglement 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Here is the paper I was talking out 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Look at this exciting output by my test program 2016-11-29 nylxs <mrbrklyn-at-optonline.net> Subject: [Learn] Look at this exciting output by my test program 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Quantum Entanglement 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] The Death of PBS 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] witmer lab ohio and 3d imaging 2016-11-30 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] phylogenetic crawler NYLXS are Do'ers and the first step of Doing is Joining! Join NYLXS and make a difference in your community today!