afl2_skitse2.tex

\section{b}
Vi ser at i og j initialiseres som positioner udenfor arrayret A[p..r] -hhv. som p-1 og r+1.
Grundet repeat-until konstruktionen vil de dog blive in/dekrementeret inden der laves opslag i A.

Første iteration:

Første indre løkke (linje 5-7):
Vi ser at j dekrementeres ved indgangen til den første indre løkke. j ligger nu indenfor arrayet A[p..r]. 
Såfremt A[j] <= x stopper den indre løkke (linje 7), ellers fortsætter vi med at at dekrementere j.
vi ved at j aldrig bliver mindre end p, da A[p] = x. Den indre løkke vil altså altid stoppe med p >= j <= r samt A[j] <= x.
Derudover ved vi at der ikke kan være nogen elementer i A[j+1..r] der er mindre/lig med x.
 
Anden indre løkke (linje 8-10):
Ved indgangen til den anden indre løkke inkrementeres i, så i=p og da A[i] = A[p] = x vil den indre løkke stoppe her.

Efter de to indre løkker sammenlignes i og j.
Enten har j bevæget sig hele vejen ned igennem arrayet så j=i=p hvorefter vi ved at alle elementer er større end x. Der skal derfor ikke gøres mere da x er det mindste element og ligger forrest. Her vil funktionen terminere.

Hvis j nu er forskellig fra i må j nødvendigvis være større end i (j kan på nuværende tidspunkt ikke være mindre end i da A[i] = x).
Vi ved så at A[i] = x og at A[j] <= x. Derfor vil A[i] og A[j] blive ombyttet.
Efter første iteration gælder derfor at A[i] er et element der er mindre eller lig med x samt at A[j] = x. Derudover ved vi at alle elementer i A[j+1 .. r] er større end x.
Mere generelt kan vi sige at alle elementer i A[p..i] er mindre eller lig x samt at alle elementer i A[j .. r] er større eller lig med x.
Vi kan konkludere at vi på intet tidspunkt i første iteration tilgår et element der ikke findes i A[p..r].


Efterfølgene iterationer:
Vi ved nu at der i intervallet A[p..i] kun eksiterer elementer der er mindre/lig x samt at der i intervallet A[j..r] kun eksisterer elementer der er større/lig x
i hver iteration opretholder vi denne orden samtidig med at vi dekrementerer j og inkrementerer i.


Afslutning:
På et tidspunkt vil j og i bevæge sig forbi hinanden eller lande på samme element. 
Vi ved at A[p..i] indeholder mindst et element, samt at elementerne er mindre/lig x. Derfor vil den første indre løkke stoppe hvis j <= i da A[j] så vil være <= x

Tilsvarende ved vi at A[j..r] indeholder mindst et element samt at elementerne er større/lig x. Derfor vil den anden indre løkke stoppe hvis i >= j da A[i] så vil være >= x

Når j og i krydser ved vi altså at de vil stoppe og da i ikke er mindre end j stopper den ydre løkke og funktionen termiererer. 



\section{c}
Dette skyldes at den første indre løkke altid vil blive kørt mindst to gange: Ved første iteration bliver j sat til r. \section{b}
Vi ser at i og j initialiseres som positioner udenfor arrayret A[p..r] -hhv. som p-1 og r+1.
Grundet repeat-until konstruktionen vil de dog blive in/dekrementeret inden der laves opslag i A.

Første iteration:

Første indre løkke (linje 5-7):
Vi ser at j dekrementeres ved indgangen til den første indre løkke. j ligger nu indenfor arrayet A[p..r]. 
Såfremt A[j] <= x stopper den indre løkke (linje 7), ellers fortsætter vi med at at dekrementere j.
vi ved at j aldrig bliver mindre end p, da A[p] = x. Den indre løkke vil altså altid stoppe med p >= j <= r samt A[j] <= x.
Derudover ved vi at der ikke kan være nogen elementer i A[j+1..r] der er mindre/lig med x.
 
Anden indre løkke (linje 8-10):
Ved indgangen til den anden indre løkke inkrementeres i, så i=p og da A[i] = A[p] = x vil den indre løkke stoppe her.

Efter de to indre løkker sammenlignes i og j.
Enten har j bevæget sig hele vejen ned igennem arrayet så j=i=p hvorefter vi ved at alle elementer er større end x. Der skal derfor ikke gøres mere da x er det mindste element og ligger forrest. Her vil funktionen terminere.

Hvis j nu er forskellig fra i må j nødvendigvis være større end i (j kan på nuværende tidspunkt ikke være mindre end i da A[i] = x).
Vi ved så at A[i] = x og at A[j] <= x. Derfor vil A[i] og A[j] blive ombyttet.
Efter første iteration gælder derfor at A[i] er et element der er mindre eller lig med x samt at A[j] = x. Derudover ved vi at alle elementer i A[j+1 .. r] er større end x.
Mere generelt kan vi sige at alle elementer i A[p..i] er mindre eller lig x samt at alle elementer i A[j .. r] er større eller lig med x.
Vi kan konkludere at vi på intet tidspunkt i første iteration tilgår et element der ikke findes i A[p..r].


Efterfølgene iterationer:
Vi ved nu at der i intervallet A[p..i] kun eksiterer elementer der er mindre/lig x samt at der i intervallet A[j..r] kun eksisterer elementer der er større/lig x
i hver iteration opretholder vi denne orden samtidig med at vi dekrementerer j og inkrementerer i.


Afslutning:
På et tidspunkt vil j og i bevæge sig forbi hinanden eller lande på samme element. 
Vi ved at A[p..i] indeholder mindst et element, samt at elementerne er mindre/lig x. Derfor vil den første indre løkke stoppe hvis j <= i da A[j] så vil være <= x

Tilsvarende ved vi at A[j..r] indeholder mindst et element samt at elementerne er større/lig x. Derfor vil den anden indre løkke stoppe hvis i >= j da A[i] så vil være >= x

Når j og i krydser ved vi altså at de vil stoppe og da i ikke er mindre end j stopper den ydre løkke og funktionen termiererer. 



\section{c}
Dette skyldes at den første indre løkke altid vil blive kørt mindst to gange: Ved første iteration bliver j sat til r. 




Der kan ske en af to ting, enten vil j være forskelig fra i hvorved der vil ske en ombytning




I første trin:
elementet mindre=, så skal der byttes, j != i
Der udføres en ekstra it. hvorved j < r

eller
j møder et element der er større så fortsætter j mod p og er <r




Dernæst skal vi vise
j <p
og at j kan ende i p (=)









\section{b}
Vi ser at i og j initialiseres som positioner udenfor arrayret A[p..r] -hhv. som p-1 og r+1.
Grundet repeat-until konstruktionen vil de dog blive in/dekrementeret inden der laves opslag i A.

Første iteration:

Første indre løkke (linje 5-7):
Vi ser at j dekrementeres ved indgangen til den første indre løkke. j ligger nu indenfor arrayet A[p..r]. 
Såfremt A[j] <= x stopper den indre løkke (linje 7), ellers fortsætter vi med at at dekrementere j.
vi ved at j aldrig bliver mindre end p, da A[p] = x. Den indre løkke vil altså altid stoppe med p >= j <= r samt A[j] <= x.
Derudover ved vi at der ikke kan være nogen elementer i A[j+1..r] der er mindre/lig med x.
 
Anden indre løkke (linje 8-10):
Ved indgangen til den anden indre løkke inkrementeres i, så i=p og da A[i] = A[p] = x vil den indre løkke stoppe her.

Efter de to indre løkker sammenlignes i og j.
Enten har j bevæget sig hele vejen ned igennem arrayet så j=i=p hvorefter vi ved at alle elementer er større end x. Der skal derfor ikke gøres mere da x er det mindste element og ligger forrest. Her vil funktionen terminere.

Hvis j nu er forskellig fra i må j nødvendigvis være større end i (j kan på nuværende tidspunkt ikke være mindre end i da A[i] = x).
Vi ved så at A[i] = x og at A[j] <= x. Derfor vil A[i] og A[j] blive ombyttet.
Efter første iteration gælder derfor at A[i] er et element der er mindre eller lig med x samt at A[j] = x. Derudover ved vi at alle elementer i A[j+1 .. r] er større end x.
Mere generelt kan vi sige at alle elementer i A[p..i] er mindre eller lig x samt at alle elementer i A[j .. r] er større eller lig med x.
Vi kan konkludere at vi på intet tidspunkt i første iteration tilgår et element der ikke findes i A[p..r].


Efterfølgene iterationer:
Vi ved nu at der i intervallet A[p..i] kun eksiterer elementer der er mindre/lig x samt at der i intervallet A[j..r] kun eksisterer elementer der er større/lig x
i hver iteration opretholder vi denne orden samtidig med at vi dekrementerer j og inkrementerer i.


Afslutning:
På et tidspunkt vil j og i bevæge sig forbi hinanden eller lande på samme element. 
Vi ved at A[p..i] indeholder mindst et element, samt at elementerne er mindre/lig x. Derfor vil den første indre løkke stoppe hvis j <= i da A[j] så vil være <= x

Tilsvarende ved vi at A[j..r] indeholder mindst et element samt at elementerne er større/lig x. Derfor vil den anden indre løkke stoppe hvis i >= j da A[i] så vil være >= x

Når j og i krydser ved vi altså at de vil stoppe og da i ikke er mindre end j stopper den ydre løkke og funktionen termiererer. 



\section{c}
Dette skyldes at den første indre løkke altid vil blive kørt mindst to gange: Ved første iteration bliver j sat til r. 




Der kan ske en af to ting, enten vil j være forskelig fra i hvorved der vil ske en ombytning




I første trin:
elementet mindre=, så skal der byttes, j != i
Der udføres en ekstra it. hvorved j < r

eller
j møder et element der er større så fortsætter j mod p og er <r




Dernæst skal vi vise
j <p
og at j kan ende i p (=)









\section{b}
Vi ser at i og j initialiseres som positioner udenfor arrayret A[p..r] -hhv. som p-1 og r+1.
Grundet repeat-until konstruktionen vil de dog blive in/dekrementeret inden der laves opslag i A.

Første iteration:

Første indre løkke (linje 5-7):
Vi ser at j dekrementeres ved indgangen til den første indre løkke. j ligger nu indenfor arrayet A[p..r]. 
Såfremt A[j] <= x stopper den indre løkke (linje 7), ellers fortsætter vi med at at dekrementere j.
vi ved at j aldrig bliver mindre end p, da A[p] = x. Den indre løkke vil altså altid stoppe med p >= j <= r samt A[j] <= x.
Derudover ved vi at der ikke kan være nogen elementer i A[j+1..r] der er mindre/lig med x.
 
Anden indre løkke (linje 8-10):
Ved indgangen til den anden indre løkke inkrementeres i, så i=p og da A[i] = A[p] = x vil den indre løkke stoppe her.

Efter de to indre løkker sammenlignes i og j.
Enten har j bevæget sig hele vejen ned igennem arrayet så j=i=p hvorefter vi ved at alle elementer er større end x. Der skal derfor ikke gøres mere da x er det mindste element og ligger forrest. Her vil funktionen terminere.

Hvis j nu er forskellig fra i må j nødvendigvis være større end i (j kan på nuværende tidspunkt ikke være mindre end i da A[i] = x).
Vi ved så at A[i] = x og at A[j] <= x. Derfor vil A[i] og A[j] blive ombyttet.
Efter første iteration gælder derfor at A[i] er et element der er mindre eller lig med x samt at A[j] = x. Derudover ved vi at alle elementer i A[j+1 .. r] er større end x.
Mere generelt kan vi sige at alle elementer i A[p..i] er mindre eller lig x samt at alle elementer i A[j .. r] er større eller lig med x.
Vi kan konkludere at vi på intet tidspunkt i første iteration tilgår et element der ikke findes i A[p..r].


Efterfølgene iterationer:
Vi ved nu at der i intervallet A[p..i] kun eksiterer elementer der er mindre/lig x samt at der i intervallet A[j..r] kun eksisterer elementer der er større/lig x
i hver iteration opretholder vi denne orden samtidig med at vi dekrementerer j og inkrementerer i.


Afslutning:
På et tidspunkt vil j og i bevæge sig forbi hinanden eller lande på samme element. 
Vi ved at A[p..i] indeholder mindst et element, samt at elementerne er mindre/lig x. Derfor vil den første indre løkke stoppe hvis j <= i da A[j] så vil være <= x

Tilsvarende ved vi at A[j..r] indeholder mindst et element samt at elementerne er større/lig x. Derfor vil den anden indre løkke stoppe hvis i >= j da A[i] så vil være >= x

Når j og i krydser ved vi altså at de vil stoppe og da i ikke er mindre end j stopper den ydre løkke og funktionen termiererer. 



\section{c}
Dette skyldes at den første indre løkke altid vil blive kørt mindst to gange: Ved første iteration bliver j sat til r. 




Der kan ske en af to ting, enten vil j være forskelig fra i hvorved der vil ske en ombytning




I første trin:
elementet mindre=, så skal der byttes, j != i
Der udføres en ekstra it. hvorved j < r

eller
j møder et element der er større så fortsætter j mod p og er <r




Dernæst skal vi vise
j <p
og at j kan ende i p (=)









\section{b}
Vi ser at i og j initialiseres som positioner udenfor arrayret A[p..r] -hhv. som p-1 og r+1.
Grundet repeat-until konstruktionen vil de dog blive in/dekrementeret inden der laves opslag i A.

Første iteration:

Første indre løkke (linje 5-7):
Vi ser at j dekrementeres ved indgangen til den første indre løkke. j ligger nu indenfor arrayet A[p..r]. 
Såfremt A[j] <= x stopper den indre løkke (linje 7), ellers fortsætter vi med at at dekrementere j.
vi ved at j aldrig bliver mindre end p, da A[p] = x. Den indre løkke vil altså altid stoppe med p >= j <= r samt A[j] <= x.
Derudover ved vi at der ikke kan være nogen elementer i A[j+1..r] der er mindre/lig med x.
 
Anden indre løkke (linje 8-10):
Ved indgangen til den anden indre løkke inkrementeres i, så i=p og da A[i] = A[p] = x vil den indre løkke stoppe her.

Efter de to indre løkker sammenlignes i og j.
Enten har j bevæget sig hele vejen ned igennem arrayet så j=i=p hvorefter vi ved at alle elementer er større end x. Der skal derfor ikke gøres mere da x er det mindste element og ligger forrest. Her vil funktionen terminere.

Hvis j nu er forskellig fra i må j nødvendigvis være større end i (j kan på nuværende tidspunkt ikke være mindre end i da A[i] = x).
Vi ved så at A[i] = x og at A[j] <= x. Derfor vil A[i] og A[j] blive ombyttet.
Efter første iteration gælder derfor at A[i] er et element der er mindre eller lig med x samt at A[j] = x. Derudover ved vi at alle elementer i A[j+1 .. r] er større end x.
Mere generelt kan vi sige at alle elementer i A[p..i] er mindre eller lig x samt at alle elementer i A[j .. r] er større eller lig med x.
Vi kan konkludere at vi på intet tidspunkt i første iteration tilgår et element der ikke findes i A[p..r].


Efterfølgene iterationer:
Vi ved nu at der i intervallet A[p..i] kun eksiterer elementer der er mindre/lig x samt at der i intervallet A[j..r] kun eksisterer elementer der er større/lig x
i hver iteration opretholder vi denne orden samtidig med at vi dekrementerer j og inkrementerer i.


Afslutning:
På et tidspunkt vil j og i bevæge sig forbi hinanden eller lande på samme element. 
Vi ved at A[p..i] indeholder mindst et element, samt at elementerne er mindre/lig x. Derfor vil den første indre løkke stoppe hvis j <= i da A[j] så vil være <= x

Tilsvarende ved vi at A[j..r] indeholder mindst et element samt at elementerne er større/lig x. Derfor vil den anden indre løkke stoppe hvis i >= j da A[i] så vil være >= x

Når j og i krydser ved vi altså at de vil stoppe og da i ikke er mindre end j stopper den ydre løkke og funktionen termiererer. 



\section{c}
Dette skyldes at den første indre løkke altid vil blive kørt mindst to gange: Ved første iteration bliver j sat til r. 




Der kan ske en af to ting, enten vil j være forskelig fra i hvorved der vil ske en ombytning




I første trin:
elementet mindre=, så skal der byttes, j != i
Der udføres en ekstra it. hvorved j < r

eller
j møder et element der er større så fortsætter j mod p og er <r




Dernæst skal vi vise
j <p
og at j kan ende i p (=)









\section{b}
Vi ser at i og j initialiseres som positioner udenfor arrayret A[p..r] -hhv. som p-1 og r+1.
Grundet repeat-until konstruktionen vil de dog blive in/dekrementeret inden der laves opslag i A.

Første iteration:

Første indre løkke (linje 5-7):
Vi ser at j dekrementeres ved indgangen til den første indre løkke. j ligger nu indenfor arrayet A[p..r]. 
Såfremt A[j] <= x stopper den indre løkke (linje 7), ellers fortsætter vi med at at dekrementere j.
vi ved at j aldrig bliver mindre end p, da A[p] = x. Den indre løkke vil altså altid stoppe med p >= j <= r samt A[j] <= x.
Derudover ved vi at der ikke kan være nogen elementer i A[j+1..r] der er mindre/lig med x.
 
Anden indre løkke (linje 8-10):
Ved indgangen til den anden indre løkke inkrementeres i, så i=p og da A[i] = A[p] = x vil den indre løkke stoppe her.

Efter de to indre løkker sammenlignes i og j.
Enten har j bevæget sig hele vejen ned igennem arrayet så j=i=p hvorefter vi ved at alle elementer er større end x. Der skal derfor ikke gøres mere da x er det mindste element og ligger forrest. Her vil funktionen terminere.

Hvis j nu er forskellig fra i må j nødvendigvis være større end i (j kan på nuværende tidspunkt ikke være mindre end i da A[i] = x).
Vi ved så at A[i] = x og at A[j] <= x. Derfor vil A[i] og A[j] blive ombyttet.
Efter første iteration gælder derfor at A[i] er et element der er mindre eller lig med x samt at A[j] = x. Derudover ved vi at alle elementer i A[j+1 .. r] er større end x.
Mere generelt kan vi sige at alle elementer i A[p..i] er mindre eller lig x samt at alle elementer i A[j .. r] er større eller lig med x.
Vi kan konkludere at vi på intet tidspunkt i første iteration tilgår et element der ikke findes i A[p..r].


Efterfølgene iterationer:
Vi ved nu at der i intervallet A[p..i] kun eksiterer elementer der er mindre/lig x samt at der i intervallet A[j..r] kun eksisterer elementer der er større/lig x
i hver iteration opretholder vi denne orden samtidig med at vi dekrementerer j og inkrementerer i.


Afslutning:
På et tidspunkt vil j og i bevæge sig forbi hinanden eller lande på samme element. 
Vi ved at A[p..i] indeholder mindst et element, samt at elementerne er mindre/lig x. Derfor vil den første indre løkke stoppe hvis j <= i da A[j] så vil være <= x

Tilsvarende ved vi at A[j..r] indeholder mindst et element samt at elementerne er større/lig x. Derfor vil den anden indre løkke stoppe hvis i >= j da A[i] så vil være >= x

Når j og i krydser ved vi altså at de vil stoppe og da i ikke er mindre end j stopper den ydre løkke og funktionen termiererer. 



\section{c}
Dette skyldes at den første indre løkke altid vil blive kørt mindst to gange: Ved første iteration bliver j sat til r. 




Der kan ske en af to ting, enten vil j være forskelig fra i hvorved der vil ske en ombytning




I første trin:
elementet mindre=, så skal der byttes, j != i
Der udføres en ekstra it. hvorved j < r

eller
j møder et element der er større så fortsætter j mod p og er <r




Dernæst skal vi vise
j <p
og at j kan ende i p (=)









\section{b}
Vi ser at i og j initialiseres som positioner udenfor arrayret A[p..r] -hhv. som p-1 og r+1.
Grundet repeat-until konstruktionen vil de dog blive in/dekrementeret inden der laves opslag i A.

Første iteration:

Første indre løkke (linje 5-7):
Vi ser at j dekrementeres ved indgangen til den første indre løkke. j ligger nu indenfor arrayet A[p..r]. 
Såfremt A[j] <= x stopper den indre løkke (linje 7), ellers fortsætter vi med at at dekrementere j.
Vi ved at j aldrig bliver mindre end p, da A[p] = x. Den indre løkke vil altså altid stoppe med p >= j <= r samt A[j] <= x.
Derudover ved vi at der ikke kan være nogen elementer i A[j+1..r] der er mindre/lig med x.
 
Anden indre løkke (linje 8-10):
Ved indgangen til den anden indre løkke inkrementeres i, så i=p og da A[i] = A[p] = x vil den indre løkke stoppe her.

Efter de to indre løkker sammenlignes i og j.
Enten har j bevæget sig hele vejen ned igennem arrayet så j=i=p hvorefter vi ved at alle elementer er større end x. Der skal derfor ikke gøres mere da x er det mindste element og ligger forrest. Her vil funktionen terminere.

Hvis j nu er forskellig fra i må j nødvendigvis være større end i (j kan på nuværende tidspunkt ikke være mindre end i da A[i] = x).
Vi ved så at A[i] = x og at A[j] <= x. Derfor vil A[i] og A[j] blive ombyttet.
Efter første iteration gælder derfor at A[i] er et element der er mindre eller lig med x samt at A[j] = x. Derudover ved vi at alle elementer i A[j+1 .. r] er større end x.
Mere generelt kan vi sige at alle elementer i A[p..i] er mindre eller lig x samt at alle elementer i A[j .. r] er større eller lig med x.
Vi kan konkludere at vi på intet tidspunkt i første iteration tilgår et element der ikke findes i A[p..r].

Efterfølgene iterationer:
Vi ved nu at der i intervallet A[p..i] kun eksisterer elementer der er mindre/lig x samt at der i intervallet A[j..r] kun eksisterer elementer der er større/lig x. I hver iteration opretholder vi denne orden samtidig med at vi dekrementerer j og inkrementerer i.


Afslutning:
På et tidspunkt vil j og i bevæge sig forbi hinanden eller lande på samme element. 
Vi ved at A[p..i] indeholder mindst et element, samt at elementerne er mindre/lig x. Derfor vil den første indre løkke stoppe hvis j <= i da A[j] så vil være <= x

Tilsvarende ved vi at A[j..r] indeholder mindst et element samt at elementerne er større/lig x. Derfor vil den anden indre løkke stoppe hvis i >= j da A[i] så vil være >= x

Når j og i krydser ved vi altså at de vil stoppe og da i ikke er mindre end j stopper den ydre løkke og funktionen terminerer. 


\section{c}
Den første indre løkke vil altid blive kørt mindst to gange: Ved første iteration bliver j sat til r. Hvis j er større end x vil j fortsætte i mod p, og j er derfor mindre end r. Hvis j er mindre eller lig med x, vil j blive ombyttet med i, og i næste iteration vil j blive skubbet så at j er mindre end r. 
 Således ved vi at j altid vil være mindre end r når funktionen terminerer. Dette ved vi fordi der herefter kan ske én af to ting: enten enten vil j møde et element der er mindre end eller lig med x hvorved der vil ske en ombytning. Ellers vil j møde et element der er større end x, i hvilket tilfælde j fortsætter mod p og er mindre end r. 

I de følgende iterationer bevæger j sig nedad imod p. Såfremt j møder et element der er mindre end eller lig med x vil j blive swappet, så j vil aldrig blive mindre end p, eftersom A[p] = x. j kan dog blive lig x i den situation hvor p er den største værdi i arrayet (jvf. argumentationen i sektion b). Ud fra dette kan vi konkludere at når funktionen terminerer vil den returnere en værdi som overholder ordenen p <= j < r.