改进最坏情况下的运行插入的时间排序使用二进制搜索 [英] Improving worst-case running time of insertion sort using binary search

问题描述

while循环使用线性搜索扫描倒退。但是，我们知道，while循环中的数组已经排序。所以我们可以替换折半查找替换，这样为O（n）将变为O（LG N）的线性搜索。但是，我采取的是，它不会有助于减少整体的时间，因为我们仍然要移动的元素一个索引前锋将始终以倍（向后步（n）的数字）。所以，总体来说，运行时间保持为O（n ^ 2），并没有办法实现为O（n LG N），对于这种情况。请告诉我，如果我在一个错误的方式接近这一点。

 插入排序（A）

 对于j = 2的长度[A]
  做到关键= A [J]。
     I =的J  -  1

  而I＆GT; 0和A [1]≥键
    A [1 + 1] = A [1]
    I = I  -  1

  A [I + 1] =键
 

解决方案

插入排序推动数组中的元素，以腾出空间来排队的下一个元素。
所以如果你发现在那里使用二进制搜索，输入新的元素，你仍然需要推动该指数一步向前（右）之后的所有元素。
所以给一个数组排序倒退：10,9,8,7,6,5,4,3,2,1
你需要做的i-1推到右侧，以便插入第i个元素（即使你使用二进制搜索） - 最坏情况下的时间：为O（n ^ 2）
如果你能插入的元素，一个接一个，到一个列表，你就不必推元素，但你将不得不支付在列表中选择搜索合适的位置（所以在这个实施WCT是O （N ^ 2））。

一个解决这个问题将与某种列表和数组之间的协同作用，以便可以达到在O（1）时间第i个元素（如在阵列），可以推一个新元素给定的位置（说，在O（1）时间索引j）后（如表） - 如果你成功了，我相信你会赢得永恒的荣耀

The while loop uses linear search to scan backwards. However, we know that the array within the while loop is already sorted. So we can replace the linear search with binary search instead so that O(n) will change to O(lg n). However, my take on this is that it won't contribute to reducing the overall time because we would still have to move the elements one index forward which will always take (number of backward steps(n)) times. So overall, the running time stays O(n^2) and there is no way to achieve O(n lg n) for this case. Please tell me if I am approaching this in a wrong way.

INSERTION-SORT(A)

 for j = 2 to length[A]
  do key = A[j]
     i = j - 1

  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1

  A[i+1] = key

解决方案

insertion sort pushes the elements of the array in order to free a space to the next element in line.
so if you find where to enter the new element using binary search, you will still need to push all the elements after that index one step forward (to the right).
so given an array sorted backwards: 10,9,8,7,6,5,4,3,2,1
you will need to make i-1 pushes to the right in order to insert the i'th element (even if you use binary search) - worst case time: O(n^2)
if you could insert the elements, one by one, to a list you wouldn't have to push the elements, but you will have to "pay" for the search of the proper location in the list (so in this implementation W.C.T is O(n^2)).

a solution to this problem will be with some kind of synergy between lists and arrays so you could reach the i'th element in O(1) time (as in arrays) and could push a new element to a given location (say after the index j) in O(1) time (as in lists) - if you succeed, I believe you will win eternal glory!

这篇关于改进最坏情况下的运行插入的时间排序使用二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！