Question

Records R1, R2, R3,.. RN  with keys K1, K2, K3,.. KN   are said to be h-ordered, if ________

(a) Ki <= Ki+h  for 1<= i*h <= N

(b) Kh <= Ki+h  for 1<= i <= N

(c) Ki <= Kh  for 1<= i <= h

(d) Ki <= Ki+h  for 1<= i <= N-h

I had been asked this question during an online exam.

Query is from Shell sort in section Sorting of Data Structures & Algorithms II

Answer 1

Correct option is (d) Ki <= Ki+h  for 1<= i <= N-h

Best explanation: Records are h-ordered  if every hth element (starting anywhere) yields a sorted array. Therefore, given records with keys K1, K2, K3,.. KN   are said to be h-ordered, if Ki <= Ki+h  for 1<= i <= N-h.