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