- Insertion sort:
! Object methodsFor: 'algorithms' !
insertionsort
"(FileStream oldFileNamed: 'insertion.st') fileIn.
numbers := #(4 3 16 1 14 25 2) asOrderedCollection.
numbers insertionsort"
self size = 0 ifTrue: [ ^#() asOrderedCollection.]
ifFalse: [
self size = 1 ifTrue: [
^self.
]
ifFalse: [
^self first insert: (self allButFirst insertionsort).
]
]
!
insert: lis
lis size = 0 ifTrue:[
^(OrderedCollection with: self).]
ifFalse: [
self > lis first ifTrue: [
^(OrderedCollection with: lis first),
(self insert: lis allButFirst).
]
ifFalse: [
^(OrderedCollection with: self), lis.
]
]
!
- List flattening
! Object methodsFor: 'algorithms' !
flatten
"(FileStream oldFileNamed: 'flatten.st') fileIn.
numbers := #(1 ((2 3) 4) (((5))) (6 ((7 8)))) asOrderedCollection
numbers flatten"
self size = 0 ifTrue: [ ^#() asOrderedCollection.]
ifFalse: [
self first class = Array ifFalse: [
^(OrderedCollection with: self first),
(self allButFirst flatten).
]
ifTrue: [
^(self first flatten),
(self allButFirst flatten).]
]
!
- Partition function for quicksort
! Object methodsFor: 'algorithms' !
partition
" (FileStream oldFileNamed: 'quicksort2.st') fileIn.
numbers := #(4 3 16 1 14 25 2) asOrderedCollection.
numbers partition.
((<= part) part (> part)) will be returned "
^self allButFirst part: self first.
!
part: pivot
| r y z|
self size = 0 ifTrue: [
^(OrderedCollection with: #() asOrderedCollection),
(OrderedCollection with: pivot),
(OrderedCollection with: #() asOrderedCollection).]
ifFalse: [
r := self allButFirst part: pivot.
" recursive call which will return a list with structure
( (<= pivot) pivot (> pivot)) "
self first > pivot ifTrue: [
y := (OrderedCollection with: r first),
(OrderedCollection with: pivot).
z := (OrderedCollection with: self first),
(r at: 3).
y addLast: z.
^y.]
ifFalse: [
z := r allButFirst.
y := (OrderedCollection with: self first),r first.
z addFirst: y.
^z.
]
]
!
Now, using the above partition function, try to write quicksort. A
soln is here but don't look until you have tried it!