Sorting algorithms/Tree sort on a linked list

Sorting algorithms/Tree sort on a linked list is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

This page uses content from Wikipedia. The current wikipedia article is at article. The original RosettaCode article was extracted from the wikipedia article № 295989333 of 15:13, 12 June 2009 . The list of authors can be seen in the page history. As with Rosetta Code, the pre 5 June 2009 text of Wikipedia is available under the GNU FDL. (See links for details on variance)

A tree sort is a sort algorithm that builds a binary search tree from the keys to be sorted, and then traverses the tree (in-order) so that the keys come out in sorted order. Its typical use is when sorting the elements of a stream from a file. Several other sorts would have to load the elements to a temporary data structure, whereas in a tree sort the act of loading the input into a data structure is sorting it.

The tree sort is considered by some to be the faster method to sort a linked list, followed by Quicksort and Mergesort:

• A Comparative Study of Linked List Sorting Algorithms by Ching-Kuang Shene

Sediment sort, bubble sort, selection sort perform very badly.

Test case: Create a linked list of all the sentences of all the episodes of Finnegans Wake by James Joyce. Load them into a local memory based linked list, then tree sort them inplace and print the number of node swaps and seconds of BogoMips are necessary to perform the sort. (The book is to be stored locally (whole or in individual episodes) in a test text file on disk before loading by the specimin code into a linked list for sorting.)

Racket

Translation of: Scheme

-- this implementation illustrates differences in identifiers and syntaxes of Scheme and Racket's match-lambda family. racket/match documented here.

<lang racket>#lang racket/base (require racket/match)

(define insert

 ;; (insert key tree)
 (match-lambda**
  [(x '())         `(() ,x ())]
  [(x '(() () ())) `(() ,x ())]
  [(x `(,l ,k ,r)) #:when (<= x k) `(,(insert x l) ,k ,r)]
  [(x `(,l ,k ,r)) `(,l ,k ,(insert x r))]
  [(_ _) "incorrect arguments or broken tree"]))

(define in-order

 ;; (in-order tree)
 (match-lambda
   [`(() ,x ()) `(,x)]
   [`(,l ,x ())  (append (in-order l) `(,x))]
   [`(() ,x ,r)  (append `(,x) (in-order r))]
   [`(,l ,x ,r)  (append (in-order l) `(,x) (in-order r))]
   [_ "incorrect arguments or broken tree"]))

(define (tree-sort lst)

 (define tree-sort-itr
   (match-lambda**
     [(x `())        (in-order x)]
     [(x `(,a . ,b)) (tree-sort-itr (insert a x) b)] 
     [(_ _) "incorrect arguments or broken tree"]))
 (tree-sort-itr '(() () ()) lst))

(tree-sort '(5 3 7 9 1))</lang>

Output:

'(1 3 5 7 9)

Scheme

The following implements a sorting algorithm that takes a linked list, puts each key into an unbalanced binary tree and returns an in-order traversal of the tree.

Library: Matchable

Works with: Chicken Scheme

<lang Scheme>(use matchable)

(define insert

 ;; (insert key tree)
 (match-lambda*
  [(x ())         `(() ,x ()) ]
  [(x (() () ())) `(() ,x ()) ]
  [(x (l k r))
   (=> continue)
   (if (<= x k)

`(,(insert x l) ,k ,r) (continue)) ]

  [(x (l k r)) `(,l ,k ,(insert x r)) ]
  [_ "incorrect arguments or broken tree" ]))

(define in-order

 ;; (in-order tree)
 (match-lambda
  [(() x ()) `(,x)]
  [(l x ())  (append (in-order l) `(,x))]
  [(() x r)  (append `(,x) (in-order r))]
  [(l x r)   (append (in-order l) `(,x) (in-order r))]
  [_ "incorrect arguments or broken tree" ]))

(define (tree-sort lst)

 (define tree-sort-itr
   (match-lambda*
    [(x ())      (in-order x)]
    [(x (a . b)) (tree-sort-itr (insert a x) b)] 
    [_ "incorrect arguments or broken tree" ]))
 (tree-sort-itr '(() () ()) lst))</lang>

Usage: <lang Scheme> #;2> (tree-sort '(5 3 7 9 1)) (1 3 5 7 9)</lang>