Tuesday, January 20, 2009

Bill Gates ' paper on sort

Bill Gates published one academic paper on sort. You are given an array A of unsorted integers and the only allowed operation is to "flip" a sub-array. A flip(i) is an operation which reverses all the sub-array starting in position A[i]. Namely,

(A[1], .... A[i-1], A[i], A[i+1] ...., A[n-1], A[n])

is changed into

(A[1], .... A[i-1], A[n], A[n-1] ...., A[i+1], A[i])

Can you suggest a sorting algorithm based just on flip() operations?

PS: this sorting method has an impact on genetic studies and evolution of species.

PS: the paper is W. Gates and C. Papadimitriou, Bounds for sorting by prefix reversal (1976)

No comments:

Post a Comment