Aprende a usar a función Python Sort para ordenar listas, matrices, dicionarios, etc. usando varios métodos e algoritmos de ordenación en Python:
A clasificación é unha técnica que se usa para ordenar os datos nunha orde secuencial, xa sexa en orde ascendente ou descendente.
A maioría das veces os datos dos grandes proxectos non están dispostos na orde correcta e isto xera problemas ao acceder e obter os datos necesarios de forma eficiente.
Utilízanse técnicas de clasificación para resolver este problema. Python ofrece varias técnicas de ordenación por exemplo, Clasificación por burbulla, Ordenación por inserción, Ordenación por combinación, Clasificación rápida, etc.
Neste tutorial, entenderemos como funciona a ordenación en Python mediante varios algoritmos.
Python Sort
Sintaxe de Python Sort
Para realizar a clasificación, Python proporciona a función integrada, é dicir, a función “sort()”. Úsase para ordenar os elementos de datos dunha lista en orde ascendente ou descendente.
Entendemos este concepto cun exemplo.
Exemplo 1:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ```
Saída:
Neste exemplo, a lista non ordenada dada ordénase en orde ascendente mediante a función “sort() ” .
Exemplo 2:
``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ```
Saída
No exemplo anterior, a lista non ordenada dada ordénase na orde inversa usando a función “ sort( reverse = True ) ”.
Tempolugar Ordenación de burbulla O(n) O(n2) O(n2) O(1) Si Si Ordenación por inserción O(n) O(n2) O(n2) O(1) Si Si Ordenación rápida O(n log(n)) O(n log(n)) O(n2) O(N) Non Si Combinar ordenar O(n log(n)) O(n log(n)) O(n log(n)) O(N) Si Non Clasificación de pila O(n log (n)) O(n log(n)) O(n log(n)) O(1) Non Si
Na táboa de comparación anterior " O " é a notación Big Oh explicada anteriormente, mentres que " n " e " N " significan o tamaño da entrada .
Preguntas frecuentes
P #1) Que é ordenar () en Python?
Resposta: En Python sort() é unha función que se usa para ordenar as listas ou matrices nunha orde específica. Esta función facilita o proceso de clasificación mentres se traballa nos grandes proxectos. É moi útil para os desenvolvedores.
P #2) Como ordenas en Python?
Resposta: Python ofrece varias técnicas de clasificación que se usan para ordenar o elemento. Por exemplo, Ordenación rápida, Ordenación por combinación, Ordenación por burbulla, Ordenación por inserción, etc. Todas as técnicas de clasificación son eficientes e fáciles de entender.
P #3) Como funciona Python ordenar () traballar?
Resposta: O sort()A función toma a matriz dada como entrada do usuario e ordénaa nunha orde específica usando o algoritmo de clasificación. A selección do algoritmo depende da elección do usuario. Os usuarios poden usar Ordenación rápida, Ordenación por combinación, Ordenación por burbulla, Ordenación por inserción, etc., dependendo das necesidades do usuario.
Conclusión
No tutorial anterior, comentamos a técnica de ordenación en Python xunto co técnicas xerais de clasificación.
- Clasificación de burbulla
- Clasificación por inserción
- Clasificación rápida
Aprendemos sobre as súas complexidades e vantaxes de tempo & desvantaxes. Tamén comparamos todas as técnicas anteriores.
Complexidade dos algoritmos de clasificaciónTempo A complexidade é a cantidade de tempo que tarda o ordenador en executar un determinado algoritmo. Ten tres tipos de casos de complexidade temporal.
- O peor dos casos: Tempo máximo que tarda o ordenador en executar o programa.
- Caso medio: Tempo que tarda o ordenador entre o mínimo e o máximo en executar o programa.
- O mellor dos casos: Tempo mínimo que tarda o ordenador en executar o programa. É o mellor caso de complexidade temporal.
Notacións de complexidade
Notación Big Oh, O: A notación Big Oh é a forma oficial de transmitir o límite superior do tempo de execución dos algoritmos. Úsase para medir a complexidade do tempo no peor dos casos ou dicimos a maior cantidade de tempo que tarda o algoritmo en completarse.
Notación omega grande, : A notación omega grande é a forma oficial de transmitir o límite inferior do tempo de execución dos algoritmos. Úsase para medir a complexidade do tempo no mellor dos casos ou dicimos a excelente cantidade de tempo que leva o algoritmo.
Notación Theta, : A notación Theta é a forma oficial de transmitir ambos os límites, é dicir, o inferior e o superior do tempo que tarda o algoritmo en completarse.
Métodos de ordenación en Python
Clasificación de burbulla
A ordenación de burbulla é a forma máis sinxela de ordenar os datos que utiliza a técnica da forza bruta. Iterará a cada elemento de datos e comparará con outros elementospara proporcionar ao usuario os datos ordenados.
Poñamos un exemplo para comprender esta técnica:
- Proporcionamos unha matriz que ten os elementos “ 10, 40, 7, 3, 15”. Agora, necesitamos organizar esta matriz nunha orde ascendente usando a técnica de ordenación de burbulla en Python.
- O primeiro paso é organizar a matriz na orde indicada.
- Na " Iteración 1 ", estamos comparando o primeiro elemento dunha matriz cos outros elementos un por un.
- As frechas vermellas describen a comparación dos primeiros elementos cos outros elementos dunha matriz.
- Se observas que "10" é menor que "40", polo que permanecerá igual. lugar pero o seguinte elemento " 7 " é menor que " 10 ". Polo tanto, substitúese e pasa ao primeiro lugar.
- O proceso anterior realizarase unha e outra vez para ordenar os elementos.
-
- Na “Iteración 2” o segundo elemento está sendo comparado cos outros elementos dunha matriz.
- Se o elemento comparado é pequeno, entón será ser substituído, se non, permanecerá no mesmo lugar.
-
- En " Iteración 3 " o terceiro elemento está sendo comparado cos outros elementos dunha matriz.
-
- No último " Iteración 4 " o penúltimo elemento está sendo comparado cos outros elementos dunha matriz.
- Eneste paso a matriz ordénase en orde ascendente.
Programa para a ordenación de burbullas
``` 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)) ```
Saída
Complejidade do tempo da clasificación da burbulla
- O peor dos casos: A peor complexidade de tempo para a clasificación de burbullas é O( n 2).
- Caso medio: A complexidade de tempo medio para a clasificación de burbullas é O( n 2).
- Mellor caso: A mellor complexidade temporal para a clasificación de burbullas é O(n).
Vantaxes
- Úsase principalmente e é fácil de implementar.
- Podemos intercambiar os elementos de datos sen consumir almacenamento a curto prazo.
- Require menos espazo.
Inconvenientes
- Non funcionou ben ao tratar cunha gran cantidade de elementos de datos grandes.
- É precisa n 2 pasos por cada "n" número de elementos de datos para ordenarse.
- Non é moi bo para aplicacións do mundo real.
Inserción Ordenar
A clasificación por inserción é unha técnica de clasificación sinxela e sinxela que funciona de forma similar á ordenación das cartas. A ordenación por inserción ordena os elementos comparando cada elemento un por un co outro. Os elementos cóllense e intercámbianse co outro elemento se o elemento é maior ou menor que o outro.
Poñamos un exemplo
- Proporcionamos unha matriz que ten os elementos " 100, 50, 30, 40, 10 ".
- Primeiro, organizamos a matriz e comezamos a comparariso.
- No primeiro paso compárase “100” co segundo elemento “50”. " 50 " cámbiase por " 100 " xa que é maior.
- No segundo paso, de novo o segundo elemento "100 " compárase co terceiro elemento " 30 " e intercámbiase.
- Agora, se observas que "30" pasa en primeiro lugar porque volve ser menor que "50".
- A comparación ocorrerá ata o último elemento dunha matriz e ao final, obteremos o datos ordenados.
Programa para ordenar por inserción
``` 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]) ```
Saída
Complexidade temporal da ordenación por inserción
- O peor caso: A peor complexidade temporal para a ordenación por inserción é O( n 2).
- Caso medio: A complexidade media do tempo para a ordenación por inserción é O( n 2).
- Mellor caso: A mellor complexidade temporal para a ordenación por inserción é O(n).
Vantaxes
- É sinxelo e fácil de implementar.
- Funciona ben ao tratar cun pequeno número de elementos de datos.
- Non necesita máis espazo para a súa implementación.
Inconvenientes
- Non é útil ordenar un gran número de elementos de datos.
- En comparación con outras técnicas de clasificación, non funciona ben.
Ordenar por combinación
Este método de ordenación usa o método dividir e vencer para ordenar os elementos nunha orde específica. Mentres se ordena coa axuda de merge sort, oos elementos divídense en metades e, a continuación, clasifícanse. Despois de clasificar todas as metades, de novo os elementos únense para formar unha orde perfecta.
Poñamos un exemplo para entender esta técnica
- Proporcionamos unha matriz "7, 3, 40, 10, 20, 15, 6, 5". A matriz contén 7 elementos. Se o dividimos á metade ( 0 + 7 / 2 = 3 ).
- No segundo paso, verás que os elementos están divididos en dúas partes. Cada un ten 4 elementos.
- Ademais, os elementos volven dividirse e teñen 2 elementos cada un.
- Este proceso continuará ata que só estea presente un elemento nunha matriz. Consulte o paso núm. 4 da imaxe.
- Agora, ordenaremos os elementos e comezaremos a unilos segundo nos dividían.
- No paso núm. 5 se observas que 7 é maior que 3, así que os intercambiaremos e unirémolo no seguinte paso e viceversa.
- Ao final, notarás que a nosa matriz está a ordenarse en orde ascendente.
Programa para ordenar por combinación
``` 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) ```
Saída
Complexidade temporal da ordenación por fusión
- O peor dos casos: A peor complexidade temporal para a ordenación por fusión é O( n log( n )).
- Caso medio: A complexidade media do tempo para a ordenación por fusión é O( n log( n )).
- Mellor caso: A mellor complexidade temporal para a ordenación por fusión é O( n log( n )).
Vantaxes
- O tamaño do ficheiro non importa para esta técnica de clasificación.
- Esta técnica é boa para os datos aos que se accede xeralmente nunha orde de secuencia. Por exemplo, listas vinculadas, unidade de cinta, etc.
Inconvenientes
- Require máis espazo en comparación con outros técnicas de clasificación.
- É comparativamente menos eficiente que outras.
Ordenación rápida
A clasificación rápida usa de novo o método dividir e vencer para ordenar os elementos dunha Lista ou unha matriz. Dirixe os elementos pivotes e ordena os elementos segundo o elemento pivote seleccionado.
Por exemplo
- Proporcionamos unha matriz que ten os elementos “ 1 ,8,3,9,4,5,7 ”.
- Supoñamos que “7 ” é un elemento piloto.
- Agora dividiremos a matriz de tal xeito que o o lado esquerdo contén os elementos que son máis pequenos que o elemento pivote " 7 " e o lado dereito contén os elementos maiores que o elemento pivote " 7 ".
- Agora temos dúas matrices " 1,3,4,5 ". ” e “ 8, 9 ” .
- De novo, temos que dividir as dúas matrices do mesmo xeito que fixemos anteriormente. A única diferenza é que os elementos pivote cambian.
- Necesitamos dividir as matrices ata obter o único elemento na matriz.
- Ao final, recolle todos os elementos pivote nunha matriz. secuencia de esquerda a dereita e obterás o ordenadomatriz.
Programa para a clasificación rápida
``` 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 ] ) ```
Saída
Complexidade temporal da clasificación rápida
- O peor dos casos: A peor complexidade temporal da clasificación rápida é O( n 2).
- Caso medio: A complexidade media do tempo para a clasificación rápida é O( n log( n ) ).
- Mellor caso: A mellor complexidade temporal para a clasificación rápida é O( n log( n )).
Vantaxes
- É coñecido como o mellor algoritmo de clasificación en Python.
- É útil cando se manexa gran cantidade de datos.
- Non require espazo adicional.
Inconvenientes
- A súa complexidade no peor dos casos é semellante á complexidade da clasificación de burbulla e ordenación por inserción.
- Este método de ordenación non é útil cando xa temos a lista ordenada.
Ordenación por montón
Ordenamento por montón é a versión avanzada da árbore de busca binaria . Na ordenación do montón, o elemento máis grande dunha matriz colócase sempre na raíz da árbore e despois, en comparación coa raíz cos nodos da folla.
Por exemplo:
- Proporcionamos unha matriz que ten os elementos " 40, 100, 30, 50, 10 ".
- No " paso 1 " fixemos unha árbore segundo o presenza dos elementos na matriz.
- En “ paso 2 ” estamos facendo un montón máximo, é dicir, para organizar o elementos en orde descendente. O maior elemento seráreside na parte superior (raíz) e o elemento máis pequeno reside na parte inferior (nodos da folla). A matriz dada pasa a ser " 100, 50, 30, 40, 10 ".
- No " paso 3 " , están facendo o montón mínimo para que poidamos atopar os elementos mínimos dunha matriz. Ao facelo, obtemos os elementos máximo e mínimo.
- En “ paso 4 ” realizando os mesmos pasos obtemos a matriz ordenada.
Programa para a ordenación de pilas
``` 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 ] ) ```
Saída
Complexidade temporal da ordenación do montón
- O peor caso: A peor complexidade do tempo para a ordenación do montón é O( n log( n )).
- Caso medio: A complexidade media do tempo para a ordenación do montón é O( n log( n )).
- Mellor caso: A mellor complexidade temporal para a ordenación de pila é O( n log( n )).
Vantaxes
- Utilízase principalmente pola súa produtividade.
- Pode implementarse como un algoritmo no lugar.
- Non precisa de almacenamento grande.
Inconvenientes
- Necesita espazo para ordenando os elementos.
- Fai a árbore para ordenar os elementos.
Comparación entre as técnicas de clasificación
Método de clasificación | Complexidade do tempo do mellor caso | Complexidade do tempo medio do caso | Complexidade do tempo do peor dos casos | Complexidade do espazo | Estabilidade | En - |
---|