Sorteringsalgoritmer-implementeringer i Python

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.

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.

Initialiser matrisen med dummydata (heltall).

Iterer over den gitte matrisen.

Iterer fra 0 til ni-1. De siste i-elementene er allerede sortert.

Sjekk om det gjeldende elementet er større enn det neste elementet eller ikke.

Hvis det gjeldende elementet er større enn det neste elementet, så bytt de to elementene.

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 🙂 👨‍💻