Perl Sorting Examples

• Selection sorting.
  Remember that selection sort works by finding the smallest element and moving it into the first position, then finding the second smallest and moving it into the second position. In general, on the ith iteration, it finds the ith smallest element and move it to position i. This works as follows:
  (selection '(6 4 5 3 9 3))
  (cons 3 (selection '(6 4 5 9 3))
  (cons 3 (cons 3 (selection '(6 4 5 9))
  (cons 3 (cons 3 (cons 4 (selection '(6 5 9))
  (cons 3 (cons 3 (cons 4 (cons 5 (selection '(6 9))
  (cons 3 (cons 3 (cons 4 (cons 5 (cons 6 (selection '(9))
  (cons 3 (cons 3 (cons 4 (cons 5 (cons 6 (cons 9 (selection '())
  Which becomes (3 3 4 5 6 9).
  The scheme code below does exactly this:

  sub selectionsort {
  	my @templis;
  	my @templis2;
  	my $s;
  	
  	if (scalar(@_) == 0) {
  		return ();
  	} else {	# put the smallest element at the front of the  current list 
  			# call selection on the list minus the smallest  element
  		$s = smallest(@_[1..$#_], $_[0]);
  		@templis = selectionsort(remove($s, @_));
  		unshift(@templis, $s);
  		return @templis;
  	}
  }
  
  
  # remove the first occurance of atom A from L
  sub remove {
  	my ($element, @lis) = @_;
  	my @templis;
  	
  	if (scalar(@lis) == 0) {
  		return ();
  	}
  	elsif ($lis[0] == $element) {
  		return @lis[1..$#lis];
  	} else {
  		@templis = remove($element, @lis[1..$#lis]);
  		unshift(@templis, $lis[0]);
  		return @templis;
  	}
  }
  
  sub smallest {     # looks for the smallest element in the list
                                      #atom A is the current smallest
  	my ($element, @lis) = @_;
  	if (scalar(@lis) == 0) {
  		return $element;	
  	} elsif ($lis[0] < $element) {
  		return smallest(@lis[1..$#lis], $lis[0]);
  	} else {
  		return smallest(@lis[1..$#lis], $element);
  	}
  }
  
  x = [6,3,4,9,10,1,7]
  print x, "\n"
  print smallest(x, 6), "\n"
  #print myremove(x, smallest(x,6))
  print selection(x), "\n"
  
  

• Merge Sort
  Mergesort divides the list in half everytime, calling itself on each half. As the recursion unwinds, it merges the sorted list into a new sorted list. For example, assume we have the following:
  

              (mergesort '(6 4 5 7 8 9 3 4))
                       /                    \
      (mergesort '(6 4 5 7))                 (mergesort '(8 9 3 4))
              /             \                   /             \
  (mergesort '(6 4)) (mergesort '(5 7)) (mergesort '(8 9)) (mergesort '(3 4))
  

  At the lowest tree leves, the two element get sorted and the recursion unwinds.

              (mergesort '(6 4 5 7 8 9 3 4))
                       /                    \
      (mergesort '(6 4 5 7))                 (mergesort '(8 9 3 4))
              /             \                   /             \
           (4 6)          (5 7)              (8 9))          (3 4))
  

  The next level of recursion:

              (mergesort '(6 4 5 7 8 9 3 4))
                       /                    \
                (4 5 6 7))                 (3 4 8 9)
                /     \                     /    \
             (4 6)    (5 7)              (8 9))  (3 4))
  

  And the final level with merges into the overall list

                           (3 4 4 5 6 7 8 9)
                            /             \
                        (4 5 6 7)      (3 4 8 9)
  

  Of course, this is not the actual order that things happen but it give the overall algorithm flavor. In scheme, we can write functions to split lists, and merge sorted lists. Once we have these, the mergesort itself is fairly short.

  
  #####################################################
  # Not yet implemented in Perl...
  
  def mergesort(lis)
  	if lis.length == 0 then
  		 []
  	elsif lis.length == 1 then
  		 lis
  	elsif lis.length == 2 then
  		 mergelists ([lis[0]], lis[1..lis.length-1])
  	else  
  		 mergelists(mergesort(split(lis)[0]),mergesort(split(lis)[1..lis.length-1][0]))
  	end
  end
  
  def mergelists(lis, m)  # assume L and M are sorted lists
  	if lis.length==0 then
  		 m
  	elsif m.length==0 then
  		 lis
  	elsif lis[0] < m[0] then
  		 [lis[0]] + mergelists(lis[1..lis.length-1], m)
  	else
  		 [m[0]] + mergelists(lis, m[1..m.length-1])
  	end
  end
  
  def sub(lis, start, stop, ctr)  # extract elements start to stop into a list
  	if lis.length== 0 then
  		 lis
  	elsif ctr < start then
  		 sub(lis[1..lis.length-1], start, stop, ctr+1)
  	elsif ctr > stop then
  		 []
  	else
  		 [lis[0]] + sub(lis[1..lis.length-1],start, stop, ctr+1)
  	end
  end
  
  def split(lis)	# split the list in half:,   ; returns ((first half)(second half))
  	len=lis.length
  	if len == 0 then
  		 [lis]+[lis]
  	elsif len == 1 then
  		 [lis] + [[]]
  	else
  		 [sub(lis, 1, len//2, 1)] + [sub(lis, (len//2)+1, len, 1)]
  	end
  end
  
  
  

• Binary Tree sort
  The binary tree sort works by building a binary search tree from the input and then traversing it. A binary search tree has the following property at each tree node with value V:
  • any nodes in the left subtree have values < V
  • any nodes in the right subtree have values >= V
  If we can build such a tree from the input, than a inorder visit finds the elements in the correct order.

  
  ; We are going to represent each node in a binary tree as:
  ;  (value (left child)(right child))  If the node has no left 
  ;  and/or right child, this is represented with ().  So,
  ;  (2 (1()())(3()()))  is the tree:   2
  ;                                   /   \
  ;                                  1     3
  
  
  (define (binarysort L)
    (if (null? L) '()
       (traverse (btree L))
  ))
  
  (define (btree L)
    (if (= (length L) 1) (leaf (car L))
          (binsert (btree (cdr L)) (car L))
    )
  )
  
  
  (define (binsert T A)     ; insert A into the tree
     (cond  ( (null? T) (leaf A) )        ; insert here
            ( (> (car T) A) (list (car T) 
                                  (binsert (car (cdr T)) A)
                                  (car (cdr (cdr T))))
             )  ; left subtree 
            ( else (list (car T)
                         (car (cdr T)) 
                         (binsert (car (cdr (cdr T))) A))     ; right subtree
            )
      )
  )
  
  (define (leaf A)          ; add a leaf to the tree (A ()())
     (list A '() '())
  )
  
  (define (traverse L)   ; output sorted list by traversing the tree 
    (cond ( (null? L) L)
          ( else
             (append (traverse (car (cdr L)))
                     (cons (car L)(traverse (car (cdr (cdr L))))))
          )
    )
  )
  
  (define (length L)
    (if (null? L) 0
       (+ 1 (length (cdr L)))
    )
  )