performance - Why does the sorting algorithm work correctly? -


i got sorting algorithm. know have been written in many other , more simple ways that's not point of question.

here the algorithm:

sort(a : array of n, : n, j : n) assert j-i+1 istwopotency if a[i] > a[j] swap a[i] , a[j] if i+1 < j     k:= (j − + 1)/4     sort(a, i, j − 2k)     sort(a, j − 2k + 1, j)     sort(a, + k, j − k)     sort(a, i, j − 2k)     sort(a, j − 2k + 1, j)     sort(a, + k, j − k)

my question is, why algorithm work correctly in following case?

sort(a, 1, length(a))

and array be:

a[1 . . . length(a)]

length(a) 2 potency , can assume there no identical numbers inside array. tested it, got no errors assume works correctly. how can prove algorithm works correctly in these conditions?

and wondering how long algorithm needs running time. great if give me running time big theta notation (that's 1 understand best)

f(n) = Θ(g(n))

correctness

divide array 4 quarters, a1 through a4, , consider sub-array each element should end in.

  • after first 2 recursive calls, elements belong in a1 located in a1 or a3. a4 elements located in a2 or a4.

  • after third recursive call, a1 elements in a1 or a2, , a4 elements in a3 or a4.

  • after next 2 recursive calls, a1 elements in a1 in sorted order, , a4 elements in a4 in sorted order. leaves a2 , a3 elements in either a2 or a3.

  • after last recursive call a2 , a3 elements in correct sub-array in sorted order. array sorted.

illustration:

schematic illustration of above explanation

runtime

notice when execute algorithm on array of length n, have execute algorithm 6 times on arrays of length n/2. yields following recurrence:

  • t(1) = o(1).
  • t(n) = 6 t(n/2) + o(1).

solving recurrence t(n) = o(6^log2(n)) = o(n^log2(6)) ≈ o(n^2.585)


-

Comments

Post a Comment

Popular posts from this blog

PySide and Qt Properties: Connecting signals from Python to QML -

i trying run simple pyside appliccation design made in qml. call function in qml python in separated thread. i have following qml view: import qt 4.7 rectangle { visible: true width: 100; height: 100 color: "lightgrey" text { id: datestr objectname: "datestr" x: 10 y: 10 text: "init text" font.pixelsize: 12 function updatedata(text) { datestr.text = qstr(text) console.log("you said: " + text) } } } here application: some imports.... #!/usr/bin/python import sys import time pyside import qtdeclarative, qtcore pyside.qtgui import qapplication pyside.qtdeclarative import qdeclarativeview the qthread worker.... #worker thread class worker(qtcore.qthread): updateprogress = qtcore.signal(int) def __init__(self, child): qtcore.qthread.__init__(self) self.child = child def run(self):
Read more

c# - DevExpress.Wpf.Grid.InfiniteGridSizeException was unhandled -

Image
when using devexpress, see error: devexpress.wpf.grid.infinitegridsizeexception unhandled message="by default, infinite grid height not allowed since grid rows rendered , hence grid work slowly. fix issue, should place grid container give finite height grid, or should manually specify grid's height or maxheight. note can avoid exception setting gridcontrol.allowinfinitegridsize static property true, in case grid run slowly." the problem dxgrid has infinite height. to fix, set height non-infinite. snoop absolutely invaluable this: if "height" xaml element infinite (i.e. 0 or nan ), can set using one of following: option 1: height="{binding path=actualheight, relativesource={relativesource mode=findancestor, ancestortype=uielement}}" option 2: verticalalignment="stretch" option 3: height="auto" hint: use verticalalignment="stretch" if child of grid <rowdefinition height=
Read more

scala - 'wrong top statement declaration' when using slick in IntelliJ -

Image
i'm porting project scala 2.9 2.10, therefore have use slick instead of scalaquery. i'm using slick 2.1.0 since supports ms access. according this tutorial , upgrade guide changed robs object class , added val robs : why error message wrong top statement declaration , how rid of it? edit: i'm new scala... according this question seems can't put val outside of methods or classes, right? code above directly in packge. right approach slick then? should move code in class or trait? according this changed val robs = tablequery[robs] to object robs extends tablequery(new robs(_)) {} . no warnings or errors anymore. :)
Read more