Thu Nov 21 23:28:33 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-09 FROM Ruben Safir SUBJECT Re: [Learn] merge sort parallel hw From learn-bounces-at-nylxs.com Wed Nov 9 21:14:47 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 D5D67161312; Wed, 9 Nov 2016 21:14:46 -0500 (EST) X-Original-To: learn-at-nylxs.com Delivered-To: learn-at-nylxs.com Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62]) by mrbrklyn.com (Postfix) with ESMTP id 49E71160E77 for ; Wed, 9 Nov 2016 21:14:44 -0500 (EST) To: learn-at-nylxs.com References: <6714100a-3ebd-8129-b8bc-6d1db3ae59be-at-mrbrklyn.com> <877f8ccf4h.fsf-at-contrapunctus.net> From: Ruben Safir Message-ID: <9c3e75e5-b83a-229b-867c-dcc364df895d-at-mrbrklyn.com> Date: Wed, 9 Nov 2016 21:14:44 -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: <877f8ccf4h.fsf-at-contrapunctus.net> 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 08:12 PM, Christopher League wrote: > = > Maybe you shouldn't have renamed the variables. That introduced a bug. no doubt > 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[pos= 2]) =3D=3D in[pos1])) I was zeroing in on just that segment. I just didn't see where there was a different through the stack of the two expressions. > { > space[i] =3D in[pos1]; > pos1++; > ~~~~ > = > Indeed, at the starting point, `pos2 =3D=3D left+mpt` and `pos3 =3D=3D ri= ght`, > but `pos2` and `pos3` *change* throughout the merge loop. = Yes, but they changed, or so I thought, only when left changes, which is only when the function starts off, and with each new iteration is a new function call with the new values for the paramters. Only that middle spot seems to be sensitive, and I'm not certain of the logic of that line either. I started to map the data flow. I should have kicked up gdb > What you're > comparing them to is supposed to stay fixed. left is fixed. I don't think mpt is. > = > With that change, it works. > = > (Unclear to me why `pos1` and `pos2` are more "sensible" names than `l`, > `r` but okay...) > = l is ALWAY a disaster but we had r and right and, and it isn't even what you really want. What you want is like a cursor, that marches and marks the left, the right and the middle. > 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. I was considering rewriting it completely. I need to add pthreads to it. It was due at 6PM tonight. An array slice is an interesting thought. I was going to make each node a separate class object. Now I understand I just don't understand this algorithm as well as I thought. 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 << "________________________________________________________" << e= ndl; >> >> 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 1= 74 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 o= ne >> * 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 storage= */ = >> for(i =3D 0; i < length; i++) >> { >> /* Check to see if any elements remain in the left array; if= so, >> * we check if there are any elements left in the right arra= y; if >> * so, we compare them. Otherwise, we know that the merge m= ust >> * use take the element from the left array */ >> if(l < left + midpoint_distance && = >> (r =3D=3D right || max(input[l], input[r]) =3D=3D in= put[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 > = -- = 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!