Sortering utgör en grundläggande operation inom programmering, och valet av algoritm är avgörande för effektivitet. Felaktig algoritm kan resultera i oacceptabelt långa sorteringstider.
I den här artikeln kommer vi att utforska olika sorteringsalgoritmer, från de enklaste till mer komplexa.
Vi går igenom varje algoritm steg för steg, inklusive implementeringen i Python. Kodexempel kan enkelt anpassas till andra programmeringsspråk. Skillnaderna ligger huvudsakligen i syntax.
Denna handledning presenterar algoritmerna i stigande ordning av effektivitet, från sämst till bäst. Följ med och experimentera med kodexemplen.
Låt oss dyka ner i världen av sorteringsalgoritmer.
Insättningssortering
Insättningssortering är en relativt enkel algoritm att förstå och implementera, men den är inte optimal för stora datamängder. Den fungerar bäst på mindre eller nästan sorterade listor.
Denna metod bygger på idén om att dela upp den givna listan i en sorterad och en osorterad del.
I början består den sorterade delen av det första elementet. Element från den osorterade delen plockas ut och placeras på sin korrekta position i den sorterade delen.
Låt oss illustrera insättningssortering steg för steg med ett exempel.
Nedan följer stegen för att implementera insättningssortering:
- Initialisera en array med slumptal (heltal).
- Iterera igenom arrayen från det andra elementet.
- Spara det aktuella elementets position och värde i separata variabler.
- Skapa en loop som fortsätter tills arrayens början nås eller ett element mindre än det aktuella elementet påträffas.
- Flytta fram elementen som är större än det aktuella elementet.
- Minska den aktuella positionen.
- Placera det aktuella elementet på rätt plats i den sorterade delen.
Tidskomplexiteten för insättningssortering är O(n^2) och rymdkomplexiteten är O(1).
Det är allt! Listan är nu sorterad. Här är kodexemplet i Python. (Se till att Python är installerat, eller använd en onlinekompilator).
def insertion_sort(arr, n): for i in range(1, n): current_position = i current_element = arr[i] while current_position > 0 and current_element < arr[current_position - 1]: arr[current_position] = arr[current_position - 1] current_position -= 1 arr[current_position] = current_element if __name__ == '__main__': arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] insertion_sort(arr, 9) print(str(arr))
Urvalssortering
Urvalssortering liknar insättningssortering, men med en viktig skillnad. Även här delas listan upp i en sorterad och osorterad del. Vid varje iteration hämtas det minsta elementet från den osorterade delen och placeras sist i den sorterade delen.
Låt oss illustrera urvalssortering för en bättre förståelse.
Här är stegen för att implementera urvalssortering:
- Initialisera en array med slumptal (heltal).
- Iterera igenom hela arrayen.
- Spara indexet för det minsta elementet.
- Skapa en loop som går igenom den osorterade delen av arrayen.
- Kontrollera om det aktuella elementet är mindre än det nuvarande minsta.
- Uppdatera indexet för det minsta elementet om så är fallet.
- Byt plats på det aktuella elementet och det minsta elementet.
Tidskomplexiteten för urvalssortering är O(n^2), och rymdkomplexiteten är O(1).
Försök att implementera algoritmen själv då den liknar insättningssortering. Här är koden som referens.
def selection_sort(arr, n): for i in range(n): min_element_index = i for j in range(i + 1, n): if arr[j] < arr[min_element_index]: min_element_index = j arr[i], arr[min_element_index] = arr[min_element_index], arr[i] if __name__ == '__main__': arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] selection_sort(arr, 9) print(str(arr))
Bubbelsortering
Bubbelsortering är en enkel algoritm som upprepade gånger byter plats på intilliggande element tills listan är sorterad.
Algoritmen itererar över listan och flyttar varje element framåt i listan tills den hamnar på en plats där den är mindre än nästa element.
Illustrationer kan hjälpa till att visualisera bubbelsortering, låt oss kolla på dem.
Här är stegen för att implementera bubbelsortering:
Tidskomplexiteten för bubbelsortering är O(n^2), och rymdkomplexiteten är O(1).
Du kan enkelt implementera bubbelsortering nu. Här är koden:
def bubble_sort(arr, n): for i in range(n): for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] if __name__ == '__main__': arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] bubble_sort(arr, 9) print(str(arr))
Sammanslagningssortering
Sammanslagningssortering är en rekursiv algoritm för att sortera en lista. Den är effektivare än de tidigare diskuterade algoritmerna vad gäller tidskomplexitet. Den bygger på ”dela och härska”-principen.
Algoritmen delar upp listan i två halvor, som sorteras separat. Sedan slås de två sorterade halvorna samman till en enda sorterad lista.
Eftersom sammanslagningssortering är en rekursiv algoritm, fortsätter delningen tills listan inte kan delas ytterligare (en lista med ett enda element är sorterad per definition).
Låt oss titta på en illustration.
Här är stegen för att implementera sammanslagningssortering:
- Initialisera en array med slumptal (heltal).
- Skriv en funktion, `merge`, som slår samman två sorterade sub-arrayer till en enda sorterad array. Funktionen tar arrayen, samt vänster-, mitt- och högerindex som argument.
- Beräkna längden på vänster och höger sub-arrayer.
- Kopiera elementen från den ursprungliga arrayen till separata vänster- och högerarrayer.
- Iterera igenom de två sub-arrayerna.
- Jämför elementen från de två sub-arrayerna.
- Ersätt element i arrayen med det mindre av de två elementen.
- Kontrollera om det finns några element kvar i de två sub-arrayerna.
- Lägg till resterande element i arrayen.
- Skriv en funktion, `merge_sort`, med arrayen samt vänster- och högerindex som parametrar.
- Om vänsterindex är större än eller lika med högerindex, avsluta funktionen.
- Beräkna mittpunkten för att dela arrayen i två halvor.
- Anropa `merge_sort` rekursivt för varje halva.
- Slå samman de sorterade halvorna med hjälp av `merge`-funktionen.
Tidskomplexiteten för sammanslagningssortering är O(n log n), och rymdkomplexiteten är O(n).
Det var allt för implementeringen av sammanslagningssortering. Här är den kompletta koden:
def merge(arr, left_index, mid_index, right_index): left_array = arr[left_index:mid_index+1] right_array = arr[mid_index+1:right_index+1] left_array_length = mid_index - left_index + 1 right_array_length = right_index - mid_index i = j = 0 k = left_index while i < left_array_length and j < right_array_length: if left_array[i] < right_array[j]: arr[k] = left_array[i] i += 1 else: arr[k] = right_array[j] j += 1 k += 1 while i < left_array_length: arr[k] = left_array[i] i += 1 k += 1 while j < right_array_length: arr[k] = right_array[j] j += 1 k += 1 def merge_sort(arr, left_index, right_index): if left_index >= right_index: return mid_index = (left_index + right_index) // 2 merge_sort(arr, left_index, mid_index) merge_sort(arr, mid_index + 1, right_index) merge(arr, left_index, mid_index, right_index) if __name__ == '__main__': arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] merge_sort(arr, 0, 8) print(str(arr))
Sammanfattning
Det finns många andra sorteringsalgoritmer, men ovanstående är några av de vanligaste. Vi hoppas att du har haft nytta av att utforska dessa sorteringsmetoder.
Fortsätt nu att studera sökalgoritmer.
Lycka till med kodningen! 🙂 👨💻