Sortera en array med data är en av de klassiska problemen i datavetenskap , och så det borde inte komma som någon överraskning att en mängd olika metoder för sortering i Turbo C och andra språk har tänkt . De sträcker sig från ineffektiva men enkel att implementera metoder för att mycket snabbare men mer komplexa metoder . Den bästa algoritmen för en situation beror på den förväntade storleken på de data som ska sorteras och vikten av effektivitet . Bubble Sort
Bubble Sort är det enklaste , och långsammast , sortering algoritm . Den utgår helt enkelt genom arrayen och jämför det aktuella elementet till elementet direkt framför den . Om dessa två delar är i ordning , byter de plats . När bubblan Sortera når slutet , kontrollerar den för att se om något förändrats ställen . Om det gjorde det , börjar det om från början . Det fortsätter loopa igenom arrayen tills det lyckas fullfölja en hel passera utan att göra någon byta . I genomsnitt tar det O ( n ² ) tid , men om uppgifterna är kända för att vara mycket nära sorterade , med kanske bara en del på sin plats , kan det fungera i O ( n ) . Så det är en bra metod för små matriser som inte sorteras ofta eller större matriser som är kända för att redan sorteras ( eller väldigt nära så ) för det mesta .
Selection Sort
Selection sort är något mer raffinerat än Bubble sort . Algoritmen fortsätter genom hela samling av data för att hitta det minsta elementet . Varhelst det elementet är , har det sin position bytte med det första elementet , och en räknare konstaterar att det första elementet i arrayen är kända för att vara ordentligt sorteras . Den fortsätter sedan genom hela matrisen igen , med undantag för det första elementet ( vilket är känt för att vara i rätt plats . ) När den hittar den lägsta elementet , flyttas det till det andra och ökar räknaren för att indikera att de två första element är kända som skall sorteras . Sammantaget arbetar Selection Sort i O ( n ² ) tid , men den har en fördel : som mest , endast n -1 ändrar någonsin inträffar i arrayen , eftersom varje element endast flyttas när dess läge är känt . Detta gör den till en bra algoritm i vissa exotiska situationer där data skrivs till minnet tar drastiskt längre än att läsa den .
Quicksort
Som namnet antyder , den QuickSort är snabb. I genomsnitt kan den utföra ett slags i O ( n log n ) tid. Men det är mycket mer komplicerat än många andra program och kräver att utvecklaren veta lite om data i arrayen innan handen . Först en " pivot värde " måste väljas . Detta är det värde som utvecklaren tror ligger nära medianen av alla värden i arrayen. Ju bättre pivot värde , desto snabbare Quicksort kommer att utföra . Därefter arrayen indelade i två grupper : de som ovanför pivot värde flyttas till den högra sidan , och de under den svängbara värde flyttas till den vänstra sidan . Förhoppningsvis , de två sidorna är nära att vara lika i storlek , men de behöver inte vara exakt samma . Slutligen börjar quicksort algoritmen om från början på varje sida , med nya pivot valda värden , och dessa halvor så småningom delas i fjärdedelar . När quicksort har uppdelat arrayen så att varje sektion har bara ett värde , har arrayen har sorterats .
Liksom de flesta rekursiva algoritmer , kan detta vara svårt att visualisera , så du uppmuntras att se steg för steg - exempel som ges i tredje referens .
