# -*-coding:utf-8 -*-
import random

def insert_sort(data):
    temp = 0
    for i in range(1,len(data)):
        if data[i] >= data[i-1] :
            continue
        for j in reversed(range(0,i)):
            if (data[i] < data[j])and(j > 0):
                continue
            else:
                break

        if data[i] >= data[j]:
            temp = data[i]
            p=i
            while p>(j+1):
                data[p] = data[p-1]
                p = p-1
            data[j+1] = temp

        else :
            temp = data[i]
            p=i
            while p>0:
                data[p] = data[p-1]
                p = p-1
            data[0] = temp

def buddle_sort(data):
    for i in range(len(data)):
        for j in range(len(data) - 1):
            if data[j + 1] < data[j]:
                data[j + 1], data[j] = data[j], data[j + 1]

def quick_sort(data, begin, end):
    if begin >= end:
        return
    l = begin
    r = end
    rand = random.randint(l + 1, r)
    data[l], data[rand] = data[rand], data[l]
    tmp = data[l]
    while l < r:
        while l < r and data[r] >= tmp:
            r -= 1
        if l < r:
            data[l] = data[r]
            l += 1
        while l < r and data[l] < tmp:
            l += 1
        if l < r:
            data[r] = data[l]
            r -= 1
    data[l] = tmp
    quick_sort(data, begin, l - 1)
    quick_sort(data, l + 1, end)

# -*-coding:utf-8 -*-
import random

def insert_sort(data):
    temp = 0
    for i in range(1,len(data)):
        if data[i] >= data[i-1] :
            continue
        for j in reversed(range(0,i)):
            if (data[i] < data[j])and(j > 0):
                continue
            else:
                break

        if data[i] >= data[j]:
            temp = data[i]
            p=i
            while p>(j+1):
                data[p] = data[p-1]
                p = p-1
            data[j+1] = temp

        else :
            temp = data[i]
            p=i
            while p>0:
                data[p] = data[p-1]
                p = p-1
            data[0] = temp

def buddle_sort(data):
    for i in range(len(data)):
        for j in range(len(data) - 1):
            if data[j + 1] < data[j]:
                data[j + 1], data[j] = data[j], data[j + 1]

def quick_sort(data, begin, end):
    if begin >= end:
        return
    l = begin
    r = end
    rand = random.randint(l + 1, r)
    data[l], data[rand] = data[rand], data[l]
    tmp = data[l]
    while l < r:
        while l < r and data[r] >= tmp:
            r -= 1
        if l < r:
            data[l] = data[r]
            l += 1
        while l < r and data[l] < tmp:
            l += 1
        if l < r:
            data[r] = data[l]
            r -= 1
    data[l] = tmp
    quick_sort(data, begin, l - 1)
    quick_sort(data, l + 1, end)

# -*-coding:utf-8 -*-