a = [2, 3, 4, 1]
b = [4, 2, 5, 1, 2, 7, 6, 0]

def bubble_sort(A):
  n = len(A)
  while n > 1:
    for i in range(0, n - 1):
      if A[i] > A[i + 1]:
        A[i], A[i + 1] = A[i + 1], A[i]
    n -= 1
  return A


def bubble_sort2(A):
  for j in range(len(A)):
    for i in range(len(A) - 1):
      if A[i] > A[i + 1]:
         A[i], A[i + 1] = A[i + 1], A[i]
  return A


# print('Przed sortowaniem', a)
# print('Po sortowaniu', bubble_sort2(a))

# print('Przed sortowaniem', b)
# print('Po sortowaniu', bubble_sort2(b))

def counting_sort(array):
    maxval = max(array)
    n = len(array)
    m = maxval + 1
    count = [0] * m               # init with zeros
    for a in array:
        count[a] += 1             # count occurences
    new_array = []
    for liczba in range(m):
      for ilosc_wystapien in range(count[liczba]):
        new_array.append(liczba)
    return new_array

# print('Przed sortowaniem', a)
# print('Po sortowaniu', counting_sort(a))

# print('Przed sortowaniem', b)
# print('Po sortowaniu', counting_sort(b))


def bucket_sort(alist):
    largest = max(alist)
    length = len(alist)
    size = largest/length

    buckets = [[] for _ in range(length)]
    for i in range(length):
        j = int(alist[i]/size)
        if j != length:
            buckets[j].append(alist[i])
        else:
            buckets[length - 1].append(alist[i])

    for i in range(length):
        insertion_sort(buckets[i])
    result = []
    for i in range(length):
        result = result + buckets[i]

    return result

def insertion_sort(alist):
    for i in range(1, len(alist)):
        temp = alist[i]
        j = i - 1
        while (j >= 0 and temp < alist[j]):
            alist[j + 1] = alist[j]
            j = j - 1
        alist[j + 1] = temp

a = [7, 10, 2, 8, 4, 5, 27]
print('Sorting list', a)
print('Bucket sort', bucket_sort(a))




def selecting_sort(alist):
  for i in range(len(alist)):
    min_ = alist[i] # 10
    idx = i # 1
    for j in range(i + 1, len(alist)):
      if alist[j] < min_:
        min_ = alist[j]
        idx = j
    alist[i], alist[idx] = alist[idx], alist[i]
  return alist

a = [7, 10, 2, 8, 4, 5, 27]
print('Sorting list', a)
print('Selection sort', bucket_sort(a))