AOJ Sort I-

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A

Bubble Sort

op.py


#!/usr/bin/python
i = input()
n = map(int, raw_input().split())
cnt=0

for i in xrange(len(n)):
    for j in xrange(len(n)-1, i, -1):
        if n[j] < n[j-1]:
            n[j], n[j-1] = n[j-1], n[j]
            cnt+=1
print ' '.join(map(str,n))
print cnt

a,b =b,a It's amazing that the values of a and b are swapped.

        if n[j] < n[j-1]:
            n[j], n[j-1] = n[j-1], n[j]

The part of is comparing n [j] specified by for j in ~ with n [j-1] to be checked next. By setting the smaller one to n [j-1], the smallest value in the first lap emerges from the back to the front of the list.

Inner loop first round sample list.py


#6,Compare 8 6 is smaller, so don't replace it.
[2, 5, 3, 1, 7, 9, 10, 4, 6, 8]

#4,Compare 6 4 is smaller, so don't replace it.
[2, 5, 3, 1, 7, 9, 10, 4, 6, 8]

#10,Compare 4 Since 4 is smaller, it has been replaced.
[2, 5, 3, 1, 7, 9, 4, 10, 6, 8]

#9,Compare 4 Since 4 is smaller, it has been replaced.
[2, 5, 3, 1, 7, 4, 9, 10, 6, 8]

#7,Compare 4 Since 4 is smaller, it has been replaced.
[2, 5, 3, 1, 4, 7, 9, 10, 6, 8]

#1,Compare 4 1 is smaller, so don't replace it.
#Change from 4 to 1 and leave.
[2, 5, 3, 1, 4, 7, 9, 10, 6, 8]

#3,Compare 1. Replaced.
[2, 5, 1, 3, 4, 7, 9, 10, 6, 8]

#5,Compare 1. Replaced.
[2, 1, 5, 3, 4, 7, 9, 10, 6, 8]

#2,Compare 1. It has been replaced.
[1, 2, 5, 3, 4, 7, 9, 10, 6, 8]

If there is a smaller number on the way, change to Hoi Hoi and take him to the front. It is guaranteed that the smallest value in the list will be replaced at the front in this first lap (Isn't it?). So on the second lap, the check will be one step before.

Excerpt


for i in xrange(len(n)):
#Every time you go around, the check is up to one point.
#Because it has a smaller value in front.
    for j in xrange(len(n)-1, i, -1):

I tried to stop it in the middle if it seemed to be over


for m in range(len(n)):
    for j in range(len(n)-1, m, -1):
        if n[j]<n[j-1]:
            n[j],n[j-1]=n[j-1],n[j]
            ans+=1
#        print ans
    if ans==chk: break
    chk=ans
print ' '.join(map(str,n))
print ans

I passed all the test cases of Ichio AOJ, but I'm not sure if this is good. Operation is not guaranteed.

AOJ Sort I - Selection Sort

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B

Yes.

op.py


#!/usr/bin/python
# -*- coding: UTF-8 -*-
i = input()
n = map(int, raw_input().split())
cnt=0

#View from the front of the list.
for i in xrange(len(n)):
#Remember the number you are looking at
    min=i
#Initialize flag judgment with 0
    flag=0
#Second and subsequent in the list(i Go to the right to go around)From to the last one
    for j in xrange(i,len(n)):
        if n[j]<n[min]:
#Memorize the order of smaller values.
#If it is in this if, it means that there was a replacement processing candidate, so set a flag.
            min=j
            flag=1
#Swap the value taken for the initial comparison with the smallest value found.
    n[i],n[min]=n[min],n[i]
    cnt+=flag
print ' '.join(map(str,n))
print cnt

Hmmm, False, True also have values of 0 and 1? Are you taking advantage of that?

Recommended Posts

AOJ Sort I-
Insertion sort of AOJ exercises
sort
[AOJ] Descending sort in various languages
Insertion sort
Selection Sort
[Python] Sort
Natural sort
I wrote the selection sort in C
Python # sort
Bubble sort
Bubble sort
I tried to program bubble sort by language
I tried to implement selection sort in python