Sortering er en av de mest brukte funksjonene i programmering. Og det vil ta tid å fullføre sorteringen hvis vi ikke brukte riktig algoritme.
I denne artikkelen skal vi diskutere forskjellige sorteringsalgoritmer.
Vi vil lede deg gjennom de forskjellige sorteringsalgoritmene med hvert trinn som kommer i implementeringen. Implementeringsdelen vil være i Python. Du kan enkelt konvertere den til et hvilket som helst språk når du får algoritmen. Det er spørsmålet om språksyntaks.
Vi vil se forskjellige algoritmer fra verst til best i denne opplæringen. Så ikke bekymre deg. Følg artikkelen og implementer dem.
La oss dykke ned i sorteringsalgoritmene.
Innholdsfortegnelse
Innsettingssortering
Innsettingssortering er en av de enkle sorteringsalgoritmene. Det er enkelt å implementere. Og det vil koste deg mer tid å sortere en matrise. Det vil ikke bli brukt i de fleste tilfeller for sortering for større matriser.
Algoritmen for innsettingssortering opprettholder sorterte og usorterte underdeler i den gitte matrisen.
Den sorterte underdelen inneholder kun det første elementet i begynnelsen av sorteringsprosessen. Vi vil ta et element fra den usorterte matrisen og plassere dem i riktig posisjon i den sorterte undermatrisen.
La oss se de visuelle illustrasjonene av innsetting sortere trinn for trinn med et eksempel.
La oss se fremgangsmåten for å implementere innsettingssortering.
- Initialiser matrisen med dummydata (heltall).
- Iterer over den gitte matrisen fra det andre elementet.
- Ta gjeldende posisjon og element i to variabler.
- Skriv en sløyfe som itererer til det første elementet i matrisen eller elementet oppstår som er mindre enn det gjeldende elementet.
- Oppdater det gjeldende elementet med det forrige elementet.
- Redusering av gjeldende posisjon.
- Her må sløyfen enten nå starten av matrisen eller finne et mindre element enn det gjeldende elementet. Erstatt gjeldende posisjonselement med gjeldende element.
Tidskompleksiteten til innsettingssorteringen er O(n^2), og romkompleksiteten hvis O(1).
Det er det; vi har sortert den gitte matrisen. La oss kjøre følgende kode. Jeg håper du har installert Python, hvis ikke sjekk ut installasjonsveiledningen. Alternativt kan du bruke en online Python-kompilator.
def insertion_sort(arr, n): for i in range(1, n): ## current position and element current_position = i current_element = arr[i] ## iteratin until ### it reaches the first element or ### the current element is smaller than the previous element while current_position > 0 and current_element < arr[current_position - 1]: ## updating the current element with previous element arr[current_position] = arr[current_position - 1] ## moving to the previous position current_position -= 1 ## updating the current position element arr[current_position] = current_element if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] insertion_sort(arr, 9) ## printing the array print(str(arr))
Utvalgssortering
Utvalgssorteringen ligner på innsettingssorteringen med en liten forskjell. Denne algoritmen deler også matrisen inn i sorterte og usorterte underdeler. Og så, på hver iterasjon, vil vi ta minimumselementet fra den usorterte underdelen og plassere den i den siste posisjonen til den sorterte underdelen.
La oss illustrasjoner av utvalg sortere for bedre forståelse.
La oss se fremgangsmåten for å implementere utvalgssortering.
- Initialiser matrisen med dummydata (heltall).
- Iterer over den gitte matrisen.
- Oppretthold indeksen til minimumselementet.
- Skriv en løkke som itererer fra det gjeldende elementet til det siste elementet.
- Sjekk om det gjeldende elementet er mindre enn minimumselementet eller ikke.
- Hvis det gjeldende elementet er mindre enn minimumselementet, erstatter du indeksen.
- Vi har minimum elementindeks med oss. Bytt gjeldende element med minimumselementet ved å bruke indeksene.
Tidskompleksiteten til utvalgssorteringen er O(n^2), og romkompleksiteten hvis O(1).
Prøv å implementere algoritmen siden den ligner på innsettingssortering. Du kan se koden nedenfor.
def selection_sort(arr, n): for i in range(n): ## to store the index of the minimum element min_element_index = i for j in range(i + 1, n): ## checking and replacing the minimum element index if arr[j] < arr[min_element_index]: min_element_index = j ## swaping the current element with minimum element arr[i], arr[min_element_index] = arr[min_element_index], arr[i] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] selection_sort(arr, 9) ## printing the array print(str(arr))
Boblesortering
Boblesortering er en enkel algoritme. Den bytter de tilstøtende elementene på hver iterasjon gjentatte ganger til den gitte matrisen er sortert.
Den itererer over matrisen og flytter det gjeldende elementet til neste posisjon til det er mindre enn det neste elementet.
Illustrasjoner hjelper oss å forstå boblesorten visuelt. La oss se dem.
La oss se fremgangsmåten for å implementere boblesorteringen.
Tidskompleksiteten til boblesorteringen er O(n^2), og romkompleksiteten hvis O(1).
Du kan enkelt implementere boblesorteringen nå. La oss se koden.
def bubble_sort(arr, n): for i in range(n): ## iterating from 0 to n-i-1 as last i elements are already sorted for j in range(n - i - 1): ## checking the next element if arr[j] > arr[j + 1]: ## swapping the adjucent elements arr[j], arr[j + 1] = arr[j + 1], arr[j] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] bubble_sort(arr, 9) ## printing the array print(str(arr))
Slå sammen sortering
Merge sort er en rekursiv algoritme for å sortere den gitte matrisen. Det er mer effektivt enn de tidligere diskuterte algoritmene når det gjelder tidskompleksitet. Den følger skille og hersk-tilnærmingen.
Sammenslåingssorteringsalgoritmen deler matrisen i to halvdeler og sorterer dem separat. Etter å ha sortert de to halvdelene av matrisen, slår den dem sammen til en enkelt sortert matrise.
Siden det er en rekursiv algoritme, deler den matrisen til matrisen blir den enkleste (matrise med ett element) å sortere.
Det er tid for illustrasjon. La oss se det.
La oss se fremgangsmåten for å implementere sammenslåingssortering.
- Initialiser matrisen med dummydata (heltall).
- Skriv en funksjon kalt flette for å slå sammen undermatriser til en enkelt sortert matrise. Den godtar argumentene array, left, mid og right indekser.
- Få lengdene til venstre og høyre undergruppelengder ved å bruke de gitte indeksene.
- Kopier elementene fra arrayet til de respektive venstre og høyre arrayene.
- Iterer over de to undermatrisene.
- Sammenlign de to sub-array-elementene.
- Bytt ut array-elementet med det mindre elementet fra de to underarrayene for sortering.
- Sjekk om det er noen elementer igjen i begge undermatrisene.
- Legg dem til matrisen.
- Skriv en funksjon kalt merge_sort med parametere array, left og right indekser.
- Hvis venstre indeks er større enn eller lik høyre indeks, så returner.
- Finn midtpunktet til matrisen for å dele matrisen i to halvdeler.
- Kall merge_sort rekursivt ved å bruke venstre, høyre og mid indekser.
- Etter de rekursive anropene, slå sammen arrayet med flettefunksjonen.
Tidskompleksiteten til flettesorteringen er O(nlogn), og romkompleksiteten hvis O(1).
Det er det for implementering av flettesorteringsalgoritmen. Sjekk koden nedenfor.
def merge(arr, left_index, mid_index, right_index): ## left and right arrays left_array = arr[left_index:mid_index+1] right_array = arr[mid_index+1:right_index+1] ## getting the left and right array lengths left_array_length = mid_index - left_index + 1 right_array_length = right_index - mid_index ## indexes for merging two arrays i = j = 0 ## index for array elements replacement k = left_index ## iterating over the two sub-arrays while i < left_array_length and j < right_array_length: ## comapring the elements from left and right arrays if left_array[i] < right_array[j]: arr[k] = left_array[i] i += 1 else: arr[k] = right_array[j] j += 1 k += 1 ## adding remaining elements from the left and right arrays while i < left_array_length: arr[k] = left_array[i] i += 1 k += 1 while j < right_array_length: j += 1 k += 1 def merge_sort(arr, left_index, right_index): ## base case for recursive function if left_index >= right_index: return ## finding the middle index mid_index = (left_index + right_index) // 2 ## recursive calls merge_sort(arr, left_index, mid_index) merge_sort(arr, mid_index + 1, right_index) ## merging the two sub-arrays merge(arr, left_index, mid_index, right_index) if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] merge_sort(arr, 0, 8) ## printing the array print(str(arr))
Konklusjon
Det finnes mange andre sorteringsalgoritmer, men ovenfor er noen av de ofte brukte. Håper du likte å lære sorteringen.
Finn deretter ut om søkealgoritmer.
Lykke til med koding 🙂 👨💻