Algoritmu ieviešanas kārtošana Python

Kārtošana ir viena no visvairāk izmantotajām programmām. Ja mēs neizmantojām pareizo algoritmu, šķirošanas pabeigšana prasīs laiku.

Šajā rakstā mēs apspriedīsim dažādus šķirošanas algoritmus.

Mēs iepazīstināsim jūs ar dažādiem šķirošanas algoritmiem katrā ieviešanas posmā. Īstenošanas daļa būs Python. Kad esat ieguvis algoritmu, varat to viegli pārvērst jebkurā valodā. Tas ir valodas sintakses jautājums.

Šajā apmācībā mēs redzēsim dažādus algoritmus no sliktākajiem līdz labākajiem. Tātad, neuztraucieties. Izpildiet rakstu un ieviesiet tos.

Iedziļināsimies šķirošanas algoritmos.

Ievietošanas kārtošana

Ievietošanas kārtošana ir viens no vienkāršajiem kārtošanas algoritmiem. To ir viegli īstenot. Un tas maksās vairāk laika, lai sakārtotu masīvu. Vairumā gadījumu tas netiks izmantots lielāku masīvu šķirošanai.

Ievietošanas kārtošanas algoritms saglabā sakārtotās un nešķirotās apakšdaļas dotajā masīvā.

Sakārtotajā apakšdaļā ir tikai pirmais elements šķirošanas procesa sākumā. Mēs paņemsim elementu no nešķirotā masīva un novietosim tos pareizajā pozīcijā sakārtotajā apakšmasīvā.

Apskatīsim ievietošanas kārtošanas vizuālās ilustrācijas soli pa solim ar piemēru.

Apskatīsim ievietošanas kārtošanas ieviešanas darbības.

  • Inicializējiet masīvu ar fiktīviem datiem (veseliem skaitļiem).
  • Atkārtojiet doto masīvu no otrā elementa.
    • Paņemiet pašreizējo pozīciju un elementu divos mainīgajos.
    • Uzrakstiet cilpu, kas atkārtojas, līdz parādās pirmais masīva elements vai elements, kas ir mazāks par pašreizējo elementu.
      • Atjauniniet pašreizējo elementu ar iepriekšējo elementu.
      • Pašreizējās pozīcijas samazināšana.
    • Šeit cilpai ir jāsasniedz vai nu masīva sākums, vai jāatrod mazāks elements nekā pašreizējais elements. Aizstāt pašreizējās pozīcijas elementu ar pašreizējo elementu.

Ievietošanas kārtošanas laika sarežģītība ir O(n^2), un telpas sarežģītība, ja O(1).

Tieši tā; esam sakārtojuši doto masīvu. Palaidīsim šādu kodu. Es ceru, ka esat instalējis Python, ja ne, skatiet instalēšanas rokasgrāmatu. Varat arī izmantot tiešsaistes Python kompilatoru.

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

Atlase Kārtot

Atlases kārtošana ir līdzīga ievietošanas kārtošanai ar nelielu atšķirību. Šis algoritms arī sadala masīvu sakārtotās un nešķirotās apakšdaļās. Un tad katrā iterācijā mēs ņemsim minimālo elementu no nešķirotās apakšdaļas un novietosim to sakārtotās apakšdaļas pēdējā pozīcijā.

  Kas ir attālās piekļuves kods?

Lai labāk izprastu, kārtosim atlases ilustrācijas.

Apskatīsim atlases kārtošanas ieviešanas darbības.

  • Inicializējiet masīvu ar fiktīviem datiem (veseliem skaitļiem).
  • Atkārtojiet pa norādīto masīvu.
    • Saglabājiet minimālā elementa indeksu.
    • Uzrakstiet cilpu, kas atkārtojas no pašreizējā elementa līdz pēdējam elementam.
      • Pārbaudiet, vai pašreizējais elements ir mazāks par minimālo elementu.
      • Ja pašreizējais elements ir mazāks par minimālo elementu, nomainiet indeksu.
    • Mums līdzi ir minimālais elementu indekss. Apmainiet pašreizējo elementu ar minimālo elementu, izmantojot indeksus.

Atlases kārtošanas laika sarežģītība ir O(n^2), un telpas sarežģītība, ja O(1).

Mēģiniet ieviest algoritmu, jo tas ir līdzīgs ievietošanas kārtošanai. Jūs varat redzēt kodu zemāk.

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

Burbuļu kārtošana

Burbuļu kārtošana ir vienkāršs algoritms. Tas atkārtoti apmaina blakus esošos elementus katrā iterācijā, līdz dotais masīvs ir sakārtots.

  Ansible iesācējiem — Ansible pamati un kā tas darbojas

Tas atkārtojas pa masīvu un pārvieto pašreizējo elementu uz nākamo pozīciju, līdz tas ir mazāks par nākamo elementu.

Ilustrācijas palīdz mums vizuāli izprast burbuļu kārtošanu. Apskatīsim viņus.

Apskatīsim darbības, lai ieviestu burbuļu kārtošanu.

  • Inicializējiet masīvu ar fiktīviem datiem (veseliem skaitļiem).
  • Atkārtojiet pa norādīto masīvu.
  • Atkārtojiet no 0 līdz ni-1. Pēdējie i elementi jau ir sakārtoti.
  • Pārbaudiet, vai pašreizējais elements ir lielāks par nākamo elementu.
  • Ja pašreizējais elements ir lielāks par nākamo elementu, nomainiet abus elementus.
  • Burbuļu kārtošanas laika sarežģītība ir O(n^2), un telpas sarežģītība, ja O(1).

    Tagad varat viegli ieviest burbuļu kārtošanu. Apskatīsim kodu.

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

    Sapludināt Kārtot

    Sapludināšanas kārtošana ir rekursīvs algoritms dotā masīva kārtošanai. Laika sarežģītības ziņā tas ir efektīvāks par iepriekš apspriestajiem algoritmiem. Tas seko „skaldi un uzvar” pieejai.

    Sapludināšanas kārtošanas algoritms sadala masīvu divās daļās un kārto tās atsevišķi. Pēc divu masīva daļu šķirošanas tas apvieno tās vienā sakārtotā masīvā.

    Tā kā tas ir rekursīvs algoritms, tas sadala masīvu, līdz masīvs kļūst par vienkāršāko kārtojamo (masīvs ar vienu elementu).

    Ir pienācis laiks ilustrācijām. Paskatīsimies.

    Apskatīsim sapludināšanas kārtošanas ieviešanas darbības.

    • Inicializējiet masīvu ar fiktīviem datiem (veseliem skaitļiem).
    • Uzrakstiet funkciju, ko sauc par sapludināšanu, lai sapludinātu apakšmasīvus vienā sakārtotā masīvā. Tas pieņem argumentu masīvu, kreiso, vidējo un labo indeksus.
      • Iegūstiet kreiso un labo apakšmasīvu garumus, izmantojot dotos indeksus.
      • Kopējiet elementus no masīva attiecīgajā kreisajā un labajā masīvā.
      • Atkārtojiet divus apakšmasīvus.
        • Salīdziniet abus apakšmasīvu elementus.
        • Nomainiet masīva elementu ar mazāko elementu no diviem kārtošanas apakšmasīviem.
      • Pārbaudiet, vai abos apakšmasīvos ir atlikuši elementi.
      • Pievienojiet tos masīvam.
    • Uzrakstiet funkciju merge_sort ar parametru masīvu, kreiso un labo indeksu.
      • Ja kreisais indekss ir lielāks vai vienāds ar labo indeksu, atgriezieties.
      • Atrodiet masīva viduspunktu, lai sadalītu masīvu divās daļās.
      • Rekursīvi izsauciet merge_sort, izmantojot kreiso, labo un vidējo indeksu.
      • Pēc rekursīvajiem izsaukumiem sapludiniet masīvu ar sapludināšanas funkciju.
      Kā atvienot tālruņa numuru no Discord

    Sapludināšanas kārtošanas laika sarežģītība ir O(nlogn), un telpas sarežģītība, ja O(1).

    Tas ir viss sapludināšanas kārtošanas algoritma ieviešanai. Pārbaudiet tālāk norādīto kodu.

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

    Secinājums

    Ir daudzi citi šķirošanas algoritmi, taču iepriekš minēti daži no bieži lietotajiem. Cerams, ka jums patika mācīties šķirošanu.

    Tālāk uzziniet par meklēšanas algoritmiem.

    Laimīgu kodēšanu 🙂 👨‍💻