Start Logga In Skriv Artikel Om Oss
Vad söker du?
Allt om 'Sorteringsalgoritm'

Sorteringsalgoritm

Innehåll- 1. Stabilitet - 2. Prestandagränser - 3. Vanliga algoritmer

En sorteringsalgoritm är en metod för att sortera data. Olika algoritmer har olika egenskaper.

1. Stabilitet

En sorteringalgoritm är stabil om den inte byter plats på element som är lika.

2. Prestandagränser

Det kan visas att om sorteringen bygger på att man jämför element med varandra så kan man inte nå bättre tidskomplexitet än O(n*log n). Om man kan utnyttja speciella egenskaper hos datat så kan man få ner det till O(n). T.ex. om man vet att man som data har nummer mellan 10 och 30 i vilket fall man kan lägga upp fack för de olika numren och sortera in dem i de facken likt en brevbärare.

3. Vanliga algoritmer

  • Quicksort - Oftast snabb (n*log n), men O(n^2) i värsta fallet. Inte stabil.
  • Heapsort - O(n*log n)
  • Merge sort - Designad för fallet när inte hela mängden får plats i minnet. O(n*log n). Stabil.
  • Shell sort - snabb, men svåranalyserad. Någonstans mellan O(n*log n) och O(n^2) beroende på implementation.
  • Insertion sort - långsam, men mycket bra på mängder som är så gott som sorterade. O(n^2)
  • Selection sort - långsam. O(n^2)
  • Bubblesort - mycket långsam men lätt att komma ihåg. O(n^2)
  • Radix sort - Linjär i tiden, men kräver speciella egenskaper hos datat. Använder minne proportionellt mot mängden av möjliga element.

Redigera?

Artikeln skriven 2009-01-16 av Learning4sharing

Inga kategorier för denna artikel än...

Vi behhöver hjälp att kategorisera våra artiklar. Kan du skriva ett nyckelord för denna artikel? Du kan skriva upp till 3 olika nyckelord för denna artikel, vi uppskattar din hjälp!

Skriv nyckelord som du tycker beskriver denna artikel på ett bra sätt. Du kan ange 3 olika nyckelord för denna artikel, max 20 tecken per nyckelord.

  1. Lägg till fler
    Skriv in svaret på frågan: 4+10

Intresserad av fler artiklar?

Quicksort
Solokarriär
Arbogaån
Humla
Bi
Lina
Vinare
Ring
Katoliker

Senaste sökningarna

IT har fått 1540 sökningar. Den senaste gjordes 2021-09-18 19:50:39.

boktryck har fått 1241 sökningar. Den senaste gjordes 2021-09-18 19:48:54.

rosen har fått 1229 sökningar. Den senaste gjordes 2021-09-18 19:47:10.

Servostyrning har fått 1173 sökningar. Den senaste gjordes 2021-09-18 19:44:47.

fyrtornet har fått 1107 sökningar. Den senaste gjordes 2021-09-18 19:43:59.

regiassistent har fått 1195 sökningar. Den senaste gjordes 2021-09-18 19:42:38.

cell har fått 1455 sökningar. Den senaste gjordes 2021-09-18 19:42:25.

snus har fått 1591 sökningar. Den senaste gjordes 2021-09-18 19:41:24.

dreja har fått 1187 sökningar. Den senaste gjordes 2021-09-18 19:40:52.

error har fått 1318 sökningar. Den senaste gjordes 2021-09-18 19:40:35.

spel har fått 1458 sökningar. Den senaste gjordes 2021-09-18 19:40:21.

lss har fått 1555 sökningar. Den senaste gjordes 2021-09-18 19:38:58.

Designed by: template world
Learning4sharing.nu
All Rights Reserved. 0.29 SEK

Logga in

Välkommen att redigera och skriva nya artiklar!

Ingent Konto?

Skaffa konto för att redigera och skapa nya ariklar Nytt Konto.

Ny Användare

Välkommen att redigera och skriva nya artiklar! Skapa konto nedan.


Ett verifieringsmail kommer att skickas till din E-post som du måste öppna och verifiera din E-post med

Lägg till artikel

Du är inte inloggad.

Logga In eller Skapa konto.