Sortering af algoritmer implementeringer i Python

Af
Tweet
Share
Share
Pin

Sortering er en af ​​de mest brugte funktioner i programmering. Og det vil tage tid at gennemføre sorteringen, hvis vi ikke brugte den korrekte algoritme.

I denne artikel skal vi diskutere forskellige sorteringsalgoritmer.

Vi vil lede dig gennem de forskellige sorteringsalgoritmer med hvert trin, der kommer i implementeringen. Implementeringsdelen vil være i Python. Du kan nemt konvertere det til ethvert sprog, når du har fået algoritmen. Det er spørgsmålet om sprogsyntaks.

Vi vil se forskellige algoritmer fra værste til bedste i denne tutorial. Så bare rolig. Følg artiklen og implementer dem.

Lad os dykke ned i sorteringsalgoritmerne.

Indsættelsessortering

Indsættelsessortering er en af ​​de simple sorteringsalgoritmer. Det er nemt at implementere. Og det vil koste dig mere tid at sortere et array. Det vil ikke blive brugt i de fleste tilfælde til sortering for større arrays.

Indsættelsessorteringsalgoritmen opretholder sorterede og usorterede underdele i det givne array.

Den sorterede underdel indeholder kun det første element i begyndelsen af ​​sorteringsprocessen. Vi tager et element fra det usorterede array og placerer dem i den korrekte position i det sorterede underarray.

Lad os se de visuelle illustrationer af indsættelse sortere trin for trin med et eksempel.

Lad os se trinene til at implementere indsættelsessorteringen.

  • Initialiser arrayet med dummy-data (heltal).
  • Iterér over det givne array fra det andet element.
    • Tag den aktuelle position og element i to variable.
    • Skriv en løkke, der itererer, indtil det første element i arrayet eller elementet opstår, der er mindre end det aktuelle element.
      • Opdater det aktuelle element med det forrige element.
      • Reduktion af den aktuelle position.
    • Her skal sløjfen enten nå starten af ​​arrayet eller finde et mindre element end det aktuelle element. Erstat det aktuelle positionselement med det aktuelle element.

Tidskompleksiteten af ​​indsættelsessorteringen er O(n^2), og rumkompleksiteten hvis O(1).

Det er det; vi har sorteret det givne array. Lad os køre følgende kode. Jeg håber du har installeret Python, hvis ikke tjek installationsvejledningen. Alternativt kan du bruge en online Python-kompiler.

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))

Udvalgssortering

Valgsorteringen ligner indsættelsessorteringen med en lille forskel. Denne algoritme opdeler også arrayet i sorterede og usorterede underdele. Og derefter, ved hver iteration, vil vi tage minimumselementet fra den usorterede underdel og placere den i den sidste position af den sorterede underdel.

  Sådan opretter du en sidekant i Microsoft Word

Lad os illustrationer af udvælgelse sortere for bedre forståelse.

Lad os se trinene for at implementere udvælgelsessortering.

  • Initialiser arrayet med dummy-data (heltal).
  • Gentag over det givne array.
    • Oprethold indekset for minimumselementet.
    • Skriv en løkke, der itererer fra det aktuelle element til det sidste element.
      • Kontroller, om det aktuelle element er mindre end minimumselementet eller ej.
      • Hvis det aktuelle element er mindre end minimumselementet, skal du erstatte indekset.
    • Vi har minimumselementindekset med os. Skift det aktuelle element med minimumselementet ved hjælp af indekserne.

Tidskompleksiteten af ​​udvælgelsessorten er O(n^2), og rumkompleksiteten hvis O(1).

Prøv at implementere algoritmen, da den ligner indsættelsessorteringen. 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))

Boble sortering

Boblesortering er en simpel algoritme. Det udskifter de tilstødende elementer på hver iteration gentagne gange, indtil det givne array er sorteret.

  Sådan deaktiverer du AT&T-meddelelser backup og synkronisering

Det itererer over arrayet og flytter det aktuelle element til den næste position, indtil det er mindre end det næste element.

Illustrationer hjælper os med at forstå boblesorteringen visuelt. Lad os se dem.

Lad os se trinene til at implementere boblesorteringen.

  • Initialiser arrayet med dummy-data (heltal).
  • Gentag over det givne array.
  • Gentag fra 0 til ni-1. De sidste i-elementer er allerede sorteret.
  • Kontroller, om det aktuelle element er større end det næste element eller ej.
  • Hvis det aktuelle element er større end det næste element, så skift de to elementer.

    • Tidskompleksiteten af ​​boblesorteringen er O(n^2), og rumkompleksiteten hvis O(1).

    Du kan nemt implementere boblesorteringen nu. Lad os 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))

    Flet sortering

    Merge sort er en rekursiv algoritme til at sortere den givne matrix. Det er mere effektivt end de tidligere diskuterede algoritmer med hensyn til tidskompleksitet. Det følger skille og hersk-tilgangen.

    Fletningssorteringsalgoritmen opdeler arrayet i to halvdele og sorterer dem separat. Efter at have sorteret de to halvdele af arrayet, flettes de sammen til et enkelt sorteret array.

    Da det er en rekursiv algoritme, deler den arrayet, indtil arrayet bliver det enkleste (array med ét element) at sortere.

    Det er tid til illustration. Lad os se det.

    Lad os se trinene til at implementere flettesorteringen.

    • Initialiser arrayet med dummy-data (heltal).
    • Skriv en funktion kaldet fletning for at flette sub-arrays til et enkelt sorteret array. Det accepterer argumenterne array, left, mid og right indekser.
      • Få længderne af venstre og højre underarrays længder ved hjælp af de givne indekser.
      • Kopier elementerne fra arrayet til de respektive venstre og højre arrays.
      • Gentag over de to underarrays.
        • Sammenlign de to sub-arrays elementer.
        • Udskift array-elementet med det mindre element fra de to under-arrays til sortering.
      • Kontroller, om der er elementer tilbage i begge underarrays.
      • Tilføj dem til arrayet.
    • Skriv en funktion kaldet merge_sort med parametre array, venstre og højre indekser.
      • Hvis det venstre indeks er større end eller lig med det højre indeks, så vend tilbage.
      • Find midtpunktet af arrayet for at dele arrayet i to halvdele.
      • Kald rekursivt merge_sort ved hjælp af venstre, højre og mid-indeks.
      • Efter de rekursive opkald skal du flette arrayet med flettefunktionen.
      Sidder du fast på skærmen CTRL+ALT+DEL? Her er, hvordan du løser dette

    Tidskompleksiteten af ​​flettesorteringen er O(nlogn), og rumkompleksiteten hvis O(1).

    Det er det for implementering af flettesorteringsalgoritmen. Tjek 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))

    Konklusion

    Der er mange andre sorteringsalgoritmer, men ovenfor er nogle af de hyppigt brugte. Håber du nød at lære sorteringen.

    Find derefter ud af om søgealgoritmer.

    God kodning 🙂 👨‍💻