All Sorts of Sorts 
Author Message
 All Sorts of Sorts

 Date: 02-17-90 (13:52)              Number: 2918 (Echo)
   To: IAN GREEN                     Refer#: 2881
 From: DON MADSON                      Read: NO
 Subj: LEARN TO SORT                 Status: PUBLIC MESSAGE

 Except for a list that's already sorted the selection sort
 performs better than the bubble sort.

 The bubble sort (with a flag) only performs well on an ordered
 list. If the list is already ordered why sort it?  When a new
 record is added insert it where it belongs and the list is still
 sorted. If a record is deleted close the gap.

 I suppose one option is to include every possible sort in your
 program and before sorting your database perform an analysis of
 that data to determine which sorting procedure to call. Or ...
 just include one that performs well most of the time.

 There is a good chapter on sorting in Wirth's book "Algorithms +
 Data Structures = Programs."
 ---
  ~ EZ-Reader 1.14 ~ ><><><><><><><><><><><><><><<>><><>
-----
This message came from GEnie via willett through a semi-automated process.



Fri, 07 Aug 1992 07:42:15 GMT  
 All Sorts of Sorts

 Date: 02-19-90 (10:10)              Number: 2933 (Echo)
   To: DON MADSON                    Refer#: 2918
 From: IAN GREEN                       Read: NO
 Subj: LEARN TO SORT                 Status: PUBLIC MESSAGE

    Well, in my application where I used the bubble sort, I decided to
 use that algorithm because of the data-structure I chose. It is simply
 an array of records. Now since it is an array (to be sure a simple data
 structure), insertion and deletion is trivial; to insert just add a
 record to the first 'blank' entry, to delete, change an entry to
 'blank'. Then after editing is completed the bubble sort quickly
 'cleans' up the array as the bulk of it is still ordered. The blank
 entry is designed to represent the highest possible key value so it
 naturally moves to the end of the list where it belongs. Simple and
 efficient.

 Ian Green

 NET/Mail : British Columbia Forth Board - Burnaby BC - (604)434-5886  
-----
This message came from GEnie via willett through a semi-automated process.



Sun, 09 Aug 1992 10:19:27 GMT  
 All Sorts of Sorts

 Date: 02-19-90 (22:24)              Number: 2934 (Echo)
   To: STEVE PALINCSAR               Refer#: NONE
 From: ZAFAR ESSAK                     Read: NO
 Subj: SELECTION SORT                Status: PUBLIC MESSAGE

 Thanks for the descriptions.

 I have also been looking at the SORT_OUT.ZIP that contains the program
 by Henning Hansen and Niels Jergen Christensen.  That is an awesome
 collection of sorts complete with an executable program that
 demonstrates a large number of sorts incluing a couple of their own.
 Unfortunately, for novices of the sort like me, there are no
 descriptive narratives of the different sorts.

 The list of sorts contained in that file are:

 \ Bubblesort

 \ Shakersort
 \ Shakersort with a flag
 \ Shakersort with interval reduction

 \ Shuttlesort - Sifting

 \ Straight Insertionsort
 \ Insertionsort, assymmetric search
 \ Insertionsort with bisection search

 \ Selectionsort
 \ Selectionsort, stable

 \ Stacksort (Selectionsort w. stack)
 \ Stacksort, stable

 \ Heapsort - Treesort

 \ Shellsort, dim. incr. insertion
 \ Shellsort with stack-seletion

 \ Splicesort
 \ Splicesort with insertion
 \ Splicesort with selection

 \ Batchersort

 \ Mergesort, binary subdivision
 \ Mergesort, natural

 \ Quicksort, first pivot element
 \ Quicksort, random pivot element
 \ Quicksort, middle pivot element
 \ Quicksort, median-of-three pivot
 \ Quicksort-partition + other sort

 It will be awhile before I have enough time to explore this variety of
 sorts.
 ---
  * Via Qwikmail 2.01

 NET/Mail : British Columbia Forth Board - Burnaby BC - (604)434-5886  
-----
This message came from GEnie via willett through a semi-automated process.



Sun, 09 Aug 1992 10:19:31 GMT  
 All Sorts of Sorts

 Date: 02-19-90 (10:10)              Number: 2933 (Echo)
   To: DON MADSON                    Refer#: 2918
 From: IAN GREEN                       Read: NO
 Subj: LEARN TO SORT                 Status: PUBLIC MESSAGE

    Well, in my application where I used the bubble sort, I decided to
 use that algorithm because of the data-structure I chose. It is simply
 an array of records. Now since it is an array (to be sure a simple data
 structure), insertion and deletion is trivial; to insert just add a
 record to the first 'blank' entry, to delete, change an entry to
 'blank'. Then after editing is completed the bubble sort quickly
 'cleans' up the array as the bulk of it is still ordered. The blank
 entry is designed to represent the highest possible key value so it
 naturally moves to the end of the list where it belongs. Simple and
 efficient.

 Ian Green

 NET/Mail : British Columbia Forth Board - Burnaby BC - (604)434-5886  
-----
This message came from GEnie via willett through a semi-automated process.



Mon, 10 Aug 1992 09:34:51 GMT  
 All Sorts of Sorts

 Date: 02-19-90 (22:24)              Number: 2934 (Echo)
   To: STEVE PALINCSAR               Refer#: NONE
 From: ZAFAR ESSAK                     Read: NO
 Subj: SELECTION SORT                Status: PUBLIC MESSAGE

 Thanks for the descriptions.

 I have also been looking at the SORT_OUT.ZIP that contains the program
 by Henning Hansen and Niels Jergen Christensen.  That is an awesome
 collection of sorts complete with an executable program that
 demonstrates a large number of sorts incluing a couple of their own.
 Unfortunately, for novices of the sort like me, there are no
 descriptive narratives of the different sorts.

 The list of sorts contained in that file are:

 \ Bubblesort

 \ Shakersort
 \ Shakersort with a flag
 \ Shakersort with interval reduction

 \ Shuttlesort - Sifting

 \ Straight Insertionsort
 \ Insertionsort, assymmetric search
 \ Insertionsort with bisection search

 \ Selectionsort
 \ Selectionsort, stable

 \ Stacksort (Selectionsort w. stack)
 \ Stacksort, stable

 \ Heapsort - Treesort

 \ Shellsort, dim. incr. insertion
 \ Shellsort with stack-seletion

 \ Splicesort
 \ Splicesort with insertion
 \ Splicesort with selection

 \ Batchersort

 \ Mergesort, binary subdivision
 \ Mergesort, natural

 \ Quicksort, first pivot element
 \ Quicksort, random pivot element
 \ Quicksort, middle pivot element
 \ Quicksort, median-of-three pivot
 \ Quicksort-partition + other sort

 It will be awhile before I have enough time to explore this variety of
 sorts.
 ---
  * Via Qwikmail 2.01

 NET/Mail : British Columbia Forth Board - Burnaby BC - (604)434-5886  
-----
This message came from GEnie via willett through a semi-automated process.



Mon, 10 Aug 1992 09:34:55 GMT  
 All Sorts of Sorts

 Date: 02-23-90 (06:44)              Number: 2950 (Echo)
   To: BILL MCCARTHY                 Refer#: 2943
 From: STEVE PALINCSAR                 Read: 02-23-90 (18:12)
 Subj: SELECTION SORT                Status: PUBLIC MESSAGE

 No, adding a few unordered records wasn't my application.  My stuff
 comes down in item number order, which corresponds roughly to when the
 records were created -- actually, when the bibliographers & analysts
 applied for the number, I think, not when they got the job finished! --
 and I have to rearrange them into author title order.  Since the
 selection sort handles my data sets in under 2 seconds, it's hard to see
 how _any_ improvement in sort methodology would produce a meaningful
 improvement in run time!

 OTOH, the insertion sort also got a very good write-up in both Knuth &
 Sedgewick, and I do intend one of these days to take a look at it.

 BTW, nice to hear from you again!  How's it going?
-----
This message came from GEnie via willett through a semi-automated process.



Thu, 13 Aug 1992 05:54:46 GMT  
 All Sorts of Sorts

 Date: 02-25-90 (09:15)              Number: 2965 (Echo)
   To: IAN GREEN                     Refer#: NONE
 From: STEVE PALINCSAR                 Read: NO
 Subj: DO LOOPS IN FORTH             Status: PUBLIC MESSAGE

 Ian, you're probably looking for something like this:
 : LOOP_DEMONSTRATION  ( n2 n1 -- )
 \ That is, both the inner and outer loop limits are on the stack
 \ before this word executes.  You could put them there by fetching
 \ from a couple of variables, or whatever other means you like.
    1 DO        ( Takes n1 from param stack, puts in on Rstack )
       1 DO     ( Takes n2 from param stack, puts it on Rstack )
           <SOMETHING>  ( whatever you want to execute )
       LOOP
    LOOP  ;

 The "FOR-NEXT" construct in Forth is written as DO - LOOP.  
-----
This message came from GEnie via willett through a semi-automated process.



Sat, 15 Aug 1992 07:17:30 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Sort (List sorts...)

2. Binary Sort/Merge Sort in awk

3. Sort of Sorts

4. All Sorts of Sorts

5. All Sorts of Sorts

6. All Sorts of Sorts

7. Bubble sort/Selection sort help neded.

8. Qsort, Merge sort, Radix sort in prolog Help!

9. UNIX sort exponents (bc|sort)

10. ANN: New release of S.C.A. Micro Templates (Browse Header Sort and Reverse Sort Template)

11. Straight Insertion Sort and Binary Insertion Sort

12. Sorting a file w/o SORT verb

 

 
Powered by phpBB® Forum Software