Oppgave 1

I boblesortering, som i andre sorteringsmetoder, er det normalt en sammenligning som er den dominerende operasjonen. Her er det sammenligningen a[j - 1] > a[j] som utføres i innerste løkke. I første runde (når i = a.length) utføres den alltid n − 1 ganger. Neste gang alltid n − 2 ganger. Osv. Tilsammen n − 1 + n − 2 +  ·  ·   + 2 + 1 = n(n − 1)/2 ganger. Med andre ord er arbeidsmengden den samm i det beste tilfellet, i gjennomsnitt og i det verste tilfellet. Boblesortering er derfor av kvadratisk orden i alle de tre tilfellene.

Hvis sammenligningen a[j - 1] > a[j] er sann, blir det utført en ombytting. Vil antallet ombyttinger være det samme i alle de tre tilfellene? Vi ser fort at hvis tabellen er sortert stigende, skjer det ingen ombyttinger. Med andre ord 0 ombyttinger i det beste tilfellet. Det verste tilfellet er når tabellen er sortert avtagende. Da vil a[j - 1] > a[j] være sann hver gang og vi får en ombytting hver gang. Tilsammen n(n − 1)/2 ombyttinger.

Anta at tabellen inneholder er permutasjon av tallene fra 1 til n. Husk at (se Avsnitt 1.1.6) det gjennomsnittlige antallet tall som er større enn det største foran er gitt ved H_n − 1. Ta første runde i boblesorteringen. Da skjer det en ombytting hver gang det kommer et tall (fra og med det andre tallet) som ikke er større enn det største foran. Med andre ord blir det i gjennomsnitt n − 1 − (H_n − 1) = n − H_n ombyttinger i første runde.

Det blir litt verre å finne antallet ombyttinger i de neste rundene siden hver «runde» drar med seg verdier mot høyre. Men det viser seg at det i gjennomsnitt for hele sorteringen blir nøyaktig n(n − 1)/4 ombyttinger.

En annen måte å se dette på er å se på antallet inversjoner i tabellen - se Avsnitt 1.3.14. Det utføres nøyaktig like mange ombyttinger i boblesortering som det er inversjoner i tabellen og det gjennomsnittlige antallet inversjoner i en permutsajon av tallene fra 1 til n er nøyaktig lik n(n − 1)/4.