There is a simple algorithm, called bubble-sort, for sorting

Authors:

Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

Chapter:

List And Iterator Adts

Exercise:

Exercises

Question:51 | ISBN:9781118771334 | Edition: 6

Question

There is a simple algorithm, called bubble-sort, for sorting a list L of n comparable elements. This algorithm scans the list 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 pseudocode description of bubble-sort that is as efficient as possible assuming L is implemented with a doubly linked list. What is the running time of this algorithm?