Fråga om sorteringstid

Har en tentauppgift i "Datastrukturer och Algoritmer" här där läraren bara har skrivit svaret utan beräkning, förmodligen för att han vill att vi ska lära oss beräkningen själva.

Frågan går så här:

Antag att det dröjer 1s att sortera en array med n st tal med hjälp av
bubble sort. Hur lång tid (hur många sekunder) skulle det då ta att
sortera en tusen gånger så lång array (10^3 * n) med samma algoritm?


Jag skriver svaret här ifall ni vill se:

Uppskattar all hjälp

Vet du vad bubbelsort har för tidskomplexitet? Vet du vad tidskomplexitet är?

Om du läser om datastrukturer och algoritmer är det här fullständigt fundamentala saker.

https://sv.wikipedia.org/wiki/Komple...gsvetenskap%29

Vi lyckades lösa den, kan bli så att man missar det mest uppenbara när man har suttit sen kl 10 på morgonen och pluggat :P

(1000n)^2 = 1000^2 * n^2, alltså tar det 1000^2 = 1'000'000 ggr längre tid.

Jag tycker däremot att du är väldigt otrevlig. Istället för att ifrågasätta min kunskap inom DALGO så kunde du ha lagt ner den tiden på att skriva beräkningen istället.

En bättre länk:
https://en.wikipedia.org/wiki/Sorting_algorithm

Det svaret är inte helt korrekt.
Är arrayen sorterad eller ett värde fel så får du ett specialfall t då max sorteringstid är t^2. Så det korrekta svaret är t <= sorteringstiden <= t^2.

Jag undrade lite på vilken nivå jag skulle lägga förklaringen. Visst ibland får man hjärnsläpp, men det verkade som att du inte visste något alls. Det är skönt att veta innan man skriver en hel roman som förklaring.

Kuriosa:
Om listan är sorterad förutom ett element beror det väldigt mycket på placeringen av det felaktiga elementet. Ligger det i början tar det 2t, men om det ligger i slutet tar det t². För att undvika dessa specialare kan man köra igenom listan åt andra hållet varannan gång.

Det är en jävla skitalgoritm.
https://www.youtube.com/watch?v=lyZQPjUT5B4


Man kör en merge sort och forkar/parallellkör processen maximalt.
Det är nog den snabbaste sorteringsmetoden mig veterligen.

Javisst men om du skulle anta att du kan forka/tråda en bubbelsort i typ 128 trådar på en fet maskin då kan det bli rätt hyfsat resultat ändå,

Kör man tex tvåtrådat så kör den första tråden alla med jämna index (dvs i = 0; i++ i++), den andra tråden kör man med udda index (dvs j = 1; j++ j++) , när bägge trådarna är klara så kör en enkeltråd med ett svep med index ökande med 1, det kapar sorteringen i tid,

Men hur mycket tid då ? - Sorry men de anteckningarna har jag inte kvar (om de inte ligger i källaren dit jag inte ids leta)
Jag ska ha provat med upp till och med 8 trådar ( dvs i = 0; i += 8; ), fast ökningen i hastighet blev ju inte 8 ggr, drygt 7 kanske den blev - minns inte -- längesedan nu.

Skriver egentligen detta för att reta er sorteringsproffs så ni får ngt att klura på

Bubbelsorten kommer definitivt att dra mer ström med 128 processorer. Vilket i sig kan vara skönt en kall vinterdag.

Bubbelsort är T(n^2). Mergesort, heapsort och quicksort är T(n*log n).

Vid drygt 1000 element går vår perfekt parallelliserade bubbelsort på 128 processorer lika fort som en mergesort/heapsort/quicksort på en processor. Vid 1000000 element går mergesort/heapsort/quicksort ungefär 400 gånger fortare trots parallelliseringen.

Tyvärr skalar det inte linjärt, vilket du själv tycks ha upptäckt. En sortering skyfflar mycket minne och kommer att vara bussbegränsad, om inte jämförelseoperatorn är oerhört beräkningstung. Men då gör vi antagligen något annat fel. Av alla vanliga sorteringsalgoritmer är faktiskt mergesort den som är snällast mot bussen då den skyfflar data i sekventiell ordning, medan de andra tar hopp i minnet. Därför är faktiskt mergesort den algoritm som går bäst att parallellisera.

Såklart detta kan var skönt med mera värme, Vi måste ju underhålla klimateffekten så vi har ngt att göra i framtiden,
-- Ja dessa uppskattningar av sorteringstid är ju utefter worst case scenario, om datasettet redan är delvis sorterat så kan utfallet bli ett annat. Tack för synpunkterna, väl formulerade så, som sagt är bubblesort en usel lösning när volymen börjar bli stor.


Jämförelseoperatorn bör inte vara beräkningstung, jag tycker det lutar mycket riktigt åt ett designfel om den är så, bättre i såfall att skapa ett tillfälligt "viktvärde" som redan är förberäknat, så det inte behöver beräknas för varje jämförelse operation.

Om objekten är stora så är det mera lönsamt att sortera pekare till objekten för att slippa tidsödande memcpy operationer, precis så som du nämner om minnesbussen, först när datasetet är färdigsorterat så används pekarna till att bilda ett nytt sorterat dataset

dataset = lista, array, vektor etc
det finns ju annars datasets som inte anses vara sorterbara, tex färger, där relationsoperatorerna > < inte har någon mening Medans tex spelet sten, sax, påse har funktionella relationsoperatorer > <, men de blir ändå inte sorterbara,
tex sten > sax är sant osv..

Jag tycker du ska läsa boken "The Art of Computer Programming" skriven av Donald Knuth först, det kommer ta lite tid, men det är värt det