--- a/SequenceableCollection.st Tue Apr 04 12:21:22 2000 +0200
+++ b/SequenceableCollection.st Fri Apr 07 10:08:19 2000 +0200
@@ -10,6 +10,8 @@
hereby transferred.
"
+"{ Package: 'stx:libbasic' }"
+
Collection subclass:#SequenceableCollection
instanceVariableNames:''
classVariableNames:'MissingClassInLiteralArrayErrorSignal'
@@ -2897,6 +2899,52 @@
!SequenceableCollection methodsFor:'private sorting helpers'!
+mergeFirst: first middle: middle last: last into: dst by: aBlock
+ "Private!!
+ Merge the sorted ranges [first..middle] and [middle+1..last] of the receiver into the range [first..last] of dst."
+
+ | i1 i2 val1 val2 out |
+
+ i1 := first.
+ i2 := middle + 1.
+ val1 := self at: i1.
+ val2 := self at: i2.
+ out := first - 1. "will be pre-incremented"
+
+ "select 'lower' half of the elements based on comparator"
+ [(i1 <= middle) and: [i2 <= last]] whileTrue: [
+ (aBlock value: val1 value: val2)
+ ifTrue: [
+ dst at: (out := out + 1) put: val1.
+ val1 := self at: (i1 := i1 + 1)]
+ ifFalse: [
+ dst at: (out := out + 1) put: val2.
+ i2 := i2 + 1.
+ i2 <= last ifTrue: [val2 := self at: i2]]].
+
+ "copy the remaining elements"
+ i1 <= middle
+ ifTrue: [
+ dst replaceFrom: out + 1 to: last with: self startingAt: i1]
+ ifFalse: [
+ dst replaceFrom: out + 1 to: last with: self startingAt: i2].
+
+!
+
+mergeSortFrom: first to: last src: src dst: dst by: aBlock
+ "Private!! Split the range to be sorted in half, sort each half, and merge the two half-ranges into dst."
+
+ | middle |
+
+ first = last ifTrue: [^ self].
+ middle := (first + last) // 2.
+ self mergeSortFrom: first to: middle src: dst dst: src by: aBlock.
+ self mergeSortFrom: middle + 1 to: last src: dst dst: src by: aBlock.
+ src mergeFirst: first middle: middle last: last into: dst by: aBlock.
+
+
+!
+
quickSortFrom:inBegin to:inEnd
"actual quicksort worker for sort-message"
@@ -3226,6 +3274,47 @@
"Modified: / 8.5.1998 / 21:27:18 / cg"
!
+isSorted
+ "return true. if my elements are sorted (already)"
+
+ |lastEl el|
+
+ lastEl := self first.
+ 2 to:self size do:[:i |
+ el := self at:i.
+ el >= lastEl ifFalse: [^ false].
+ lastEl := el
+ ].
+ ^ true
+
+ "
+ #(1 2 3 5 10 100) isSorted
+ #(1 2 3 5 100 10) isSorted
+ "
+!
+
+isSortedBy:aBlock
+ "return true, if my elements are sorted (already) by the given criterion (sortBlock)"
+
+ |lastEl el|
+
+ lastEl := self first.
+ 2 to:self size do:[:i |
+ el := self at:i.
+ (aBlock value:lastEl value:el) ifFalse: [^ false].
+ lastEl := el
+ ].
+ ^ true
+
+ "
+ #(1 2 3 5 10 100) isSortedBy:[:a :b | a <= b]
+ #(1 2 3 5 100 10) isSortedBy:[:a :b | a <= b]
+ #(100 10 5 3 2 1) isSortedBy:[:a :b | a <= b]
+ #(100 10 5 3 2 1) isSortedBy:[:a :b | a > b]
+ "
+
+!
+
keys
"return a collection with all keys in the Smalltalk dictionary"
@@ -4472,6 +4561,84 @@
!SequenceableCollection methodsFor:'sorting & reordering'!
+mergeSort
+ "sort the collection using a mergeSort algorithm.
+ The elements are compared using'<'
+ i.e. they should offer a magnitude-like protocol.
+
+ The implementation uses the mergesort algorithm, which may not be
+ the best possible for all situations
+ See also #quickSort and #randomizedSort for other sort algorithms
+ with different worst- and average case behavior)"
+
+ |stop|
+
+ stop := self size.
+ (stop > 1) ifTrue:[
+ self mergeSortFrom:1 to:stop by:[:a :b | a < b ]
+ ]
+
+ "
+ #(1 16 7 98 3 19 4 0) mergeSort
+
+ |data|
+ data := Random new next:100000.
+ 'merge random ' print. (Time millisecondsToRun:[data mergeSort]) printNL.
+ 'merge sorted ' print. (Time millisecondsToRun:[data mergeSort]) printNL.
+ data reverse.
+ 'merge reverse ' print. (Time millisecondsToRun:[data mergeSort]) printNL.
+
+ data := Random new next:100000.
+ 'quick random ' print. (Time millisecondsToRun:[data sort]) printNL.
+ 'quick sorted ' print. (Time millisecondsToRun:[data sort]) printNL.
+ data reverse.
+ 'quick reverse ' print. (Time millisecondsToRun:[data sort]) printNL.
+
+ data := Random new next:100000.
+ 'quickr random ' print. (Time millisecondsToRun:[data randomizedSort]) printNL.
+ 'quickr sorted ' print. (Time millisecondsToRun:[data randomizedSort]) printNL.
+ data reverse.
+ 'quickr reverse ' print. (Time millisecondsToRun:[data randomizedSort]) printNL.
+ "
+
+!
+
+mergeSortFrom: startIndex to: stopIndex by: aBlock
+ "Sort the given range of indices using the mergesort algorithm.
+ Mergesort is a worst-case O(N log N) sorting algorithm that usually does only half
+ as many comparisons as heapsort or quicksort."
+
+ "Details: recursively split the range to be sorted into two halves,
+ mergesort each half, then merge the two halves together.
+ An extra copy of the data is used as temporary storage and successive merge phases copy data back
+ and forth between the receiver and this copy.
+ The recursion is set up so that the final merge is performed into the receiver,
+ resulting in the receiver being completely sorted."
+
+ | temp |
+
+ self size <= 1 ifTrue: [^ self]. "nothing to do"
+ startIndex = stopIndex ifTrue: [^ self].
+ (startIndex >= 1 and: [startIndex < stopIndex])
+ ifFalse: [self error: 'bad start index'].
+ stopIndex <= self size
+ ifFalse: [self error: 'bad stop index'].
+ temp := self clone.
+ self mergeSortFrom: startIndex to: stopIndex src: temp dst: self by: aBlock.
+
+ "
+ #(1 16 7 98 3 19 4 0) mergeSort
+
+ |data|
+ data := Random new next:100000.
+ 'random ' print. (Time millisecondsToRun:[data mergeSort]) printNL.
+ 'sorted ' print. (Time millisecondsToRun:[data mergeSort]) printNL.
+ data reverse.
+ 'reverse ' print. (Time millisecondsToRun:[data mergeSort]) printNL.
+ "
+
+!
+
randomizedSort
"sort the collection inplace. The elements are compared using
'<' i.e. they should offer a magnitude-like protocol.
@@ -4760,6 +4927,6 @@
!SequenceableCollection class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/SequenceableCollection.st,v 1.130 2000-03-24 09:52:30 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/SequenceableCollection.st,v 1.131 2000-04-07 08:08:19 cg Exp $'
! !
SequenceableCollection initialize!