Segregating the positive and negative numbers

[Problem from Knuth,TAOCP, vol.3, p.136]
Design an algorithm that rearranges all the numbers in a given table so that all negative values precede all nonnegative one. (The items need not be sorted completely, just separated between negative and nonnegative.) Your algorithm should use the minimum possible number of exchanges.


Knuth's solution:
Knuth suggests a modified radix exchange sort which compares the MSB (bit corresponding to sign )

Another way to do this is to write a specialized comparison routine which is passed to a sorting routine. The routine can be something like:
compare(a,b)
  if a<0 and b<0: return 0 // same
  if a>0 and b>0: return 0 // same
  return a>b // one -ve, one +ve

Other solution is to include counting sort technique.
The counting sort technique is implemented below in python and is stable.

import random 

N = 50
# generate an array of +ve and -ve numbers.
array = random.sample( range(-N, N), N )

# counting techinque : 2 pass algorithm
def counting_seperate(array):
    num_pos = 0
    num_neg = 0
    for i in array:
        if i<0: num_neg += 1
        else: num_pos += 1
    # destination array
    dest = [0] * len(array)

    #the final index of a +ve number, can simply be len of array
    num_pos += num_neg

    # Count from n-1 to 0 : stable 
    i = len(array)-1
    while i>=0:
        if array[i]< 0: 
            dest[num_neg-1]=array[i]
            num_neg -= 1 # decrease the index 
        else:
            dest[num_pos-1] = array[i]
            num_pos -= 1 # decrease the index
        i -= 1

    print( "segregated array:", dest )

if __name__ == "__main__":
    print( "Original array: ", array )
    counting_seperate(array)

Finding the mth smallest of a given set on n elements.

[Problem posed by C.A.R.Hoare] Suppose that, instead of sorting an entire file, we only want to determine the mth smallest of a given set of n elements. Show that quicksort can be adapted to this purpose avoiding many of the computations required to do a complete sort. ( Knuth(1998)The Art of Computer Programming Vol.3:Sorting and Searching, p.136 // Bentley (2011) Programming Pearls Column 11 )
In the normal partitioning process of quicksort, if partition position s=m, stop;
if s < m, use the same techinque to find (m-s)th position;
If s > m, find the mth smallest element in the left hand. 

Searching a sorted 2D array


A 2D Array is sorted on its row and columns, find a key.


"""
Program to search an element in a 2-d array
The 2D array has sorted rows and sorted columns
"""
from random import randrange

N=10 # we will generate a NxN array

# initializes a 2-d array sorted on rows and columns
ARRAY = [ [i for i in range(j,N+j)] for j in range(N) ]

KEY = randrange(0,ARRAY[N-1][N-1])

# We will skip the brute force method of O(n^2) 

# Attempt 1 : Use binary search
def binary_search(lst, l, u, key):
    if l > u : return -1;
    m = (l+u)/2
    if lst[m] == key: return m
    if lst[m] < key: return binary_search(lst, m+1,u, key)
    else : return binary_search(lst, l, m-1,key)


def binsearch_method():
    "Use binary search on each row : takes loglinear time: O( n log(n) )"
    for i in range(N):
        idx = binary_search(ARRAY[i],0,len(ARRAY[i])-1,KEY)
        if idx != -1:
            print("found %d at %d,%d" % (KEY, i,idx))
            return

def linear_method():
    "search in linear time"
    currow = 0
    curcol = N-1
    steps = 0
    while curcol > 0 and currow < N:
        steps += 1
        #print(currow, curcol)
        # If the elem in a col is greater than key, we can skip the entire col
        if ARRAY[currow][curcol] > KEY: curcol -= 1 
        # If the first element in a row is > than key or if the last elem is < key, we skip the entire row.
        if ARRAY[currow][0] > KEY or ARRAY[currow][curcol] < KEY: currow += 1
        if ARRAY[currow][curcol] == KEY:
            print("found %d at %d,%d in %d steps" % (KEY, currow,curcol, steps) )
            return

if __name__ == "__main__":
    print("Key is %d" % KEY )
    binsearch_method()
    linear_method()