Thuật toán này quét chuỗi n-1 lần, ở đâu, trong mỗi lần scan, thuật toán so sánh các yếu tố hiện tại với một trong những tiếp theo và hoán đổi chúng nếu họ ra khỏi trật tự. Đưa ra một mô tả pseudo-code loại bong bóng là hiệu quả như có thể giả sử S là thực hiện với một danh sách liên kết kép. | methods of the array list ADT on such a representation. Is it better to store the entries in L by increasing indices or not There is a simple but inefficient algorithm called bubble-sort 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 Answer Exercise assuming S is implemented with an array list. A useful operation in databases is the natural join. If we view a database as a list of ordered pairs of objects then the natural join of databases A and B is the list of all ordered triples x y z such that the pair x y is in A and the pair y z is in B. Describe and analyze an efficient algorithm for computing the natural join of a list A of n pairs and a list B of m pairs. When Bob wants to send Alice a message M on the Internet he breaks M into n data packets numbers the packets consecutively and injects them into the network. When the packets arrive at Alice s computer they may be out of order so Alice must assemble the sequence of n packets in order before she can be sure she has the entire message. Describe an efficient scheme for Alice to do this. What is the running time of this algorithm Given a list L of n positive integers each represented with k logn 1 bits describe an ơ n -time method for finding a k-bit integer not in L. Argue why any solution to the previous problem must run in Q n time. Given a list L of n arbitrary integers design an ơ n -time method for finding an integer that cannot be formed as the sum of two integers in L. 370 Isabel has an interesting way of summing up the values in an array A of n integers where n is a power of two. She creates an array
