#DOCUMENTATION by mawalch
class: SequenceableCollection
comment/format in:
#insertionSort:from:to:
#mergeFirst:middle:last:into:by:
--- a/SequenceableCollection.st Tue Feb 21 14:55:37 2017 +0100
+++ b/SequenceableCollection.st Tue Feb 21 14:56:34 2017 +0100
@@ -1,5 +1,3 @@
-"{ Encoding: utf8 }"
-
"
COPYRIGHT (c) 1989 by Claus Gittinger
All Rights Reserved
@@ -435,7 +433,6 @@
! !
-
!SequenceableCollection methodsFor:'Compatibility-Squeak'!
allButFirst
@@ -7134,10 +7131,10 @@
!SequenceableCollection methodsFor:'private-sorting helpers'!
-mergeFirst:first middle:middle last:last into:dst by:aBlock
+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.
@@ -7149,7 +7146,7 @@
val2 := self at:i2.
"select 'lower' half of the elements based on comparator"
[(i1 <= middle) and:[i2 <= last]] whileTrue:[
- "this is stable if #< or #> ist used for comparison (and not #<= or #>=)"
+ "this is stable if #< or #> is used for comparison (and not #<= or #>=)"
(aBlock value:val2 value:val1) ifTrue:[
dst at:out put:val2.
i2 := i2 + 1.
@@ -7167,18 +7164,20 @@
"copy the remaining elements"
i1 <= middle ifTrue:[
- dst
+ dst
replaceFrom:out
to:last
with:self
startingAt:i1
] ifFalse:[
- dst
+ dst
replaceFrom:out
to:last
with:self
startingAt:i2
].
+
+ "Modified (format): / 21-02-2017 / 14:33:35 / mawalch"
!
mergeSortFrom: first to: last by: aBlock
@@ -9882,7 +9881,7 @@
insertionSort:sortBlock from:inBegin to:inEnd
"binary insertion sort.
- The implementation uses the insertionSort algorithm,
+ The implementation uses the insertionSort algorithm,
which is slow for large collections O(n*n), but good for small or
almost sorted collections O(N)."
@@ -9896,7 +9895,7 @@
begin to:end do:[:idx|
temp := self at:idx.
prevIdx := idx-1.
- "this is stable if #< or #> ist used for comparison (and not #<= or #>=)"
+ "this is stable if #< or #> is used for comparison (and not #<= or #>=)"
[prevIdx >= inBegin and:[sortBlock value:temp value:(self at:prevIdx)]] whileTrue:[
self at:prevIdx+1 put:(self at:prevIdx).
prevIdx := prevIdx - 1.
@@ -9920,6 +9919,8 @@
data reverse.
Transcript show:'insert reverse '; showCR:(Time millisecondsToRun:[data insertionSort]).
"
+
+ "Modified (comment): / 21-02-2017 / 14:33:09 / mawalch"
!
mergeSort