Sortering (boble, indsættelse)

Informatik C · STX · C-niveau · Computational thinking

💻 Sortering (boble, indsættelse)

Sorteringsalgoritmer ordner elementer i stigende/faldende orden.

Bobble-sort: sammenlign nabopar, byt hvis i forkert orden, gentag indtil ingen bytter.

Tidskompleksitet: O(n²) worst case, O(n) best case (allerede sorteret).

Pseudokode: ``\nFOR i = 0 til n-1:\n FOR j = 0 til n-i-1:\n IF liste[j] > liste[j+1]: byt(liste[j], liste[j+1])\n`` Ineffektiv for store datasæt, men let at forstå + implementere.

Indsættelses-sort (insertion sort): byg sorteret del én ad gangen — tag næste element, indsæt på rette plads i sorteret del.

Tidskompleksitet: O(n²) worst, O(n) best. Hurtig for små eller næsten-sorterede datasæt.

Andre sorteringer: Selection sort O(n²), Quicksort O(n log n) gennemsnit (mest brugt i biblioteker), Merge sort O(n log n) garanteret, Heap sort O(n log n).

Stabil (bevarer ordenen for elementer med samme nøgle): merge sort, indsættelses-sort.

Sammenligning vs. ikke-sammenligning: Counting sort, radix sort er O(n) for små heltal.

Anvendelse: databaser, søgealgoritmer (binær søgning kræver sorteret), rangordning (top-10 lister), grafik (z-buffer rendering).

Visualisering: Sorting Algorithm Animations (online), VisuAlgo.

Læringsmål

• Anvende dekomposition (opdele problemer)
• Identificere mønstergenkendelse og abstraktion
• Skrive pseudokode og flowcharts
• Anvende lineær og binær søgning
• Anvende sortering (boble, indsættelse)

Sådan kan du arbejde med emnet

• Implementér bobblesort i Python og spor, hvad der sker med en 6-elements liste trin for trin
• Implementér indsættelsessortering og sammenlign antallet af swaps med bobblesort på samme data
• Forklar, hvad der er tidskompleksiteten for bobblesort i det bedste og det værste tilfælde

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.