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