Non Deterministic Sorting Algorithm

• Non Deterministic Sorting Algorithm produces different outputs on every execution. They work in a probabilistic way. The output of the algorithm depends on the sequence of random numbers generated.
• Consider A and B are input and output arrays of size n, respectively. The non-deterministic sorting approach selects any random number j between 1 to n and inserts the first element of array A on location j in array B.
• The process is repeated a maximum of n times. If location B[j] is already occupied then the algorithm fails. Otherwise, the selection of the next position continues. In this way, all elements of input array A are placed in output array B.
• After putting all elements in B, the algorithm enters in verification stage. In verification, two adjacent elements are compared in output array B. If any pair of adjacent elements are out of order, it implies array B is not properly sorted and the algorithm fails.
• In the below example (left), the size of the array is 6. We generated a random number between 1 to 6, six times. Assume that the sequence of generated random numbers is <2, 6, 1, 5, 3, 4>. Elements from the input array are rearranged based on those index values.
• A[1] < A[2], A[2] < A[3], but A[3] > A[4], implies that the array is not sorted and the algorithm will return fail.
• On the right side, the generated random index sequence is <2, 6, 1, 3, 4, 5>. Elements from the input array are rearranged. For each element A[I] < A[I + 1], implies this array is sorted and the algorithm returns true.
• Thus, the success of the algorithm purely depends on generated index sequence

Non Deterministic Sorting Algorithm

A non-deterministic algorithm for sorting data is described here :

Algorithm  NON_DET_SORT(A, B)
// Description : Sort array A non-deterministically and store in array B
// Input : Array A and B of size n, representing input and output array respectively.
// Output : Success / Failure

// Guessing stage
for i ← 1 to n do
   B[i] ← 0
end

for i ← 1 to n do
   j ← select(1…n)
   if B[j] ≠ 0 then
      fail()
   end
   B[j] ← A[i]
end

// Verification stage
for  i ← 1  to n – 1 do
   if B[i + 1] < B[i] then
      fail()
   end
end
B[1…n]
success()

• The output of the algorithm is acceptable when all n guesses are true. If we run this algorithm multiple times, each time we may get different outputs.
• The running time of this algorithm is a function of a correct guess. Hence, the non-deterministic algorithm runs in O(f(n)) time, where n is the size of the input.

---

Youtube Channel: https://shorturl.at/inryW