Here is a challenge for you :-)
Christopher K Roach
chrisroach at btinternet.com
Sat Nov 17 20:07:18 UTC 2001
Sorting Algorithm,
I am not allowed to use the SortedCollection type.
Can you do the below without using SortedCollection, is that possible? Ya
see I want to impress my supervisor without using it, I suppose I could use
Orderedlist, any of you guys know how I would do this?
mysort.pt
!Collection methodsFor: `converting`!
asSortedCollection
| aSortedCollection |
aSortedCollection := SortedCollection new.
aSortedCollection addAll: self.
^aSortedCollection
!
asSortedCollection: aBlock
| aSortedCollection |
aSortedCollection := SortedCollection sortBlock: aBlock.
aSortedCollection addAll: self.
^aSortedCollection
!!
!SortedCollection methodsFor: `adding elements`!
addAll: aCollection
| newSortedCollection |
newSortedCollection _ self growTo: self basicSize + aCollection size.
firstIndex to: lastIndex do: [ :index |
newSortedCollection basicAt: index
put: (self basicAt: index)
].
aCollection do: [ :element |
lastIndex := lastIndex + 1.
newSortedCollection basicAt: lastIndex put: element
].
newSortedCollection firstIndex: firstIndex
lastIndex: lastIndex.
newSortedCollection resort.
^self become: newSortedCollection
!!
!SortedCollection methodsFor: `private`!
resort
self quicksort: firstIndex to: lastIndex
!
quicksort: begin to: end
"This is an implementation of the Quick Sort algorithm, which
is O(n*log(n)), where n is the size of the collection to
be sorted."
| pivot i j temp middle |
i := begin.
j := end.
middle := (i + j) // 2.
pivot := self basicAt: middle.
[ i > j ] whileFalse: [
[ temp := self basicAt: i.
(sortBlock value: pivot value: temp) not
and: [ sortBlock value: temp value: pivot ]
] whileTrue: [ i := i + 1 ].
[ temp := self basicAt: j.
(sortBlock value: temp value: pivot) not
and: [ sortBlock value: pivot value: temp ]
] whileTrue: [ j := j - 1 ].
(i <= j) ifTrue: [
(i == j) ifFalse: [
temp := self basicAt: i.
self basicAt: i put: (self basicAt: j).
self basicAt: j put: temp.
].
i := i + 1.
j := j - 1
]
].
(begin < j)
ifTrue: [ self quicksort: begin to: j ].
(i < end)
ifTrue: [ self quicksort: i to: end ]
!!
!SortedCollection methodsFor: `instance protocol`!
sortBlock: aSortBlock
"Change the sort criteria for a sorted collection,
resort the elements of the collection, and return it."
| newSortedCollection |
self setSortBlock: aSortBlock.
self resort
Bert Freudenberg <bert at i...> wrote the following:
order := [:a :b |
a title < b title or: [
a title = b title and: [a name < b name or: [
a name = b name and: [a ref < b ref or: [
a number < b number]]]]]]
Then you can use a SortedCollection with this order to sort:
s := SortedCollection sortBlock: order.
s addAll: unsorted.
s do: [:obj | obj print]
More information about the Squeak-dev
mailing list
|