Sortering Flashcards

1
Q

Hva er ideen til Bubble sort?

A

Vi løper gjennom arrayet og “retter opp” feil, helt til det ikke er noen flere feil å rette opp.

  1. Løp over hvert par av etterfølgende elementer i arraayet.
  2. Bytte om rekkefølgen for paret dersom det ikke er ordnet.
  3. Gå til 1. dersom det forekom minst et bytte.

For hver runde drar vi med oss det neste største elementet til bunnen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Hva er ideen til Selection sort?

A

Vi finner det minste elementet i resten og plasserer dette først.

  1. La i være 0
  2. Finn hvor det minste elementet fra i og utover ligger
  3. Bytt ut elemntet på plass i med det minste (hvis nødvendig)
  4. Øk i og gå til 2. frem til i når størrelsen av arrayet.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Hva er ideen til Insertion sort?

A

Vi plasserer alle elementene sortert inn i en liste, vi lar alt til venster for en posisjon ‘i’ være sortert.

  1. La i være 1
  2. Dra det i-te elementet mot venstre så lenge det er mindre enn elementet før seg (som ved sortert innsetting)
  3. Øk i og gå til 2. frem til i når størrelsen av arrayet.

(Slik en ville sortert kort)

Når vi drar i-te elementet mot venstre, så bytter vi plass med element på plass forran seg i arrayet, og dette gjør vi helt til vi har flyttet elementet til indeks 0 eller elementet på plassen forran er mindre eller lik elementet vi drar mot venstre.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Hva er ideen til Heapsort?

A

Vi bygger en max-heap og popper elementer av heapen.
- Siden heap kan implementeres som et array, kan vi gjøre om input arrayet til en heap.

  1. Gjør arrayet til en max-heap
  2. La i være n-1 der n er størrelsen på arrayet
  3. Pop fra max-heapen og plasser elementet på plass i
  4. Senk i og gå til 3. frem til i blir 0

Vi bruker en prosedyre BubbleDown for å lage max-heapen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Hva er ideen til Merge sort?

A

Vi splitter arrayet i to ca. like store deler, deretter:

  • sorterer de to mindre arrayene
  • flette (merge) de to sortere arrayene
  1. La n angi størrelsen på arrayet A
  2. hvis n <= 1, returner A
  3. la i = n//2
  4. splitt arrayet i to deler A[0..i] og A[i…n-1]
  5. avend merge sort rekursivt på de to arrayene
  6. flett sammen de to arrayene sortert.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Hva er ideen til Quicksort?

A

Vi velger et element, så

  • samle alt som er mindre enn elementet til venstre for det
  • samle alt som er størrre enn elementet til høyre for det
  • gjør dette rekursivt
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Hva er ideen til Bucket sort?

A

Vi lager N bøtter, hvor bøtte svarer til en kategori eller sort og kategoriene er ordnet.

Hvert element vi sorterer har en kategori, som tilsvarer en nøkkel.
Vi plasserer så vært element i riktig bøtte basert på nøkkelen.
Så løper vi gjennom hver bøtte og plasserer elementene tilbake i arrayet.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Hva er ideen til Radix sort?

A

Radix sort er en suksessiv anvendelse av bucket sort.
Altså om det benyttes flere bucket sort etter hverandre, hvor vi benytter prinsippet om at bucket sort er stabil.

For eksempel sortering av kort med to bucket soerteringer, hvor vi først sorterer på verdi og så sorterer på sort (hjerter, ruter, etc).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Hva betyr det at en sorteringsalgoritme er stabil?

A

Når en sorteringsalgoritme er stabil så er det slik at

  • for alle elementer x,y med samme nøkkel k
  • hvis x forekommer før y før sorteringen
  • så forekommer x før y etter sorteringen

For eksempel bucket sort av kort etter kun verdi, om ruter 7 kommer før kløver 7 før sorteringen, så kommer ruter 7 også før kløver 7 etter sorteringen
- (7 er altså bøtte kategorien og nøkkelen k)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Hvordan kan vi implementere Bubble sort?

A

Benytter dobbel for-loop i/j:

  • Den indre loopen går til og med n - i - 2 (hvor i er den ytre loopen) fordi vi drar med oss det i’nde største elementet til bunn hver runde i den ytre loopen.
  • Altså vet vi at elementene etter n-i-2 allerede er sortert riktig.

for i=0 to n-2 do

    • for j=0 to n-i-2
  • — if A[j] > A[j+1] then
  • —– swap(j, j+1)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Hvordan kan vi implementere Selection sort?

A

Benytter dobbel for-loop i/j:

  1. La i være 0
  2. Finn det minste elementet fra j=i+1 og utover ligger.
  3. Bytt ut elemntet på plass i med det minste (hvis nødvendig)
  4. Øk i og gå til 2. frem til i når størrelsen av arrayet.

for i=0 to n-1 do

    • k=i
    • for j=i+1 to n-1 do
  • — if A[j] < A[k] then
  • ——- k=j
    • end
    • if i != k then
  • — swap(i, k)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Hvordan kan vi implmenetere Insertion sort?

A

Benytter en for-loop og en while-loop:

  1. La i være 1
  2. Dra det i-te elementet mot venstre som ved sortert innsetting
  3. Øk i og gå til 2. frem til i når størrelsen av arrayet.

Vi drar altså det i-te elementet plass for plass mot venstre (indeks 0) så lenge det i-te elementet er mindre enn det som kommer på plass A[j-1]

for i=1 to n-1 do

    • j = i
    • while j > 0 and A[j-1] > A[j] do
  • — swap(j-1, j)
  • — j = j-1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Hvordan kan vi implementere Heapsort?

A
  1. Gjør arrayet til en max-heap
  2. La i være n-1 der n er størrelsen på arrayet
  3. Pop fra max-heapen og plasser elementet på plass i
  4. Senk i og gå til 3. frem til i blir 0

Vi bruker en prosedyre BubbleDown for å lage max-heapen.

BuildMaxHeap(A, n)
for i=n/2 down to 0 do
– BubbleDown(A, i, n)

HeapSort(A)

    • BuildMaxHeap(A, n)
    • for i = n-1 down to 0 do
  • — swap(0, i)
  • — BubbleDown(A, 0, i)

Vi bygger en max-heap.
Så for hver loop, før vi krymper arrayet vi jobber med (for loop) flytter vi det største elementet (som er på plass 0 i en max-heap) ned til bunnen som er plass i.
Når vi har flyttet dette største elementet kaller vi BubbleDown med n=i så vi ikke bobbler hele veien ned og drar det største elementet til toppen igjen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Hvordan kan vi implementere Quicksort?

A

Velg pivot-element ‘i’
- søk fra venstre mot høyre etter et element som er større enn A[i]
- søk fra høyre mot venstre etter et element som er mindre enn A[i]
- bytt plass på disse, og søk etter nye som kan byttes
- avslutt når høyre og venstre søkene krysser.
Fortsett rekursivt på alle som er hhv. til venstre og høyre for pivot.

Prosedyren Partion
- Flytter elementer som er hhv. mindre og større til venstre og høyre enn en gitt index som returneres.

Quicksort(A, low, high)

    • if low >= high then
  • — return A
    • p = Partition(A, low, high)
    • Quicksort(A, low, p-1)
    • Quicksort(A, p+1, high)
    • return A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Hvordan kan vi implementere Quicksort?

A

Velg pivot-element ‘i’
- søk fra venstre mot høyre etter et element som er større enn A[i]
- søk fra høyre mot venstre etter et element som er mindre enn A[i]
- bytt plass på disse, og søk etter nye som kan byttes
- avslutt når høyre og venstre søkene krysser.
Fortsett rekursivt på alle som er hhv. til venstre og høyre for pivot.

Prosedyren Partion
- Flytter elementer som er hhv. mindre og større til venstre og høyre enn en gitt index som returneres.

Quicksort(A, low, high)

    • if low >= high then
  • — return A
    • p = Partition(A, low, high) // returnerer pivot indeksen
    • Quicksort(A, low, p-1)
    • Quicksort(A, p+1, high)
    • return A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Hvordan kan vi implementere Bucket sort?

A

Hvert element vi sorterer har en kategori, som tilsvarer en nøkkel.
Vi plasserer så vært element i riktig bøtte basert på nøkkelen.
Så løper vi gjennom hver bøtte og plasserer elementene tilbake i arrayet.

BucketSort(A)

    • B = et array med N tomme lister
    • for i=0 til n-1 do
  • — La k være nøkkelen assosiert med A[i]
  • — Legg til A[i] på slutten av listen B[k]
    • end
    • j=0
    • for k=0 to N-1 do
  • — for hver x i listen B[k] do
  • —– A[j] = x
  • —– j = j +1
    • return A
17
Q

Hvordan kan vi implementere Radix sort?

A

RadixSort(A):
d ← antall siffer i det største tallet (N), altså antall bucket sorts
for i ← d down to 0 do
– A ← BucketSort(A) etter det ite sifferet
return A