Sat Dec 14 11:42:05 2024
EVENTS
 FREE
SOFTWARE
INSTITUTE

POLITICS
JOBS
MEMBERS'
CORNER

MAILING
LIST

NYLXS Mailing Lists and Archives
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-12-14 | 2024-11-14 | 2024-10-14 | 2024-09-14 | 2024-08-14 | 2024-07-14 | 2024-06-14 | 2024-05-14 | 2024-04-14 | 2024-03-14 | 2024-02-14 | 2024-01-14 | 2023-12-14 | 2023-11-14 | 2023-10-14 | 2023-09-14 | 2023-08-14 | 2023-07-14 | 2023-06-14 | 2023-05-14 | 2023-04-14 | 2023-03-14 | 2023-02-14 | 2023-01-14 | 2022-12-14 | 2022-11-14 | 2022-10-14 | 2022-09-14 | 2022-08-14 | 2022-07-14 | 2022-06-14 | 2022-05-14 | 2022-04-14 | 2022-03-14 | 2022-02-14 | 2022-01-14 | 2021-12-14 | 2021-11-14 | 2021-10-14 | 2021-09-14 | 2021-08-14 | 2021-07-14 | 2021-06-14 | 2021-05-14 | 2021-04-14 | 2021-03-14 | 2021-02-14 | 2021-01-14 | 2020-12-14 | 2020-11-14 | 2020-10-14 | 2020-09-14 | 2020-08-14 | 2020-07-14 | 2020-06-14 | 2020-05-14 | 2020-04-14 | 2020-03-14 | 2020-02-14 | 2020-01-14 | 2019-12-14 | 2019-11-14 | 2019-10-14 | 2019-09-14 | 2019-08-14 | 2019-07-14 | 2019-06-14 | 2019-05-14 | 2019-04-14 | 2019-03-14 | 2019-02-14 | 2019-01-14 | 2018-12-14 | 2018-11-14 | 2018-10-14 | 2018-09-14 | 2018-08-14 | 2018-07-14 | 2018-06-14 | 2018-05-14 | 2018-04-14 | 2018-03-14 | 2018-02-14 | 2018-01-14 | 2017-12-14 | 2017-11-14 | 2017-10-14 | 2017-09-14 | 2017-08-14 | 2017-07-14 | 2017-06-14 | 2017-05-14 | 2017-04-14 | 2017-03-14 | 2017-02-14 | 2017-01-14 | 2016-12-14 | 2016-11-14 | 2016-10-14 | 2016-09-14 | 2016-08-14 | 2016-07-14 | 2016-06-14 | 2016-05-14 | 2016-04-14 | 2016-03-14 | 2016-02-14 | 2016-01-14 | 2015-12-14 | 2015-11-14 | 2015-10-14 | 2015-09-14 | 2015-08-14 | 2015-07-14 | 2015-06-14 | 2015-05-14 | 2015-04-14 | 2015-03-14 | 2015-02-14 | 2015-01-14 | 2014-12-14 | 2014-11-14 | 2014-10-14

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

  1. 2016-11-01 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] how is it indexing in cuda
  2. 2016-11-01 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] not adequately speced of explained
  3. 2016-11-01 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] how is it indexing in cuda
  4. 2016-11-01 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] not adequately speced of explained
  5. 2016-11-02 Christopher League <league-at-contrapunctus.net> Re: [Learn] Fitch Algorithm - C++
  6. 2016-11-02 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fitch Algorithm - C++
  7. 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] how is it indexing in cuda
  8. 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fitch Algorithm - C++
  9. 2016-11-02 IEEE Computer Society <csconnection-at-computer.org> Subject: [Learn] Hear Google's John Martinis Take on Quantum Computing at
  10. 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] opencl
  11. 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] scheduled for tommorw
  12. 2016-11-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] threads tutorial
  13. 2016-11-03 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fitch Algorithm - C++
  14. 2016-11-03 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fitch Algorithm - C++
  15. 2016-11-03 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fitch Algorithm - C++
  16. 2016-11-03 Christopher League <league-at-contrapunctus.net> Re: [Learn] huffman code
  17. 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] huffman code
  18. 2016-11-03 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] huffman code
  19. 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fitch algorithm from the beginning
  20. 2016-11-03 From: <mrbrklyn-at-panix.com> Subject: [Learn] huffman code
  21. 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Phenology meeting
  22. 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] relevant hackathon
  23. 2016-11-03 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] relevant hackathon
  24. 2016-11-04 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] huffman code
  25. 2016-11-04 Christopher League <league-at-contrapunctus.net> Subject: [Learn] Fitch/Sankoff
  26. 2016-11-05 Christopher League <league-at-contrapunctus.net> Re: [Learn] Fwd: templates within templates
  27. 2016-11-05 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Re: const T vs T const
  28. 2016-11-05 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Template Library files and Header linking troubles
  29. 2016-11-05 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: templates within templates
  30. 2016-11-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fwd: templates within templates
  31. 2016-11-06 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Fwd: templates within templates
  32. 2016-11-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fwd: templates within templates
  33. 2016-11-06 Christopher League <league-at-contrapunctus.net> Re: [Learn] Fwd: templates within templates
  34. 2016-11-06 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Fwd: templates within templates
  35. 2016-11-06 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Fwd: templates within templates
  36. 2016-11-06 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Fwd: templates within templates
  37. 2016-11-06 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] GNU Parallel 20161022 ('Matthew') released [stable]
  38. 2016-11-07 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] templates and ostream for future reference
  39. 2016-11-08 Christopher League <league-at-contrapunctus.net> Re: [Learn] C++ signature ambiguity
  40. 2016-11-08 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] C++ signature ambiguity
  41. 2016-11-08 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] C++ signature ambiguity
  42. 2016-11-08 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Invitation: Phylogeny meeting -at- Weekly from 10:15 to
  43. 2016-11-08 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] Fwd: [nylug-talk] RSVP open: Wed Nov 16,
  44. 2016-11-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort parallel hw
  45. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] merge sort parallel hw
  46. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] merge sort parallel hw
  47. 2016-11-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort parallel hw
  48. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] mergesort tutorial
  49. 2016-11-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] mergesort tutorial
  50. 2016-11-09 Christopher League <league-at-contrapunctus.net> Re: [Learn] namespace and external files confusion
  51. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] namespace and external files confusion
  52. 2016-11-09 From: "Carlos R. Mafra" <crmafra-at-gmail.com> Re: [Learn] Question about a small change
  53. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] =?utf-8?q?C++_call_of_overloaded_=E2=80=98track=28int*=26?=
  54. 2016-11-09 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: lost arguments
  55. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Dating origins of dinosaurs,
  56. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] merge sort parallel hw
  57. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] mergesort tutorial
  58. 2016-11-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] namespace and external files confusion
  59. 2016-11-10 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort parallel hw
  60. 2016-11-10 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] merge sort parallel hw
  61. 2016-11-10 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] merge sort parallel hw
  62. 2016-11-10 Ruben Safir <ruben.safir-at-my.liu.edu> Re: [Learn] merge sort parallel hw
  63. 2016-11-10 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] [Hangout-NYLXS] mergesort tutorial
  64. 2016-11-10 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] Fwd: [Hangout-NYLXS] ease your mind- everything in the
  65. 2016-11-10 Ruben Safir <ruben.safir-at-my.liu.edu> Subject: [Learn] Fwd: [Hangout-NYLXS] R Programming Workshop
  66. 2016-11-10 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Paleocast phenogenetic tree building
  67. 2016-11-11 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort parallel hw
  68. 2016-11-12 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] HW of mergesort in parallel
  69. 2016-11-13 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] merge sort in parallel assignment
  70. 2016-11-14 Christopher League <league-at-contrapunctus.net> Re: [Learn] merge sort in parallel assignment
  71. 2016-11-14 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] merge sort in parallel assignment
  72. 2016-11-14 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] merge sort parallel hw
  73. 2016-11-14 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] CUDA and video
  74. 2016-11-14 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] PNG Graphic formats and CRCs
  75. 2016-11-15 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: PNG coding
  76. 2016-11-15 ruben safir <ruben.safir-at-my.liu.edu> Subject: [Learn] Fwd: PNG Coding
  77. 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Fwd: lost arguments
  78. 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] relevant hackathon
  79. 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] C++ Workshop Announcement
  80. 2016-11-16 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] Fwd: Re: ref use
  81. 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] ref use
  82. 2016-11-16 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] why use a reference wrapper int his example
  83. 2016-11-17 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] [Hangout-NYLXS] at K&R now
  84. 2016-11-17 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [Hangout-NYLXS] Fwd: PNG Coding
  85. 2016-11-18 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] C++ workshop and usenet responses
  86. 2016-11-19 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: ref use
  87. 2016-11-20 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] when is the constructor called for an object
  88. 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: creating a binary tree
  89. 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: hidden static
  90. 2016-11-21 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: ISBI 2017 Call for Abstracts and Non-Author
  91. 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: PNG coding
  92. 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Re: the new {} syntax
  93. 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: when is the constructor called for an object
  94. 2016-11-21 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: when is the constructor called for an object
  95. 2016-11-21 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Eoconfuciusornis feather keratin and
  96. 2016-11-21 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] look what I found
  97. 2016-11-22 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Cuccuency book
  98. 2016-11-22 ruben safir <ruben.safir-at-my.liu.edu> Subject: [Learn] declare a func or call an object
  99. 2016-11-22 Ruben Safir <ruben.safir-at-my.liu.edu> Subject: [Learn] Fwd: Re: Using CLIPS as a library
  100. 2016-11-23 Ruben Safir <ruben.safir-at-my.liu.edu> Subject: [Learn] Fwd: Simple C++11 Wrapper for CLIPS 6.30
  101. 2016-11-23 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Parrelel Programming HW2 with maxpath
  102. 2016-11-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] great research news for big data
  103. 2016-11-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] mapping algorithms
  104. 2016-11-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Todays meeting
  105. 2016-11-25 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Flightless theropod phylogenetic variation
  106. 2016-11-26 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Note to self for Thursday
  107. 2016-11-26 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fitch etc
  108. 2016-11-26 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Note to self for Thursday
  109. 2016-11-26 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] operator<<() overloading details and friend
  110. 2016-11-27 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] 130 year old feathers analysis
  111. 2016-11-27 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: ACM/SPEC ICPE 2017 - Call for Tutorial Proposals
  112. 2016-11-27 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: ACM/SPEC ICPE 2017 - Call for Workshop Proposals
  113. 2016-11-27 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: CfP 22nd Conf. Reliable Software Technologies,
  114. 2016-11-27 ruben safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: Seeking contributors for psyche-c
  115. 2016-11-29 Christopher League <league-at-contrapunctus.net> Re: [Learn] Look at this exciting output by my test program
  116. 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Look at this exciting output by my test program
  117. 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] Look at this exciting output by my test program
  118. 2016-11-29 Christopher League <league-at-contrapunctus.net> Re: [Learn] Quantum Entanglement
  119. 2016-11-29 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] Quantum Entanglement
  120. 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Here is the paper I was talking out
  121. 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Look at this exciting output by my test program
  122. 2016-11-29 nylxs <mrbrklyn-at-optonline.net> Subject: [Learn] Look at this exciting output by my test program
  123. 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Quantum Entanglement
  124. 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] The Death of PBS
  125. 2016-11-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] witmer lab ohio and 3d imaging
  126. 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!