Problem:


バブルソート

データを並べ替えるための整列（ソート）アルゴリズムはコンピュータ科学には欠かせない基本的なアルゴリズムです。例えば、下図のように「整数値の配列の要素を昇順に並べ替える」という操作が整列です。

多くの整列アルゴリズムが考案されてきましたが、その中でも基本的なアルゴリズムの１つがバブルソートです。例として、与えられた整数値の配列をバブルソートで昇順に並べてみます。

バブルソートでは、各計算ステップにおいて、配列を「ソートされた部分」と「ソートされていない部分」に分けて考えます。最初は配列全体がソートされていない部分になります。

ソートされていない部分の先頭から、隣同士の要素を比較して（図では緑色の要素）、大きい値が右にくるようにそれらを交換します。二つの値が等しい場合は交換しません。

この処理をソートされていない部分（図では白色の要素）の末尾まで繰り返します。最後に、末尾をソートされている部分（図では青色の要素）に追加して1ステップが完了します。

このステップをソートされていない部分の長さが1になるまで繰り返します。

このようにソートされていない部分の長さが 1 になったら、ソートの処理を終了します。

それでは、n 個の数値の配列を入力とし、数値が配列の先頭から昇順に並ぶように上記のバブルソートの手順で並べ替えを行い、要した配列要素の交換回数を出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットは以下の形式で与えられます。

n
a1
a2
:
an

１行目に数値の数 n (1 ≤ n ≤ 100)、続く n 行にi  番目の数値 ai (1 ≤ ai ≤ 1000000) が与えられます。

データセットの数は 20 を超えません。

Output

データセットごとにデータ要素の交換回数（整数）を１行に出力します。

Sample Input

5
5
3
2
1
4
6
1
2
3
4
5
6
3
3
2
1
0

Output for the Sample Input

7
0
3



Sample input:
5
5
3
2
1
4
6
1
2
3
4
5
6
3
3
2
1
0


Sample output:
7
0
3

Submission status: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n==0: break
    a = [input() for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(n)[:0:-1]:
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
                count+=1
    print(count)

Submission status: Wrong Answer

Solution code:
ans = []
while True:
    n = int(input())
    if n==0: break
    a = [input() for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(n)[:0:-1]:
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
                count+=1
    ans.append(count)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def merge(A):
    n = len(A)
    if(n < 2):
        return 0
    ret = 0
    L = A[:n/2]
    R = A[n/2:]
    ret += merge(L)
    ret += merge(R)
    for i in xrange(n):
        if len(L) == 0:
            A[i] = R.pop(0)
        elif len(R) == 0 or L[0] < R[0]:
            A[i] = L.pop(0)
        else:
            ret += len(L)
            A[i] = R.pop(0)
    return ret

while True:
    n = int(raw_input())
    if n == 0:
        break
    print merge([int(raw_input()) for _ in xrange(n)])

Submission status: Accepted

Solution code:
while 1:
  n = input()
  if n==0: break
  x = [int(raw_input()) for _ in [0]*n]
  c = 0
  for i in range(n):
    for j in range(i+1,n)[::-1]:
      if x[j] < x[j-1]:
        x[j], x[j-1] = x[j-1], x[j]
        c += 1
  print c

Submission status: Accepted

Solution code:
while True:
    N = input()
    if N == 0: break
    L = [input() for i in range(N)]
    c = 0
    for i in range(len(L[:])-1):
        for i in range(len(L)-1):
            if L[i] > L[i+1]:
                L[i], L[i+1] = L[i+1], L[i]
                c += 1
        else:
            del L[-1]
    else:
        print c

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    Num_lis = []
    cou = 0
    for i in range(n):
        Num_lis.append(int(input()))
    S_lis = sorted(Num_lis)
    while Num_lis != S_lis:
        
        for j in range(n - 1):
            if Num_lis[j] > Num_lis[j + 1]:
                Num_lis[j],Num_lis[j + 1] = Num_lis[j + 1],Num_lis[j]
                cou += 1
    print(cou)

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n==0: break
    a = [int(input()) for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(n)[:0:-1]:
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
                count+=1
    print(count)

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if n==0:break
    c=0
    a=[int(input()) for _ in range(n)]
    for i in range(n):
        for j in range(n-1,0,-1):
            if a[j]<a[j-1]:c,(a[j],a[j-1])=c+1,(a[j-1],a[j])
    print(c)

Submission status: Accepted

Solution code:
def bs(v):
    nc = 0
    m = len(v)
    while m > 0:
        j=0 
        while j < m-1:
            if v[j] > v[j+1]:
                x = v[j+1]
                v[j+1] = v[j]
                v[j] = x
                nc += 1
            j += 1
        m -= 1
    return(nc)

while True:
    n = int(input())
    if n==0:
        break
    v = []    
    for _ in range(n):
        x = int(input())
        v.append(x)

    print(bs(v))

Submission status: Accepted

Solution code:
# Aizu Problem 00167: Bubble Sort
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def bubble_sort(N, A):
    cnt = 0
    last = N - 1
    while last > 0:
        for k in range(last):
            if A[k] > A[k+1]:
                A[k], A[k+1] = A[k+1], A[k]
                cnt += 1
        last -= 1
    return cnt


while True:
    N = int(input())
    if N == 0:
        break
    A = [int(input()) for _ in range(N)]
    print(bubble_sort(N, A))

Submission status: Accepted

Solution code:
def bubble_sort(A, N):
    flag = True
    c = 0
    i = 0
    while flag:
        flag = 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]
                c += 1
                flag = True
        i += 1

    return c


while True:

    N = int(raw_input())

    if N == 0:
        break

    A = [int(raw_input()) for _ in xrange(N)]

    print bubble_sort(A, N)

Submission status: Accepted

Solution code:
def bubble_sort(A, N):
    flag = True
    i, c = 0, 0
    while flag:
        flag = False
        for j in range(1, N-i):
              if A[j] < A[j-1]:
                  A[j],  A[j-1] = A[j-1], A[j]
                  flag = True
                  c += 1
        i += 1

    return c


while True:

    N = int(raw_input())

    if N == 0:
        break

    A = [int(raw_input()) for _ in xrange(N)]

    print bubble_sort(A, N)

Submission status: Accepted

Solution code:
# coding: utf-8

import math
import fractions
import heapq
import collections
import re
import array
import bisect

from collections import Counter, defaultdict


class BIT(object):
    """Bibary Indexed Tree / Fenwick Tree"""
    # 1-indexed
    def __init__(self, size):
        self.size = size
        self.l = [0] * (size + 1)

    def sum(self, i):
        r = 0
        while i > 0:
            r += self.l[i]
            i -= i & -i
        return r

    def add(self, i, x):
        while i <= self.size:
            self.l[i] += x
            i += i & -i


max_a = 1000000


def solve(a):
    bit = BIT(max_a)
    ans = 0
    for i, x in enumerate(a):
        ans += i - bit.sum(x)
        bit.add(x, 1)
    return ans


def main():
    while True:
        N = int(input())
        if N == 0:
            return
        a = []
        for i in range(N):
            a.append(int(input()))
        print(solve(a))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def bubble_sort(item_list):
    length = len(item_list)
    count = 0

    for lp in range(length):
        for lp2 in range(length - lp - 1):
            if item_list[lp2] > item_list[lp2 + 1]:
                tmp = item_list[lp2]
                item_list[lp2] = item_list[lp2 + 1]
                item_list[lp2 + 1] = tmp
                count += 1

    return count


while True:

    input_count = int(input())

    if input_count == 0:
        break

    data = [int(input()) for _ in range(input_count)]

    result = bubble_sort(data)
    print(result)

Submission status: Accepted

Solution code:
while True:
    N = int(input())
    if N == 0:
        break

    a = []
    cnt = 0
    for l in range(N):
        a.append(int(input()))
    for i in range(N-1, 0, -1):
        for j in range(i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                cnt += 1

    print(cnt)

Submission status: Accepted

Solution code:
# AOJ 0167 Bubble Sort
# Python3 2018.6.20 bal4u

while True:
	n = int(input())
	if n == 0: break
	a = [0]*105
	for i in range(n): a[i] = int(input())
	cnt = 0
	for i in range(n-1, 0, -1):
		for j in range(i):
			if a[j] > a[j+1]:
				cnt += 1
				a[j], a[j+1] = a[j+1], a[j]
	print(cnt)

Submission status: Accepted

Solution code:
def b_sort(lst):
  limit = len(lst) - 1
  cnt = 0
  while limit:
    for i in range(limit):
      if lst[i] > lst[i + 1]:
        lst[i], lst[i + 1] = lst[i + 1], lst[i]
        cnt += 1
    limit -= 1
  return cnt

while True:
  n = int(input())
  if n == 0:
    break
  alst = []
  for _ in range(n):
    alst.append(int(input()))
  print(b_sort(alst))

Submission status: Accepted

Solution code:
def BubbleSort(L):
    global cnt
    for i in range(len(L)-1):
        if L[i]>L[i+1]:
            L[i],L[i+1]=L[i+1],L[i]
            cnt+=1
while True:
    n=input()
    if n==0:break
    L,cnt=[],0
    for i in range(n):
        L.append(input())

    for i in range(len(L),0,-1):
        BubbleSort(L)
    print cnt

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n==0:break
    cnt=0
    L=[input() for i in range(n)]
    for j in range(n):
        for i in range(n-j-1):
            if L[i]>L[i+1]:
                L[i],L[i+1]=L[i+1],L[i]
                cnt+=1
    print cnt

Submission status: Accepted

Solution code:
while 1:
    n = input(); ans = 0;
    if n==0: break
    s = [input() for i in range(n)]
    for i in range(n):
        for j in range(n-i-1):
            if s[j+1]<s[j]:
                s[j],s[j+1]=s[j+1],s[j]
                ans += 1
    print ans

Submission status: Accepted

Solution code:
def merge(A):
    n = len(A)
    if(n < 2):
        return 0
    ret = 0
    L = A[:n/2]
    R = A[n/2:]
    ret += merge(L)
    ret += merge(R)
    for i in xrange(n):
        if len(L) == 0:
            A[i] = R.pop(0)
        elif len(R) == 0 or L[0] <= R[0]:
            A[i] = L.pop(0)
        else:
            ret += len(L)
            A[i] = R.pop(0)
    return ret

while True:
    n = int(raw_input())
    if n == 0:
        break
    print merge([int(raw_input()) for _ in xrange(n)])

Submission status: Accepted

Solution code:
def buble(a):
    c = 0
    for i in range(n):
        for j in range(n-1,i,-1):
            if int(a[j]) < int(a[j-1]):
                a[j],a[j-1] = a[j-1],a[j]
                c += 1
    return c
    
while True:
	n = int(raw_input())
	if n == 0: break
	a = [int(raw_input()) for i in range(n)]
	print buble(a)

Submission status: Accepted

Solution code:
while True:
  N, M, C = input(), [], 0
  if not N:
    break
  for i in range(N):
    M.append(input())
  for p in range(N)[::-1]:
    for i in range(p):
      if M[i] > M[i + 1]:
        M[i], M[i + 1] = M[i + 1], M[i]
        C += 1
  print(C)

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    L=[]
    for _ in range(n):
        L.append(int(input()))

    cnt = 0
    for k in range(1,len(L))[::-1]:
        for i in range(k):
            if L[i+1] < L[i]:
                cnt += 1
                L[i+1], L[i] = L[i], L[i+1]
    print(cnt)

Submission status: Accepted

Solution code:
while True:
  n =int(input())
  A=[]
  if n==0:
    break
  for i in range(n):
    num =int(input())
    A.append(num)
  cnt=0  
  for i in range(n):
    for j in range(n-1, 0, -1):
      if A[j]<A[j-1]:
        A[j], A[j-1]=A[j-1],A[j]
        cnt+=1
  print(cnt)

Submission status: Accepted

Solution code:
def bubbleSort(list):
  j = len(list) - 1
  bcnt = 0
  while j:
    for i in range(j):
      if list[i] > list[i + 1]:
        list[i], list[i + 1] = list[i + 1], list[i]
        bcnt += 1
    j -= 1
  return bcnt
 
while True:
  n = int(input())
  if n == 0:
    break
  A = []
  for _ in range(n):
    A.append(int(input()))
  print(bubbleSort(A))

Submission status: Accepted

Solution code:
def solve(A):
    res = 0
    right = len(A)
    while right != 0:
        for left in range(0, right):
            if left + 1 < len(A) and A[left] > A[left + 1]:
                A[left], A[left + 1] = A[left + 1], A[left]
                res += 1
        right -= 1
    return res

while True:
    n = int(input())
    if n == 0 : break
    A = [int(input()) for i in range(n)]
    print(solve(A))

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break

    alist = []
    for _ in range(n):
        a = int(input())
        alist.append(a)

    cnt = 0
    for i in range(len(alist)):
        for j in range(len(alist)-1, i, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]
                cnt += 1

    print(cnt)

Submission status: Accepted

Solution code:
def bubble_sort(n):
    arr = [int(input()) for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(n-1, i, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
                cnt += 1
    return cnt

while True:
    n = int(input())
    if n == 0: break
    print(bubble_sort(n))

Submission status: Runtime Error

Solution code:
def bubble_sort(A, N):
    flag = True
    c = 0
    i = 0
    while flag:
        flag = 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]
                c += 1
                flag = True
        i += 1

    return c


while True:

    N = int(raw_input())

    if N == 0:
        break
    
    A = [map(int, raw_input()) _ for i in range(N)]

    print bubble_sort(A, N)