Introduction

Hello. It's chewy and chewy. We will solve the introduction to AOJ's algorithms and data structures. It's easy to keep a record of what you've learned.

It's been less than half a year since I started programming myself AtCoder is green, so I'm not a strong man. Let's work hard together.

Kyapee

This time PART2: Elementary sort. I want to do my best and do it to the end.

ALDS1_2_A: Bubble sort ALDS1_2_B: Selection sort ALDS1_2_C: Stable sorting ALDS1_2_D: Shellsort

ALDS1_2_A: Bubble sort

Bubble sort

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: Selection sort

 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: Stable sorting

Save as tuple so as not to change the original list Judgment of stability is an exploratory thinking

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: Shellsort

It's difficult ...



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)