
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 log2n) sorts
Shell Sort
O(n2) 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


Given an Array, derive a sequence of elements in which all duplicates are removed.

There are basically three approaches seen here:

 Put the elements into a hash table which does not allow duplicates. The complexity is O(n) on average, and O(n2) worst case. This approach requires a hash function for your type (which is compatible with equality), either built-in to your language, or provided by the user.
 Sort the elements and remove consecutive duplicate elements. The complexity of the best sorting algorithms is O(n log n). This approach requires that your type be "comparable", i.e., have an ordering. Putting the elements into a self-balancing binary search tree is a special case of sorting.
 Go through the list, and for each element, check the rest of the list to see if it appears again, and discard it if it does. The complexity is O(n2). The up-shot is that this always works on any type (provided that you can test for equality).


100 PROGRAM "RemoveDu.bas"
110 RANDOMIZE
120 NUMERIC ARR(1 TO 20),TOP
130 LET TOP=FILL(ARR)
140 CALL WRITE(ARR,TOP)
150 LET TOP=REMOVE(ARR)
160 CALL WRITE(ARR,TOP)
170 DEF WRITE(REF A,N)
180   FOR I=1 TO N
190     PRINT A(I);
200   NEXT
210   PRINT
220 END DEF
230 DEF FILL(REF A)
240   LET FILL=UBOUND(A):LET A(LBOUND(A))=1
250   FOR I=LBOUND(A)+1 TO UBOUND(A)
260     LET A(I)=A(I-1)+RND(3)
270   NEXT
280 END DEF 
290 DEF REMOVE(REF A)
300   LET ST=0
310   FOR I=LBOUND(A)+1 TO UBOUND(A)
320     IF A(I-1)=A(I) THEN LET ST=ST+1
330     IF ST>0 THEN LET A(I-ST)=A(I)
340   NEXT 
350   LET REMOVE=UBOUND(A)-ST
360 END DEF