Python Sort: Metodat dhe algoritmet e renditjes në Python

Mësoni se si të përdorni funksionin Python Sort për renditjen e listave, vargjeve, fjalorëve, etj. duke përdorur metoda dhe algoritme të ndryshme renditjeje në Python:

Renditja është një teknikë që përdoret për renditje të dhënat në një rend sekuence ose në rend rritës ose zbritës.

Shumicën e kohës të dhënat e projekteve të mëdha nuk janë të renditura në rendin e duhur dhe kjo krijon probleme gjatë aksesit dhe tërheqjes së të dhënave të kërkuara në mënyrë efikase.

Për të zgjidhur këtë problem përdoren teknikat e renditjes. Python ofron teknika të ndryshme klasifikimi për shembull, Renditja me flluska, renditja e futjes, renditja e bashkimit, renditja e shpejtë, etj.

Në këtë tutorial, ne do të kuptojmë se si funksionon renditja në Python duke përdorur algoritme të ndryshme.

Python Sort

Sintaksa e Python Sort

Për të kryer renditjen, Python ofron funksionin e integruar, d.m.th. funksionin " sort() ". Përdoret për të renditur elementet e të dhënave të një liste në rend rritës ose në rend zbritës.

Le ta kuptojmë këtë koncept me një shembull.

Shembulli 1:

``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ``` 

Outputi:

Në këtë shembull, lista e dhënë e parenditur renditet në rend rritës duke përdorur funksionin " sort( ) " .

Shembulli 2:

``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ``` 

Outputi

Në shembullin e mësipërm, lista e dhënë e parenditur renditet në rend të kundërt duke përdorur funksionin " sort( reverse = True ) ".

Kohavend Renditja me flluskë O(n) O(n2) O(n2) O(1) Po Po Renditja e futjes O(n) O(n2) O(n2) O(1) Po Po Renditja e shpejtë O(n log(n)) O(n log(n)) O(n2) O(N) Jo Po Shkrije renditi O(n log(n)) O(n log(n)) O(n log(n)) O(N) Po Jo Renditja e grumbullit O(n log (n)) O(n log(n)) O(n log(n)) O(1) Jo Po

Në tabelën e mësipërme të krahasimit "O" është shënimi Big O i shpjeguar më sipër ndërsa "n" dhe "N" do të thotë madhësia e hyrjes .

Pyetjet e bëra më shpesh

P #1) Çfarë është sort () në Python?

Përgjigje: Në Python sort() është një funksion që përdoret për të renditur listat ose vargjet në një rend të caktuar. Ky funksion lehtëson procesin e renditjes gjatë punës në projekte të mëdha. Është shumë e dobishme për zhvilluesit.

Pyetja #2) Si e klasifikoni në Python?

Përgjigje: Python ofron teknika të ndryshme renditjeje që përdoren për të renditur elementin. Për shembull, Renditja e shpejtë, renditja e bashkimit, renditja me flluska, renditja e futjes, etj. Të gjitha teknikat e renditjes janë efikase dhe të lehta për t'u kuptuar.

P #3) Si funksionon Python lloj () punë?

Përgjigje: Renditja()Funksioni merr grupin e dhënë si hyrje nga përdoruesi dhe e rendit atë në një renditje specifike duke përdorur algoritmin e renditjes. Zgjedhja e algoritmit varet nga zgjedhja e përdoruesit. Përdoruesit mund të përdorin renditjen e shpejtë, renditjen e bashkimit, renditjen me flluska, renditjen e futjes, etj. në varësi të nevojave të përdoruesit.

Përfundim

Në tutorialin e mësipërm, kemi diskutuar teknikën e renditjes në Python së bashku me teknikat e përgjithshme të renditjes.

  • Renditja me flluska
  • Renditja me futje
  • Rregullimi i shpejtë

Mësuam për kompleksitetin dhe avantazhet e tyre kohore & disavantazhet. Gjithashtu krahasuam të gjitha teknikat e mësipërme.

Kompleksiteti i algoritmeve të renditjes

Kohë kompleksiteti është sasia e kohës që i duhet kompjuterit për të ekzekutuar një algoritëm të caktuar. Ka tre lloje të rasteve të kompleksitetit kohor.

  • Rasti më i keq: Koha maksimale që i duhet kompjuterit për të ekzekutuar programin.
  • Rasti mesatar: Koha e nevojshme ndërmjet minimumit dhe maksimumit nga kompjuteri për të ekzekutuar programin.
  • Rasti më i mirë: Koha minimale e marrë nga kompjuteri për të ekzekutuar programin. Është rasti më i mirë i kompleksitetit kohor.

Shënimet e kompleksitetit

Shënimi i madh Oh, O: Shënimi i madh oh është mënyra zyrtare për të përcjellë kufirin e sipërm të kohës së funksionimit të algoritmeve. Përdoret për të matur kompleksitetin kohor në rastin më të keq ose themi sasinë më të madhe të kohës që i duhet algoritmit për të përfunduar.

Shënimi i madh omega, : Shënimi i madh omega është mënyra zyrtare për të përcjellë kufirin më të ulët të kohës së funksionimit të algoritmeve. Përdoret për të matur kompleksitetin kohor në rastin më të mirë ose themi sasinë e shkëlqyer të kohës së marrë nga algoritmi.

Shënimi Theta, : Shënimi Theta është mënyra zyrtare për të përcjellë të dy kufijtë, d.m.th. i poshtëm dhe i sipërm i kohës që kërkon algoritmi për të përfunduar.

Metodat e renditjes në Python

Renditja me flluska

Rregullimi me flluska është mënyra më e thjeshtë për të renditur të dhënat i cili përdor teknikën e forcës brutale. Ai do të përsëritet në secilin element të të dhënave dhe do ta krahasojë atë me elementë të tjerëpër t'i ofruar përdoruesit të dhënat e renditura.

Le të marrim një shembull për të kuptuar këtë teknikë:

  • Na sigurohet një grup me elementet " 10, 40, 7, 3, 15”. Tani, ne duhet ta rregullojmë këtë grup në një rend rritës duke përdorur teknikën e renditjes Bubble në Python.
    • Hapi i parë është rregullimi i grupit në rendin e dhënë.
    • Në "Iteration 1", ne po krahasojmë elementin e parë të një vargu me elementët e tjerë një nga një.
    • Shigjetat e kuqe përshkruajnë krahasimin e elementeve të parë me elementët e tjerë të një grupi.
    • Nëse vëreni se " 10 " është më e vogël se " 40 ", pra, ajo mbetet e njëjtë vend por elementi tjetër “7” është më i vogël se “10”. Prandaj, ai zëvendësohet dhe vjen në vendin e parë.
    • Procesi i mësipërm do të kryhet vazhdimisht për të renditur elementët.

    • Në "Iteration 2" elementi i dytë po krahasohet me elementët e tjerë të një grupi.
    • Nëse elementi i krahasuar është i vogël atëherë, ai do të ndërrohet, përndryshe do të mbetet në të njëjtin vend. elementi i tretë po krahasohet me elementët e tjerë të një grupi.

    • Në të fundit “Iteration 4” elementi i dytë i fundit po krahasohet me elementët e tjerë të një grupi.
    • Nënë këtë hap grupi është renditur në rend rritës.

Programi për renditjen me flluska

``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) ``` 

Outputi

Kompleksiteti kohor i llojit të flluskave

  • Rasti më i keq: Kompleksiteti më i keq kohor për renditjen me flluskë është O( n 2).
  • Rasti mesatar: Kompleksiteti kohor mesatar për renditjen me flluskë është O( n 2).
  • Rasti më i mirë: Kompleksiteti më i mirë kohor për renditjen me flluskë është O(n).

Avantazhet

  • Përdoret më së shumti dhe është i lehtë për t'u zbatuar.
  • Ne mund të ndërrojmë elementët e të dhënave pa konsumim të ruajtjes afatshkurtër.
  • Kërkon më pak hapësirë.

Disavantazhet

  • Nuk funksionoi mirë ndërsa merrej me një numër të madh elementësh të mëdhenj të të dhënave.
  • Ai nevojiten n 2 hapa për secilin numër "n" të elementeve të të dhënave për t'u renditur.
  • Nuk është vërtet i mirë për aplikacionet e botës reale.

Futja Renditja

Renditja e futjes është një teknikë e lehtë dhe e thjeshtë klasifikimi që funksionon ngjashëm me renditjen e letrave të lojës. Renditja e futjes i rendit elementet duke krahasuar secilin element një nga një me tjetrin. Elementet zgjidhen dhe këmbehen me elementin tjetër nëse elementi është më i madh ose më i vogël se tjetri.

Le të marrim një shembull

  • Na sigurohet një grup që ka elementet " 100, 50, 30, 40, 10 ".
  • Së pari, ne rregullojmë grupin dhe fillojmë të krahasojmëit.
  • Në hapin e parë “ 100 ” krahasohet me elementin e dytë “ 50 ”. " 50 " këmbehet me " 100 " pasi është më i madh.
  • Në hapin e dytë, përsëri elementi i dytë " 100 " krahasohet me elementin e tretë " 30 " dhe këmbehet.
  • Tani, nëse vëreni se "30" vjen në vend të parë sepse është përsëri më i vogël se "50".
  • Krahasimi do të ndodhë deri në elementin e fundit të një grupi dhe në fund, do të marrim të dhëna të renditura.

Programi për renditjen e futjes

``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j >= 0 and key_value  array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print ("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i]) ``` 

Output

Kompleksiteti kohor i renditjes së futjes

  • Rasti më i keq: Kompleksiteti më i keq kohor për renditjen e futjes është O( n 2).
  • Rasti mesatar: Kompleksiteti mesatar i kohës për renditjen e futjes është O( n 2).
  • Rasti më i mirë: Kompleksiteti më i mirë kohor për renditjen e futjes është O(n).

Përparësitë

  • Është e thjeshtë dhe i lehtë për t'u zbatuar.
  • Performon mirë kur merret me një numër të vogël elementesh të dhënash.
  • Nuk ka nevojë për më shumë hapësirë ​​për zbatimin e tij.

Disavantazhet

  • Nuk është e dobishme të renditësh një numër të madh elementesh të dhënash.
  • Kur krahasohet me teknikat e tjera të renditjes, ajo nuk funksionon mirë.
  • 16>

    Merge sort

    Kjo metodë klasifikimi përdor metodën divide and conquer për të renditur elementet në një rend të caktuar. Gjatë renditjes me ndihmën e merge sort, theelementët ndahen në gjysma dhe më pas, ato renditen. Pas renditjes së të gjitha gjysmave, përsëri elementët bashkohen për të formuar një renditje të përsosur.

    Le të marrim një shembull për të kuptuar këtë teknikë

    • Ne jemi të pajisur me një grup "7, 3, 40, 10, 20, 15, 6, 5". Vargu përmban 7 elemente. Nëse e ndajmë në gjysmë ( 0 + 7 / 2 = 3 ).
    • Në hapin e dytë, do të shihni se elementët ndahen në dy pjesë. Secili ka 4 elementë në të.
    • Më tej, elementët ndahen përsëri dhe kanë nga 2 elementë secili.
    • Ky proces do të vazhdojë derisa vetëm një element të jetë i pranishëm në një grup. Referojuni hapit nr. 4 në figurë.
    • Tani, ne do t'i renditim elementët dhe do të fillojmë t'i bashkojmë siç u ndamë.
    • Në hapin nr. 5 nëse vëreni 7 është më i madh se 3, kështu që ne do t'i shkëmbejmë ato dhe do t'i bashkojmë në hapin tjetër dhe anasjelltas.
    • Në fund, do të vini re se grupi ynë po renditet në rend rritës.

    Programi për renditjen e bashkimit

    ``` def MergeSort(arr): if len(arr) > 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i  len(L) and j  len(R): if L[i]  R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i  len(L): arr[k] = L[i] i += 1 k += 1 while j  len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i in range(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ``` 

    Outputi

    Kompleksiteti kohor i renditjes së bashkimit

    • Rasti më i keq: Kompleksiteti më i keq kohor për renditjen e bashkimit është O( n log( n )).
    • Rasti mesatar: Kompleksiteti mesatar i kohës për renditjen e bashkimit është O( n log( n )).
    • Rasti më i mirë: Kompleksiteti më i mirë kohor për renditjen e bashkimit është O( n log( n )).

    Përparësitë

    • Madhësia e skedarit nuk ka rëndësi për këtë teknikë renditjeje.
    • Kjo teknikë është e mirë për të dhënat të cilat përgjithësisht arrihen sipas renditjes. Për shembull, listat e lidhura, kasetë, etj.

    Disavantazhet

    • Kërkon më shumë hapësirë ​​në krahasim me të tjerat teknikat e renditjes.
    • Është relativisht më pak efikase se të tjerat.

    Renditja e shpejtë

    Rregullimi i shpejtë përdor përsëri metodën përça dhe sundo për të renditur elementet e një liste ose një grup. Ai synon elementet kryesore dhe i rendit elementet sipas elementit të zgjedhur të strumbullarit.

    Për shembull

    • Na sigurohet një grup me elementet “ 1 ,8,3,9,4,5,7 ".
    • Le të supozojmë se "7" është një element pilot.
    • Tani do ta ndajmë grupin në atë mënyrë që ana e majtë përmban elementet që janë më të vegjël se elementi strumbullar " 7 " dhe ana e djathtë përmban elementet më të mëdhenj se elementi strumbullar " 7 ".
    • Tani kemi dy vargje " 1,3,4,5 " dhe " 8, 9 ".
    • Përsëri, ne duhet t'i ndajmë të dy vargjet njësoj si më sipër. Dallimi i vetëm është se elementët e rrotullimit ndryshojnë.
    • Ne duhet t'i ndajmë vargjet derisa të marrim elementin e vetëm në grup.
    • Në fund, mblidhni të gjithë elementët e rrotullimit në një sekuencë nga e majta në të djathtë dhe ju do të merrni të rendituragrup.

    Programi për renditje të shpejtë

    ``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] = pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, lowest, highest ): if len( arr ) == 1: return arr if lowest  highest: pi = Array_Partition( arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ``` 

    Output

    Kompleksiteti kohor i renditjes së shpejtë

    • Rasti më i keq: Kompleksiteti më i keq kohor për renditjen e shpejtë është O( n 2).
    • Rasti mesatar: Kompleksiteti mesatar kohor për renditjen e shpejtë është O( n log( n ) ).
    • Rasti më i mirë: Kompleksiteti më i mirë kohor për renditjen e shpejtë është O( n log( n )).

    Avantazhet

    • Njihet si algoritmi më i mirë i renditjes në Python.
    • Është i dobishëm gjatë trajtimit të sasive të mëdha të të dhënave.
    • Nuk kërkon hapësirë ​​shtesë.

    Disavantazhet

    • Kompleksiteti i tij në rastin më të keq është i ngjashëm me kompleksitetin e llojit flluskë dhe renditja e futjes.
    • Kjo metodë renditjeje nuk është e dobishme kur tashmë e kemi listën e renditur.

    Renditja e grumbullit

    Renditja e grumbullit është versioni i avancuar i pemës së kërkimit binar . Në renditjen e grumbullit, elementi më i madh i një vargu vendoset në rrënjën e pemës gjithmonë dhe më pas, krahasuar me rrënjën me nyjet e gjetheve.

    Për shembull:

    • Na sigurohet një grup me elementet “ 40, 100, 30, 50, 10 ”.
    • “ hapin 1 ” ne bëmë një pemë sipas prania e elementeve në grup.

    • Në " hapi 2 " ne po bëjmë një grumbull maksimal, d.m.th. për të rregulluar elementet në rend zbritës. Elementi më i madh doqëndron në krye (rrënja) dhe elementi më i vogël ndodhet në fund (nyjet e gjetheve). Vargu i dhënë bëhet " 100, 50, 30, 40, 10 ".

    • “ hapin 3 " , ne po bëjnë grumbullin minimal në mënyrë që të gjejmë elementet minimale të një grupi. Duke bërë këtë, marrim elementet maksimale dhe minimale.

    • “ hapin 4 ” duke kryer të njëjtat hapa marrim grupin e renditur.

    Programi për renditjen e grumbullit

    ``` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left  n and arr[ larger_element ]  arr[ left ]: larger_element = left if right  n and arr[ larger_element ]  arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ] HeapSortify( arr, n, larger_element ) def HeapSort( arr ): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by the Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ``` 

    Outputi

    Kompleksiteti kohor i renditjes së grumbullit

    • Rasti më i keq: Kompleksiteti më i keq kohor për llojin e grumbullit është O( n log( n )).
    • Rasti mesatar: Kompleksiteti mesatar kohor për renditjen e grumbullit është O( n log( n )).
    • Rasti më i mirë: Kompleksiteti më i mirë kohor për renditjen e grumbullit ështëO( n log( n )).

    Përparësitë

    • Përdoret më së shumti për shkak të produktivitetit të tij.
    • Mund të zbatohet si një algoritëm në vend.
    • Nuk kërkon hapësirë ​​të madhe ruajtjeje.

    Disavantazhet

    • Ka nevojë për hapësirë ​​për renditja e elementeve.
    • E bën pemën për renditjen e elementeve.

    Krahasimi ndërmjet teknikave të renditjes

    Metoda e renditjes Kompleksiteti më i mirë kohor Kompleksiteti mesatar i rastit në kohë Kompleksiteti i rastit më të keq Kompleksiteti i hapësirës Stabiliteti Në -
Lëviz në Krye