arrays - insertion sort theoretical analysis, total number of shifts. -


given following array:

[14 17 21 34 47 19 71 22 29 41 8]

and following excerpt book algorithms unlocked thomas cormen (slightly edited, [start] , [stop] flags not part of text):

insertion sort excellent choice when array starts out ''almost sorted''. [start] suppose each array element starts out within k positions of ends in sorted array. total number of times given element shifted on iterations of inner loop @ k. therefore, total number of times elements shifted on inner-loop iterations, @ kn, in turn tells total number of inner-loop iterations @ kn (since each inner-loop iteration shifts 1 element 1 position).[stop] if k constant, total running time of insertion sort Θ(n), because Θ-notation subsumes constant factor k. in fact can tolerate elements moving long distance in array, long there not many such elements. in particular, if l elements can move anywhere in array (so each of these elements can move n-1 positions), , remaining n - l elements can more @ k positions, the total number of shifts is @ l * (n – 1) + (n – l) * k = (k + l) * n – (k + 1) * l, Θ(n) if both k , l constants.

the books trying explain how crafts formula, presents @ bottom of text. better understand says, likely, specific example using above sample array, going on k , n variables. can me better understand above excerpt's analysis?

to more specific confusing me, lines between [start] , [stop] flags ,these lines:

suppose each array element..... in turn tells total number of inner-loop iterations @ kn(since each inner-loop iteration shifts 1 element 1 position).

(anything below these lines totally understood way end.)

let consider insertion sort algorithm

algorithm: insertionsort(a)

i ← 1 while < length(a)     j ←     while j > 0 , a[j-1] > a[j]         swap a[j] , a[j-1]         j ← j - 1     end while     ← + 1 end while

the inner loop - move elements of a[0..i-1] 1 one, till a[i] in correct position. therefore if given element atmost k position away correct place, have maximum of k compares , swaps. n elements k*n.

hope helps!


Comments

Post a Comment

Popular posts from this blog

Is there a better way to structure post methods in Class Based Views -

i'm using class based views in django , never specify url in ajax calls , omit action parameter in form because know these requests go through post method of class based view. notice view - profile page make many requests depending on user updating on page - post method become convoluted , if/else mess example: def post(self, request, *args, **kwargs): # handle user changing available date if request.post.get('availabledate') != none: self.updateavailabledate(request) return jsonresponse({'result':'success'}) if request.post.get('newprojectname') != none: creative_user = creativeuserprofile.objects.get(id = request.user.id) project = project.create_project(creative_user, request.post['newprojectname']) project.save() return jsonresponse({'projectid': project.id }) if request.post.get('projectimage') != none , request.files['file']: proj...
Read more

performance - Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures? -

i'm doing micro-optimization on performance critical part of code , came across sequence of instructions (in at&t syntax): add %rax, %rbx mov %rdx, %rax mov %rbx, %rdx i thought had use case xchg allow me shave instruction , write: add %rbx, %rax xchg %rax, %rdx however, dimay found agner fog's instruction tables , xchg 3 micro-op instruction 2 cycle latency on sandy bridge, ivy bridge, broadwell, haswell , skylake. 3 whole micro-ops , 2 cycles of latency! 3 micro-ops throws off 4-1-1-1 cadence , 2 cycle latency makes worse original in best case since last 2 instructions in original might execute in parallel. now... cpu might breaking instruction micro-ops equivalent to: mov %rax, %tmp mov %rdx, %rax mov %tmp, %rdx where tmp anonymous internal register , suppose last 2 micro-ops run in parallel latency 2 cycles. given register renaming occurs on these micro-architectures, though, doesn't make sense me done way. why wouldn't register renamer ...
Read more

c# - Asp.net web api : redirect unauthorized requst to forbidden page -

im trying redirect unauthorized request forbidden page instead i'm getting forbidden page in response body , how can fix ? here's startup class : app.createperowincontext(storecontext.create); app.createperowincontext<applicationusermanager>(applicationusermanager.create); app.createperowincontext<applicationsigninmanager>(applicationsigninmanager.create); app.usecookieauthentication(new cookieauthenticationoptions { authenticationtype = defaultauthenticationtypes.applicationcookie, expiretimespan = timespan.fromdays(30), }); app.useexternalsignincookie(defaultauthenticationtypes.externalcookie); app.usetwofactorsignincookie(defaultauthenticationtypes.twofactorcookie, timespan.fromminutes(5)); app.usetwofactorrememberbrowsercookie(defaultauthenticationtypes.twofactorrememberbrowsercookie); the method im trying reach : [httpget] [authorize(roles = "admin")] public string getcurrentusername() { return userman...
Read more