One of the oldest applications used on the Internet is FTP, the file transfer pr
ID: 3798956 • Letter: O
Question
One of the oldest applications used on the Internet is FTP, the file transfer protocol. The definition for this protocol traces its roots back to 1971, before the Internet even existed, and its formulation for the Internet was given in 1980. Its primary purpose is for transferring files from one computer to another over the Internet. Suppose you are writing an Internet file transfer application, similar to FTP, and it is your job to write the code that takes a raw sequence of network packets that were sent from one computer and reassembles that sequence to reconstitute the file at the receiving computer. The n packets in the input are numbered by their sequence numbers, which starts at some value, N, and goes incrementally in order to N + n 1. The packets are usually not received in this order, however. Thus, to reconstruct the file at the receiving computer, your method must re-order the packets so that they are sorted by their sequence numbers. In studying example inputs, you notice that the input sequence of packets is usually not that far from being sorted. That is, you notice in the examples you studied that each input packet is proximate to its output position, which means that if a packet is at position i in the input sequence, then its position in the sorted output sequence is somewhere in the range [i50, i+50]. Describe a method for sorting a sequence of n such packets by their sequence numbers in O(n) time, assuming that every input packet is proximate to its output position.
Explanation / Answer
The FTP packets are rearranged by sorting them. Generally they are passed as items with in queue. So for large data packet sort is best suitable. Packet sort is similar to insertion sort. It is stable and inplace algorithm which is very efficient in large lists. Algorithm sorts each element in every iteration.
for p = 1 to length(Arr)
temp = Arr[p]
q = p - 1
while q >= 0 and Arr[q] > temp
Arr[q+1] = Arr[q]
q = q - 1
end while
Arr[q+1] = temp[3]
end for
If n packets are there in queue, then it will take n iterations to sort since in every iteration one element is sorted and placed in perfect place.
So complecity will be O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.