Pseudocode_4.md

Anhang 1: Pseudocode

Function RECURSIVE-SORT-AND-FIND-UNIQUES(Matrix, start, size, depth)
	end <- start + n-1	
	down_runner <- start
	up_runner <- end
	zeros <- 0
	ones <- 0
	
	while true:
		while (down-runner < end) AND (Matrix[down-runner][depth] == 0):
			INCREMENT(down_runner)
			INCREMENT(zeros)
			
		if (down-runner == start + n-1): 
			if (Matrix[down-runner][depth] == 0):
				INCREMENT(zeros)
			else:
				INCREMENT(ones)
			break
			
		while (up-runner > start) AND (Matrix[up-runner][depth] == 1):
			DECREMENT(up_runner)
			INCREMENT(ones)
		
		if (up-runner == start):
			if (Matrix[up-runner][depth] == 1):
				INCREMENT(ones)
			break
	
	    if (down-runner < up-runner):
			// Swap the elements pointed to by down-runner and up-runner.
			SWAP(Matrix, down_runner, up_runner)
		else:
			break
		
	// LENGTH(Matrix[0]) gives the length of any vector.
	if depth == (LENGTH(Matrix[0])):
		uniques <- []
		counts <- []
		
		if zeros > 0:
			uniques.APPEND(Matrix[start])
			counts.APPEND(zeros)
		if ones > 0:
			uniques.APPEND(Matrix[end])
			counts.APPEND(ones)
		
		return Tuple(counts, uniques)
		
	uniques <- []
	counts <- []
		
	if (zeros > 0):
		counts_0, uniques_0 = UNPACK(RECURSIVE-SORT-AND-FIND-UNIQUES(Matrix, start, zeros, depth+1))
		uniques.APPEND(uniques_0)
		counts.APPEND(counts_0)
		
	if (ones > 0):
		counts_1, uniques_1 = UNPACK(RECURSIVE-SORT-AND-FIND-UNIQUES(Matrix, start+zeros, ones, depth+1))
		uniques.APPEND(uniques_1)
		counts.APPEND(counts_1)
	
	return Tuple(counts, uniques)