| Author |
Compact MergeSort :)
|
|
| Alexander Seidl 2005-11-12, 7:57 am |
| Hi at all,
one of my exercises in highschool was to implement the mergesort
algorithm with smalltalk. Dont worry :) i dont want u to do my
exercises. i wrote already an implentation of it. and i think its not
bad. but im far away from being a smalltalk guru :)
Do u think, u could do it shorter? :)
to the code:
'mergeSort' provides 'merge' with two sections of the collection that
has to be sorted. both of them are sorted. 'merge' now merges these
sections into one temp-collection and writes it back to the original
unsorted Collection at the right position.
to read from the sections, 'merge' produces two streams from them.
------Code--------
"
mergeSort
"
mergeSort: l and: r
| m |
(r <= l) ifTrue: [^nil].
m := (r+l)/2 truncateTo: 1.
self mergeSort: l and: m.
self mergeSort: m+1 and: r.
self merge: l and: m and: r.
"
merge
"
merge: l and: m and: r
| temp rsLeft rsRight rsTemp |
temp := OrderedCollection new.
rsRight := (rsLeft := self outputSeq readStream) copy.
rsLeft readLimit: m; position: l-1.
rsRight readLimit: r; position: m.
[(rsLeft atEnd not) & (rsRight atEnd not)] whileTrue:
[
(self compare: rsLeft p to: rsRight p)
ifTrue: [temp add: rsLeft next]
ifFalse: [temp add: rsRight next].
].
temp addAll: (rsLeft upToEnd); addAll: (rsRight upToEnd).
rsTemp := temp readStream.
l to: r do: [:i|self at: i put: rsTemp next.]
------------------
| |
| Alexander Seidl 2005-11-12, 7:57 am |
| Alexander Seidl schrieb:
> l to: r do: [:i|self at: i put: rsTemp next.]
uh, i forgot to explain the meaning of 'self' in this case. self is an
MergeSorter object. 'at:put:' was overriden to write into an instance
variable 'outputSeq' which contains the unsorted collection.
Regards,
Alexander
| |
| Joseph Pelrine 2005-11-12, 7:57 am |
| Alexander Seidl wrote:
> Hi at all,
> one of my exercises in highschool was to implement the mergesort
> algorithm with smalltalk. Dont worry :) i dont want u to do my
> exercises. i wrote already an implentation of it. and i think its not
> bad. but im far away from being a smalltalk guru :)
> Do u think, u could do it shorter? :)
Probably. For an similar example (with excellent detailed explanation),
read John Brant's classic post at
http://groups.google.com/group/comp...lk+author:brant
Cheers
Joseph
>
> to the code:
> 'mergeSort' provides 'merge' with two sections of the collection that
> has to be sorted. both of them are sorted. 'merge' now merges these
> sections into one temp-collection and writes it back to the original
> unsorted Collection at the right position.
> to read from the sections, 'merge' produces two streams from them.
>
> ------Code--------
> "
> mergeSort
> "
>
> mergeSort: l and: r
> | m |
> (r <= l) ifTrue: [^nil].
> m := (r+l)/2 truncateTo: 1.
> self mergeSort: l and: m.
> self mergeSort: m+1 and: r.
> self merge: l and: m and: r.
>
> "
> merge
> "
>
> merge: l and: m and: r
> | temp rsLeft rsRight rsTemp |
> temp := OrderedCollection new.
> rsRight := (rsLeft := self outputSeq readStream) copy.
> rsLeft readLimit: m; position: l-1.
> rsRight readLimit: r; position: m.
>
> [(rsLeft atEnd not) & (rsRight atEnd not)] whileTrue:
> [
> (self compare: rsLeft p to: rsRight p)
> ifTrue: [temp add: rsLeft next]
> ifFalse: [temp add: rsRight next].
> ].
>
> temp addAll: (rsLeft upToEnd); addAll: (rsRight upToEnd).
> rsTemp := temp readStream.
> l to: r do: [:i|self at: i put: rsTemp next.]
>
> ------------------
| |
| Ricardo Birmann 2005-11-12, 7:00 pm |
| mergesort as a smalltalk exercise? hmmm
| |
| Alexander Seidl 2005-11-12, 7:00 pm |
| Ricardo Birmann schrieb:
> mergesort as a smalltalk exercise? hmmm
>
yes :) why does this make u thoughtful?
Alexander
| |
|
|
| Alexander Seidl 2005-11-13, 7:57 am |
| Andrew Tween schrieb:
> I'll give you some tips
Thats nice! Thx :)
>
>
> m := r+l // 2.
Hmhm, ok. This is really better.
>
>
> self
> mergeSort: l and: m;
> mergeSort: m+1 and: r;
> merge: l and: m and: r.
Yes! Cascading. Why did i forget to use this? Odd :-)
>
> Don't do it. Please. :)
Hmmm, okok :) I try to get rid of it :)
>
>
> [rsLeft atEnd or:[rsRight atEnd]] whileFalse:
Ok, i save the 'not'. But my version is the way the brain thinks.
>
>
> [
> temp add: ((self compare: rsLeft p to: rsRight p)
> ifTrue: [rsLeft next]
> ifFalse: [rsRight next]).
> ].
>
Yes! this is a very nice structure! much better than mine!
>
>
>
> temp addAll: rsLeft upToEnd; addAll: rsRight upToEnd.
>
Ok, saving the brackets.
>
>
>
> l to: r do:[:i | self at: i put: (temp at: l - i + 1)].
>
im not very good in juggling indices. but probably your structure is
better due to performance considerations.
Thank u very much for ur hints, Andrew. i will follow them in the future.
Regards,
Alexander
| |
| 1862076129Alex Baran 2005-11-14, 7:02 pm |
| (Alexander Seidl) wrote (abridged):
> is it possible to write this shorter?
If speed don't matter:
mergeSort
| middle part1 part2 |
self size <=3D 1 ifTrue: [^self].
middle :=3D self size // 2.
part1 :=3D self copyFrom: 1 to: middle.
part2 :=3D self copyFrom: middle+1 to: self size.
^(part1 mergeSort) mergeWith: (part2 mergeSort)
mergeWith: aCollection
| a b result |
a :=3D self asOrderedCollection.
b :=3D aCollection asOrderedCollection.
result :=3D OrderedCollection new.
[(a isEmpty) | (b isEmpty)] whileFalse:=20
[result add: (a first < b first
ifTrue: [a removeFirst]
ifFalse: [b removeFirst])].
result addAll: (a isEmpty
ifTrue: [b]=20
ifFalse: [a]).
^self species withAll: result
| |
|
| Hi,
sorry, I can't resist:
mergeSort:
^self asSortedCollection.
Sorry again,
Janos
| |
| Alexander Seidl 2005-11-15, 7:03 pm |
| 1862076129Alex Baran schrieb:
> If speed don't matter:
>
> mergeSort
> | middle part1 part2 |
> self size <= 1 ifTrue: [^self].
> middle := self size // 2.
> part1 := self copyFrom: 1 to: middle.
> part2 := self copyFrom: middle+1 to: self size.
> ^(part1 mergeSort) mergeWith: (part2 mergeSort)
>
> mergeWith: aCollection
> | a b result |
> a := self asOrderedCollection.
> b := aCollection asOrderedCollection.
> result := OrderedCollection new.
> [(a isEmpty) | (b isEmpty)] whileFalse:
> [result add: (a first < b first
> ifTrue: [a removeFirst]
> ifFalse: [b removeFirst])].
> result addAll: (a isEmpty
> ifTrue: [b]
> ifFalse: [a]).
> ^self species withAll: result
Hi Alex,
this looks very nice. I underrated the power of OrderedCollections. But
why do you wrote: "If speed don't matter"? Due to the fact that
mergeSort is recursive? Is it possible at all to get mergeSort faster?
Cheers,
Alexander
| |
|
| Ricardo Birmann wrote:
> mergesort as a smalltalk exercise? hmmm
>
:-)
Sounds like the games that functional programmers like to play ;-)
Whats wrong with #asSorted collection :-P
|
|
|
|