Résolution de l'introduction d'AOJ aux algorithmes et aux structures de données en Python -Partie2-

introduction

Bonjour. C'est moelleux et moelleux. Nous résoudrons l'introduction aux algorithmes et aux structures de données d'AOJ. Il est facile de garder une trace de ce que vous avez appris.

Cela fait moins d'un an et demi que j'ai commencé à toucher la programmation moi-même AtCoder est vert, donc je ne suis pas un homme fort. Travaillons dur ensemble.

Kyapee

table des matières

Cette fois, c'est PART2: Tri élémentaire. Je veux faire de mon mieux et le faire jusqu'au bout.

ALDS1_2_A: Tri à bulles ALDS1_2_B: tri sélectif ALDS1_2_C: tri stable ALDS1_2_D: tri Shell

ALDS1_2_A: Tri à bulles

Tri à bulles

def bubbleSort(A, N):
    bit = True
    i = 0
    count = 0
    while bit:
        bit = False
        for j in range(n-1,i,-1):
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]
                count += 1
                bit = True
    
    return A , count
        

n = int(input())
A = list(map(int,input().split()))

A,count = bubbleSort(A,n)
print(*A)
print(count)

ALDS1_2_B: tri sélectif

 def SelectionSort(A,n):
    count = 0
    for i in range(n):
        minv = i
        for j in range(i,n):
            if A[j] < A[minv]:
                minv = j
        
        A[i],A[minv] = A[minv],A[i]
        if i!=minv:
            count += 1

    return A,count

n = int(input())
A = list(map(int,input().split()))

A1,count1 = SelectionSort(A,n)

print(*A1)
print(count1)

ALDS1_2_C: tri stable

Enregistrer en tant que tuple pour ne pas modifier la liste d'origine Le jugement de stabilité est une réflexion exploratoire

def bubbleSort(A, N):
    A = list(A)
    bit = True
    i = 0
    while bit:
        bit = False
        for j in range(n-1,i,-1):
            if int(A[j][1]) < int(A[j-1][1]):
                A[j],A[j-1] = A[j-1],A[j]
                bit = True
    
    return A 

def SelectionSort(A,n):
    A = list(A)
    for i in range(n):
        minv = i
        for j in range(i,n):
            if int(A[j][1]) < int(A[minv][1]):
                minv = j
        
        A[i],A[minv] = A[minv],A[i]

    return A

def is_stable(A_in, A_out):
    n = len(A_in)
    for i in range(n):
        for j in range(i+1,n):
            for a in range(n):
                for b in range(a+1,n):
                    if A_in[i][1] == A_in[j][1] and A_in[i]==A_out[b] and A_in[j]==A_out[a]:
                        return "Not stable"
    return "Stable"

n = int(input())
A = list(input().split())
A_ans = tuple(A)

A1 = bubbleSort(A_ans,n)
print(*A1)
print(is_stable(A_ans, A1))

A2 = SelectionSort(A_ans,n)
print(*A2)
print(is_stable(A_ans, A2))

ALDS1_2_D: tri Shell

C'est difficile ...

def insertionSort(A,n,g):
    global count
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j]>v:
            A[j+g] = A[j]
            j -= g
            count += 1
        A[j+g] = v



def ShellSort(A, n):
    global count
    count = 0
    g = 1
    G = [g]
    while 3 * g + 1 < n:
        g = 3 * g + 1
        G.append(g)
    m = len(G)
    G = G[::-1]
    
    print(m)
    print(*G)

    for j in G:
        insertionSort(A,n,j)



n = int(input())
A = []
for i in range(n):
    a = int(input())
    A.append(a)

ShellSort(A, n)
print(count)

for i in A:
    print(i)

en conclusion

Si vous avez une mauvaise réponse, veuillez contacter Goto

p.s.p Qitta je n'ai jamais reçu de gentil garçon Nous attendons avec impatience les premiers parents mémorables. ↑ Je l'ai écrit la dernière fois, mais je le loue