
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).


		org	100h
		jmp	test
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;; Given an array of bytes starting at HL with length BC,
		;; remove all duplicates in the array. The new end of the array
		;; is returned in HL. A page of memory (256 bytes) is required
		;; to mark which bytes have been seen.
uniqpage:	equ	3	; Page to use - a compile-time constant.
				; This would need to be set to a page that
				; the rest of the program doesn't need.
uniq:		xra	a	; Zero out the page
		lxi	d,uniqpage * 256
uniqzero:	stax	d	; Zero out a byte
		inr	e	; And do the next byte
		jnz	uniqzero
		mov	d,h	; Keep a second pointer to the array in DE
		mov	e,l
uniqpos:	ldax	d	; Read from high pointer
		mov	m,a	; Write to low pointer
		inx	d	; Increment the high pointer
		push	h	; Keep low pointer around
		mvi	h,uniqpage	
		mov	l,a	; Have we seen this byte yet?
		cmp	m	
		mov	m,a	; No matter what, we've certainly seen it now
		pop	h	; Bring back the low pointer
		jz	uniqno	; If we already had it, don't increment low ptr
		inx	h	; IF we didn't, do increment it
uniqno:		dcx	b	; One fewer byte left
		mov	a,b	; If there are zero bytes left,
		ora	c
		rz		; Then return to caller
		jmp	uniqpos	; Otherwise, do the next byte
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		;; Testing code: read a string from the CP/M console, run
		;; uniq, then print the output.
test:		lxi	d,bufdef	; Read a string
		mvi	c,10
		call	5
		lxi	d,nl		; Output on new line
		mvi	c,9
		call	5
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		lda	bufdef+1	; Length of input string
		mov	c,a		; Extend to 16-bit (since uniq supports
		mvi	b,0		; long arrays)
		lxi	h,buf		; Location of input string
		call	uniq		; Only the unique bytes
		;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
		mvi	m,'$'		; Mark the (string) end with '$'
		lxi 	d,buf		; Print the string, which now has had
		mvi	c,9		; all duplicates removed. 
		jmp	5 
nl:		db	13,10,'$'
bufdef:		db	127,0
buf: