Consider a situation where your data is almost sorted—for example you are receiv
ID: 3887265 • Letter: C
Question
Consider a situation where your data is almost sorted—for example you are receiving time-stamped stock quotes and earlier quotes may arrive after later quotes because of differences in server loads and network traffic routes. Focus only on the time-stamps. To simplify this problem, assume that each time-stamp is an integer, all time-stamps are different, and for any two time-stamps, the earlier time-stamp corresponds to a smaller integer than the later time-stamp. The time-stamps arrive in a stream that is too large to be kept in memory completely. The time-stamps in the stream are not in their correct order, but you know that every time-stamp (integer) in the stream is at most hundred positions away from its correctly sorted position. Design an algorithm that outputs the time-stamps in the correct order. You can only a constant amount of storage, i.e., the memory used should be independent of the number of time-stamps processed. As a second requirement: your algorithm should use a linked list and NOT a heap
Explanation / Answer
he algorithm is as follows:
We have a set of numbers arranged in a linked list in an unsorted order. We need to sort them. One other information is that each number is 100 positions away from its sorted position.
1.Using the assunption that every item is 100 positions away, then we know the correct position of first 100 items.
2.items in the first set of 100 positions which are moving to the right(obvoiusly), there corrected position(100 positions need to be adjusted based on their
movements.
3.So in the first go we have 100 elements dorted, again the same approch can be applied for another 100 numbers with their updated adjustble positions.
4.This will be repeated till all the elements get sorted.