----------------------------------------------------------------------------- Chris Butler [email: chrisb@sandy.force9.co.uk] ----------------------------------------------------------------------------- Then what's hindering somebody to buy a cruise missile at a surplus sale and send it as Unsolited Cruise Missile to a foreign country? -- Wolfgang Schelongowski in news.admin.net-abuse.email --- FMail/386 1.22 * Origin: ... The Death Butler BBS, +44-1582-620141 ... (2:257/135) --------------- FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE Ref: F5G00347 Date: 04/19/98 From: CHRISTOPHER BUTLER Time: 01:17pm \/To: CAREY BLOODWORTH (Read 2 times) Subj: findfirst & findnext Hi Carey! Hey, Carey wasn't it you that was talking about findfirst & findnext on 16 Apr 98? Yeah... you were talking to All, weren't you? CB> I need some suggestions on changing DOS's findfirst & findnext to the CB> POSIX opendir/nextdir etc. CB> 2) just go ahead and use opendir/readdir and then call a port specific CB> wrapper function to examine the entry and decide whether it's a file CB> or directory. You can use the stat() call to get information about a file, including finding out whether it is a symbolic link, regular file, directory, char/block device, fifo or a networking socket. The stat call conforms to POSIX as well... ----------------------------------------------------------------------------- Chris Butler [email: chrisb@sandy.force9.co.uk] ----------------------------------------------------------------------------- "You've got an evil streak .. I like that." -- Adam Colley, Voice to Debbie Whitley, 9th November, 1997. --- FMail/386 1.22 * Origin: ... The Death Butler BBS, +44-1582-620141 ... (2:257/135) --------------- FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE Ref: F5G00348 Date: 04/19/98 From: GEORGE WHITE Time: 11:42am \/To: ANDREW FRANK (Read 2 times) Subj: Re: Best sort algorithm Hi Andrew, You wrote to Herman Schonfeld: AF> I'm not entirely sure of your objectives with this test, AF>if memory constraints are insignificant, some of these AF>comments are useless. AF> Assorted comments and declarations have been removed. AF> HS> char data[1000][4]; AF> HS> char save[1000][4]; AF> HS> void QKSORT() AF> HS> { AF> HS> /* Implementation of QUICKSORT algorithm */ AF> HS> char temp[20]; AF> HS> static int sl[1000][2]; AF> I'd say that this is somewhat overstated. In a worst case AF>(memory wise) the list will continually be split into AF>groups of 2, the pivot, and the rest. With a group of 1 or AF>0, the pivot, and the rest, the first group is sorted and AF>can be forgot. Thus, the amount of temporary storage peaks AF>1/3 the total list size in the worst case, so 334 would be AF>enough. It's way overstated. If he followed the well known technique of putting the larger partition on the stack and sorting the smaller one he would only need (for this case) a stack of "int sl[10][2]" (or, with his wasteful technique of increasing the stack pointer _before_ putting the data on the "stack" so that sl[0][x] is never used, "int sl[11][2]"). George * SLMR 2.1a * Wastebasket: Something to throw things near. --- Maximus/2 3.01 * Origin: DoNoR/2,Woking UK (44-1483-717905) (2:440/4) --------------- FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE Ref: F5G00349 Date: 04/19/98 From: GEORGE WHITE Time: 11:49am \/To: JASEN BETTS (Read 2 times) Subj: Best INSERTION SORT Hi Jasen, You wrote to David Noon: JB>DN> JB>Also your insertion sort could use a bisection search to find the JB>DN> JB>insertion place and memmove to do the move of multiple items to ake JB>DN> JB>room to insert, this would speed it up considerably (I'm expecting JB>DN> JB>2-3 times) JB>DN> Bisection searching? JB>DN> JB>DN> This usually presupposes sorted data. Please post some code to show us JB>DN> how you do it. JB>When you are insertion sorting, you pick the next item off the unsorted nd JB>the array and insert it into the sorted end. (I probably JB>could stop right here) :-) JB>The sorted end is by nature sorted :), so it can be bisection searched to fi JB>the insertion position. It is a helpful technique when data is added to the end of an already sorted data set, especially if the early exit technique at "note above" is used to rapidly skip already sorted data. If there is only a relatively small amount of extra data it is, in my testing, the quickest sort. On random data, unless you are maintaining a sort order on another key, there are better routines (as you've already found and reported) although it does help speed things up on larger data sets, on small data sets (which is all insertion sort is usually suitable for) the time overhead of implemeting the bi-section search is more than the time it saves. JB>some code: (which still needs a little tidying up) :-). JB>void newINSERTION() JB> { JB> int top; JB> int a,b,c; JB> char temp[20]; JB> for(top=0; top < lastone; top++) JB> { JB> strcpy(temp,data[top + 1]); JB> /* Bisection search */ JB> a=0,b=top+1; JB> while(a!=b) JB> if( strcmp(data[c=(b+a)/2],temp) <0) JB> a=c+1; else b=c; JB> /* Insert */ JB> memmove(data+a+1,data+a,(1+top-a)*sizeof(data[0])); JB> strcpy(data[b],temp); JB> } JB> } Some code to keep David happy (it's based on his to save typing anyway ). Ascending sort with memmove & bisection search #define TYPE short void ascending (TYPE array[], int n) { int i,left,right,split; TYPE Hold_it_here; for (i = 1; i < n; ++i) { if (array[i] < array[i-1]) /* Note above */ { Hold_it_here = array[i]; left = 0; right = i; while (left != right) { if (Hold_it_here > array[(split = (right + left)/2)]) left = split + 1; else right = split; } if (left != i) { memmove (&array[left + 1],&array[left],(i-left) * sizeof (array[0]) array[left] = Hold_it_here; } } } return; } Timings... I've done a lot of testing and can't find any suitable timings to present. All I can deduce from my testing is that it is generally slower than the standard sorts given the same test data and customisation, but in the specific case I referred to above of a small amount of new data added to the end of an already sorted data set it can be the fastest sort. I could draw no generalisations as to data set size or amount of extra data where it had an advantage, although the smaller the amount of new data the larger the data set size where it was fastest, so for those following the thread its a case of test it yourself for your specific requirements... George * SLMR 2.1a * Wastebasket: Something to throw things near. --- Maximus/2 3.01 * Origin: DoNoR/2,Woking UK (44-1483-717905) (2:440/4) --------------- FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE Ref: F5G00350 Date: 04/19/98 From: GEORGE WHITE Time: 11:40am \/To: CAREY BLOODWORTH (Read 2 times) Subj: Bubble And Squeak Sortin Hi Carey, CB>GW>CB>comparisons and exchanges aren't really the whole story. (I should als CB>GW>CB>point out that with most real 'bubble sorts', there will only be 'n' CB>GW>CB>exchanges. Most implementations will find the highest/lowest and then CB>GW>I'm glad you said 'bubble sort', because as soon as you change to the CB>GW>method you describe it is no longer a "bubble sort" but a "selection CB>GW>sort", and indeed selection sorts are generally quicker than Bubble CB>Not really. A few minor percent. Same lousy N^2 growth rate. All you CB>are really doing is changing the 'O' very slightly, not the growth. Oh yes, really! :-) It does depend on the time "cost" of comparisons and exchanges but, in general, comparisons are quick while exchanges are slow, and while a selection sort has at most N exchanges, a bubble sort is average 1/4 (N^2 - N) and max 1/2 (N^2 - N). A Selection sort always performs 1/2 (N^2 - N) comparisons, while this is the upper bound on a bubble sort with early exit if there are no exchanges is a pass. The early exit testing itself adds time though, so there is no simple answer :-(. Given that comparisons are quick compared to exchanges, a selection sort will generally be faster than a bubble sort. CB>Frankly, that change is so minor, I personally don't consider it to be a CB>new algorithm, just a minor refinement to an old one. (That's why I put CB>it in tiny little quotes.) I don't think changes that minor are worth CB>giving it a new name. That's like saying that parsnips and carrots are the same because they are both root vegetables with a similar shape grown from seed. While both sorts share the same basic loop structure, the operation is totally different. CB>The change I was meaning isn't what I normally consider an insertion CB>sort. (Something such as the one in snippets.) Agreed. It is in no way related to insertion sorts. CB>I just meant: CB>for (loop1=0;loop1 {highest=loop1; CB> for (loop2=loop1+1;loop2 if (data[loop2] > data[highest]) highest=loop2; CB> if (loop1!=highest) swapdata(loop1,highest); CB> } CB>Personally, I still consider it to be a bubble sort, it just reduces the CB>number of exchanges to only 'size'. But it is now a totally different family of sorts, a selection sort. Even though the loop structure is the same... CB>GW>CB>On small data sets (both quantity and size), the loop overhead (setup, CB>GW>CB>iter, end, etc.) can have a significant impact. Also, the quality f CB>GW>CB>the code, the size of the items to compare/swap, the time it takes CB>GW>Seconded... (or thirded if David gets here first!) CB>I remember one time, back in the late 80s, I guess, on an 8 bit micro, I CB>was sorting about 30 moves generated in a chess program, and it was CB>actually faster for me to use a simple bubble sort than use the CB>quick-sort library routine. I guess the library routine was just very CB>poorly written or something, but in that case, it was actually faster to CB>do a simpler, hardwired bubble sort. Just goes to show that for CB>atypical situations, you just have to try it and see. Down at that number of elements, a dedicated sort should always beat the generalised qsort() provided by the compiler, but that does not mean that a simple bubble sort, or a selection sort such as you post above, will be faster than a customised shell sort (which is an insertion sort) or quickersort (which is an exchange sort). George * SLMR 2.1a * Wastebasket: Something to throw things near. --- Maximus/2 3.01 * Origin: DoNoR/2,Woking UK (44-1483-717905) (2:440/4) --------------- FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE Ref: F5G00351 Date: 04/19/98 From: DAVID NOON Time: 06:44pm \/To: CAREY BLOODWORTH (Read 2 times) Subj: Bubble And Squeak Sortin In a message dated 04-16-98, Carey Bloodworth said to David Noon about Bubble And Squeak Sorting Hi Carey, DN>Actually, it's a selection sort. That's a whole other algorithm. CB>Personally, I don't really care what it's called. Well, it helps to keep us clear on the strategies involved if each has a separate name. CB>To me, it's such a minor change to Bubble sort that I don't see any CB>point in giving it a different name. It still has the same lousy CB>growth, just a few percent faster. Actually, selection sort has a useful place in the world when the cost of an exchange is substantially greater than the cost of a comparison. A typical example is an array whose elements are instances of large struct that has a small sort key, e.g. an int, so that 3 large memcpy() (or moral equivalent) operations are needed for an exchange, but the comparisons are done using registers. CB>I'm not an expert on sorting, since I rarely encounter any situation CB>where either a simple bubble sort or the standard library qsort isn't CB>'good enough'. Even if the method I mentioned is really called CB>something else, I'll still probably call it a bubble sort because it's CB>still a N^2 sort and they look so much alike. Not all O(n**2) algorithms are bubble sorts. More is the pity. Too many other sort algorithms are also O(n**2). The give away that it is a selection sort is that one comparand is always anchored next to an extremity of the already sorted elements and then the extremum is searched for among the unsorted elements. After the extremum is found (i.e. selected) it is exchanged with the anchor point, the anchor point is incremented/decremented and the loop repeats. OTOH, a bubble sort always compares _adjacent_ elements. This is why the outer loop can be controlled by an "early exit" flag instead of a counter. [An example of this latter strategy was H****n's FBUBBLE() routine.] In practice, this "fast bubble" sort is slower than the normal one, as was shown in H****n's benchmarks. For this reason, selection sort often performs rather fewer exchanges than bubble sort, even though they typically perform about the same number of comparisons. Regards Dave ___ * MR/2 2.25 #353 * What does Windows NT stands for? Nervous Technicians? --- Maximus/2 3.01 * Origin: DoNoR/2,Woking UK (44-1483-717905) (2:440/4) --------------- FIDO MESSAGE AREA==> TOPIC: 239 C LANGUAGE Ref: F5G00352 Date: 04/20/98 From: ELIJAH HUYNH Time: 02:49pm \/To: BRUCE WEDDING (Read 2 times) Subj: Nested loop BW> int main() BW> { BW> int i, j; BW> char *str = "ABCDE"; BW> BW> for ( i = 0; i < strlen(str); i++) BW> { BW> for (j = 0; j < i; j++) BW> putchar(str[j]); BW> puts(""); BW> } BW> return 0; You forgot that I'm a beginner. The exercise asked for nested loop using for loop. --- Maximus 3.01 * Origin: BitByters BBS, Rockland ON, Can. (613)446-7773 v34, (1:163/215)