Problem
There is a simple, but inefficient, algorithm, called bubblesort, for sorting a sequence S of n comparable elements. This algorithm scans the sequence n-1 times, where, in each scan, the algorithm compares the current element with the next one and swaps them if they are out of order. Give a pseudo-code description of bubble-sort that is as efficient as possible assuming S is implemented with a doubly linked list. What is the running time of this algorithm?