Tri rapide d'un tableau en Python 3

Introduction

Bonne année 2020 à tous. Mon nom est ryuichi69.
J'ai écrit cette phrase aujourd'hui après avoir pratiqué la sortie et l'explication de l'algorithme. Pour être honnête, il est difficile d'écrire d'une manière facile à comprendre.

Tri rapide

Présentation

Premièrement, le tri consiste à trier les éléments d'un tableau par ordre croissant ou décroissant. Il existe de nombreux types de méthodes de tri

, mais le tri rapide est basé sur la valeur de référence du tableau et est divisé en séquences de plus en plus petites. C'est une méthode pour aller .

Exemple de tri rapide

Par exemple, il existe un tableau a = [5,6,3,1,8], et envisagez de le trier rapidement par ordre croissant. De plus, la valeur médiane du tableau est utilisée comme valeur de référence.

Ici, la valeur médiane des éléments du tableau a est 3. Avec ce 3 comme limite, les éléments plus petits que 3 sont divisés en deux en deux, comme le bleu en dessous et les éléments plus grands que 3 sont divisés en jaune en dessous. En outre, comme indiqué dans la deuxième division de la figure ci-dessous, le tableau est divisé de manière récursive en deux et la récurrence est arrêtée lorsque le nombre d'éléments du tableau devient un. Enfin, il est complété par l'intégration dans un seul tableau.

sort.png

Voici un résumé de la procédure de mise en œuvre.

Procédure de mise en œuvre
  1. Trouvez la médiane m (valeur de référence) de l'élément e dans le tableau a [i].
  2. Lorsque le nombre d'éléments dans le tableau après la division devient un, écrivez un processus pour arrêter la récurrence (condition d'arrêt de récursivité).
  3. Pour chaque élément élément du tableau. Si a [i] m, stockez l'élément dans le tableau à droite.
  4. Exécutez les 1 et 2 ci-dessus de manière récursive pour le tableau de gauche et le tableau de droite.

    Exemple Soit

    n un entier naturel et i un entier satisfaisant 0 ≤ i ≤ (n-1). À ce stade, utilisez le tri rapide pour trier le tableau a [i] avec n éléments par ordre croissant.

    Contraintes
    1. 1≦n≦10
    2. 1≦a[i]≦10
    Entrée

    a = [7,3,10,5,9,1,6,4,8,2]

    Sortie

    [1,2,3,4,5,6,7,8,9,10]

    Programme

    Le code source est " algorithme de tri et implémentation en Python --Qiita de @ suecharo" Il est basé sur le type rapide de ". Je ne savais pas comment diviser le tableau en deux parties et les trier, alors j'ai décidé de le faire.

    quickSort.py

    
import os
import statistics

def quickSort(arr):

    #Un tableau d'éléments plus petit que la médiane du tableau
    left = []

    #Un tableau d'éléments plus grand que la médiane du tableau
    right = []

    #Condition d'arrêt de récidive
    #Arrêter lorsque le nombre d'éléments devient 1 ou moins après la division récursive du tableau
    if len(arr) <= 1:
        return arr

    #Valeur médiane du tableau(Médian)Obtenir
    median = int(statistics.median(arr))

    #Une variable pour compter le nombre de valeurs médianes contenues dans un tableau
    medianFlg = 0

    for element in arr:
        #Éléments du tableau(element)Est inférieur à la médiane
        #Stocker la valeur dans le tableau à gauche
        if element < median:
            left.append(element)
        #Éléments du tableau(element)Est supérieur à la médiane
        #Stocker les valeurs dans le tableau à droite
        elif element > median:
            right.append(element)
        else:
        #Si l'élément est la valeur médiane du tableau
        #Indicateurs pour le nombre de valeurs médianes ajoutées à la valeur de retour+1 Continuer
            medianFlg += 1

    #Si vous voulez voir comment le tableau est divisé,
    #Il est bon de vérifier avec l'impression à ce moment
    # print(left)
    # print(right)

    #Effectuer une récurrence pour chaque tableau à gauche et à droite
    #Divisez le tableau en tableaux plus petits
    left = quickSort(left)
    right = quickSort(right)

    #Tableau gauche, médian[median], Renvoie une concaténation du tableau à droite
    return left + [median] * medianFlg + right

#pour le test
if __name__ == "__main__":

    print(quickSort([7,3,10,5,9,1,6,4,8,2]))

    Recommended Posts