algorithm - Loop invariant when first iteration starts -


i'm taking elementary course in data structures & algorithms, book use seminal work clrs. have trouble understanding loop invariant explained in chapter 2.1: insertion sort.

the book says that:

at start of each iteration of loop of lines 1-8, subarry a[1..j -1] consists of elements in a[1..j-1], in sorted order.

now, puzzles me. why hold when first iteration starts? array sorted looks { 5, 2, 4, 6, 1, 3 }. when first iteration of loop starts a[1.. j-1] isn't in sorted order, when iteration ends though.

what missing here?

a[1.. j-1] isn't in sorted order, when iteration ends though.

assuming value of j starts @ 2 initially, a[1.. j-1] contain array of length 1, definition sorted.


Comments

Post a Comment

Popular posts from this blog

jquery - Invalid Assignment Left-Hand Side -

i trying assign class tag via jquery, resulting in error through firebug says "invalid assignment left-hand side" on fourth line below. <cfoutput> $('.pngfix a').each(function(index) { var hreflink = $(this).attr("href"); if (hreflink.tolowercase() = '../audio.cfm') { $(this).addclass('audioimg'); } }); </cfoutput> looking around online, looks syntax problem, don't seem see it... any tips? thanks if (hreflink.tolowercase() = '../audio.cfm') that attempts assign value, rather check equality. change = operator == .
Read more

javascript - Preserving URL fragment through CAS sign-on -

i maintain single-page application uses yui 2.8 history module retain local options in url fragment. i've put behind cas authentication, , i'm finding fragment gets lost during cas authentication. retained in signon url, not when redirected application page. true after session timeouts, users bumped default options after re-authentication. any suggested strategies hanging on fragment (or underlying javascript state) though cas roundtrip? you can store in cookie, sessionstorage , or value of window.name if there no security implications: //cookie document.cookie = "fragid=" + window.location.hash + ";path=/"; //session storage window.sessionstorage.setitem("fragid",window.location.hash); //window window.name = window.location.hash references url fragments , redirects – ieinternals
Read more

asp.net mvc - Implementing normal user/pass, Twitter & Facebook auth -

i have created public facing website allows login using username/password, or twitter, or facebook. when logging in twitter first time (for example), user created in database nickname matching twitter screen name. want nickname always unique. the problem in cases user nickname exists, user can't added. unsure accepted approach problem, solution can see far ask user override nickname, doesn't seem elegant. the reason nickname needs unique not code issue, interface issue, example there forums , want each user uniquely identified nickname. are there other methods can suggest dealing problem? edit: @ request of of replies clarify example: lets have user named joe bloggs member on website. not member of twitter or facebook. nickname on site joebloggs. then, joe bloggs comes along, , wants sign in twitter account. twitter name joebloggs, when signs in twitter, system attempts automatically set nickname joebloggs. however, nickname exists. normal or best practice ...
Read more