a*******y
发帖数: 1040 | 1 There is an external array of integers on which you can perform the
following operations in O(1) time.
1. get(int i) - returns the value at the index 'i' in the external array.
2. reverse( int i, int j) - returns the reverse of the array between index
positions i and j (including i and j).
example for reverse: consider an array {1,2,3,4,5}. reverse(0,2) will return
{3,2,1,4,5} and reverse(1,4) will return {1,5,4,3,2}.
Write a code to sort the external array. Mention the time and space
complexity for your code. | g****y
发帖数: 240 | 2 insertion sort? 不过要N^2的复杂度
def reverse(alist, i, j):
if i >= j:
return alist
return alist[:i] + alist[i: j + 1][::-1] + alist[j + 1:]
def sort(alist):
for i in range(1, len(alist)):
for j in range(i - 1, -1, -1):
if alist[j + 1] < alist[j]:
alist = reverse(alist, j, j + 1)
else:
break
return alist | A********l
发帖数: 184 | 3 冒泡排序？ reverse(i, i+1) = swap(i, i+1)
return
【在 a*******y 的大作中提到】
: There is an external array of integers on which you can perform the
: following operations in O(1) time.
: 1. get(int i) - returns the value at the index 'i' in the external array.
: 2. reverse( int i, int j) - returns the reverse of the array between index
: positions i and j (including i and j).
: example for reverse: consider an array {1,2,3,4,5}. reverse(0,2) will return
: {3,2,1,4,5} and reverse(1,4) will return {1,5,4,3,2}.
: Write a code to sort the external array. Mention the time and space
: complexity for your code.
|
|
