[squeak-dev] The Trunk: Collections-ul.459.mcz

commits at source.squeak.org commits at source.squeak.org
Sat Sep 10 19:45:57 UTC 2011


Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.459.mcz

==================== Summary ====================

Name: Collections-ul.459
Author: ul
Time: 10 September 2011, 9:44:55.456 pm
UUID: ebf26552-eb0f-6246-b67d-6d46a4d5b5eb
Ancestors: Collections-ul.458

- removed an unnecessary check from #quickSortFrom:to:by: (at the end of the loop i < j is guaranteed to be true)

=============== Diff against Collections-ul.458 ===============

Item was changed:
  ----- Method: ArrayedCollection>>quickSortFrom:to:by: (in category 'sorting') -----
  quickSortFrom: from to: to by: sortBlock
  	"Sort elements i through j of self to be nondescending according to sortBlock using an in-place quicksort with simple median-of-three partitioning with guaranteed O(log(n)) space usage."
  
  	| i j |
  	i := from.
  	j := to.
  	[
  		| k l dij temp ij di dj n |
  		"The prefix d means the data at that index."
  		"Sort di,dj."
  		di := self at: i.
  		dj := self at: j.
  		(sortBlock ifNil: [ di <= dj ] ifNotNil: [ sortBlock value: di value: dj ]) ifFalse: [
  			temp := self at: i. self at: i put: (self at: j); at: j put: temp.
  			temp := di. di := dj. dj := temp ].
  		(n := j + 1  - i) <= 2 ifTrue: [ ^self ].
  		"More than two elements."
  		ij := (i + j) // 2.  "ij is the midpoint of i and j."
  		dij := self at: ij.  "Sort di,dij,dj.  Make dij be their median."
  		(sortBlock ifNil: [ di <= dij ] ifNotNil: [ sortBlock value: di value: dij ])
  			ifTrue: [
  				(sortBlock ifNil: [ dij <= dj ] ifNotNil: [ sortBlock value: dij value: dj ]) ifFalse: [
  					temp := self at: j. self at: j put: (self at: ij); at: ij put: temp.
  					dij := dj ] ]
  			ifFalse: [
  				temp := self at: i. self at: i put: (self at: ij); at: ij put: temp.
  				dij := di ].
  		n = 3 ifTrue: [ ^self ].
  		"More than three elements."
  		"Find k>i and l<j such that dk,dij,dl are in reverse order.
  		Swap k and l.  Repeat this procedure until k and l pass each other."
  		k := i.
  		l := j.
  		[
  			[ k <= (l := l - 1) and: [ 
  				sortBlock ifNil: [ dij <= (self at: l) ] ifNotNil: [ sortBlock value: dij value: (self at: l) ] ] ] whileTrue.  "i.e. while dl succeeds dij"
  			[ (k := k + 1) <= l and: [
  				sortBlock ifNil: [ (self at: k) <= dij ] ifNotNil: [ sortBlock value: (self at: k) value: dij ] ] ] whileTrue.  "i.e. while dij succeeds dk"
  			k <= l ] whileTrue: [ temp := self at: k. self at: k put: (self at: l); at: l put: temp. ].
  		"Now l<k (either 1 or 2 less), and di through dl are all less than or equal to dk through dj. Sort the larger segment in this method and call another quicksort for the smaller segment. This ensures O(log(n)) space usage."
  		i < l 
  			ifFalse: [
  				k < j
  					ifFalse: [ ^self ]
  					ifTrue: [ i := k ] ]
  			ifTrue: [
  				k < j
  					ifFalse: [ j := l ]
  					ifTrue: [
  						l - i <  (j - k)
  							ifTrue: [ 
  								self quickSortFrom: i to: l by: sortBlock.
  								i := k ]
  							ifFalse: [
  								self quickSortFrom: k to: j by: sortBlock.
+ 								j := l ] ] ] ] repeat!
- 								j := l ] ] ].
- 		i < j ] whileTrue!




More information about the Squeak-dev mailing list