MichalKowalczyk_sort

# -*- coding: utf-8 -*-
"""
Created on Sun Dec  9 11:05:17 2018

@author: micha
"""
print("Michal Kowalczyk -> przykladowe metody sortowania danych!")


import math

A=[]
from random import randint
for i in range(0,100):
    A.append(randint(1,100))
print(A)
print()

def bubblesort(B):
    for i in range(len(B) - 1, 0, -1):
        for j in range(i):
            if B[j] > B[j + 1]:
                z=B[j+1]
                B[j+1]=B[j]
                B[j]=z
    return B

def Insertion_sort(B):
    for i in range(1,len(B)):
        klucz = B[i]
        j = i - 1
        while j>=0 and B[j]>klucz:
            B[j + 1] = B[j]
            j = j - 1
        B[j + 1] = klucz
    return B

def Select_Sort(B):
    for i in range (0,len(B)):
        min = i
        for j in range (i,len(B)):
            if (B[j]<B[min]):
                min=j
        if (max!=i):
            B[i],B[min] =  B[min],B[i]
    return B

def MergeSort(B,p,k):
    if(p<k):
        q=(p+k)//2
        #q = floor((p+k)/2)
        MergeSort(B,p,q)
        MergeSort(B,q+1,k)
        Merge(B,p,q,k)
    return B

def Merge(B,p,q,k):
    n1=q-p+1
    n2=k-q
    L=[0]*(n1)
    R=[0]*(n2)



    """for i in range(0,n1):
        L.append(A[p+i-1])
    for j in range(0,n2):
        R.append(A[q+j+1])
       """
    for i in range(0,n1):
        L[i]=B[p+i]
    for j in range(0,n2):
       R[j]=B[q+1+j]


    i=j=0
    z=p
    while(i<len(L) and j<len(R)):
        if(L[i]<R[j]):
            B[z]=L[i]
            i+=1

        else:
            B[z]=R[j]
            j+=1
        z+=1
    while(i<len(L)):
        B[z]=L[i]
        i+=1
        z+=1
    while(j<len(R)):
        B[z]=R[j]
        j+=1
        z+=1

def QuickSort(B,p,k):
    if(p<k):
        r = Partition(B,p,k)
        QuickSort(B,p,r-1)
        QuickSort(B,r+1,k)
    return B
def Partition(B,p,k):
    x=B[k]
    i=p-1

    for j in range(p,k):
        if(B[j]<=x):
            i+=1
            B[i],B[j] = B[j],B[i]
    B[i+1],B[k] = B[k],B[i+1]
    return i+1

def heapify(B,n,i):
    largest = i
    left = 2*i+1
    right = 2*i+2

    if(left<n and B[i]<B[left]):
        largest = left

    if(right<n and B[largest]<B[right]):
        largest = right

    if(largest != i):
        B[i],B[largest] = B[largest],B[i]

        heapify(B,n, largest)

def heapsort(B):
    n = len(B)

    #budowanie kopca maksymalnego
    for i in range(n,-1,-1):
        heapify(B,n,i)

    for i in range(n-1,0,-1):
        B[i],B[0] = B[0],B[i]

        heapify(B,i,0)

def BucketSort(B):
    max=0
    min=0
    for i in range(0, len(B)):
        if B[i] < min:
            min = B[i]
        elif B[i] > max:
            max = B[i]
    bucketCount = (max - min) + 1
    buckets = []
    for i in range(0, bucketCount):
        buckets.append([])

    for i in range(0, len(B)):
        buckets[math.floor(B[i] - min)].append(B[i])

    sortedArray = []
    for i in range(0, len(buckets)):
        Insertion_sort(buckets[i])
        for j in range(0, len(buckets[i])):
            sortedArray.append(buckets[i][j])
    return sortedArray

def radixsort( B ):
  RADIX = 10
  maxLength = False
  tmp , place = -1, 1

  while not maxLength:
    maxLength = True

    buckets = [list() for _ in range( RADIX )]


    for  i in (B):
      tmp = i // place

      buckets[tmp % RADIX].append( i )
      if maxLength and tmp > 0:
        maxLength = False


    a = 0
    for b in range( RADIX ):
      buck = buckets[b]
      for i in buck:
        B[a] = i
        a += 1


    place *= RADIX
  return B

def CountingSort(B):
    n=len(B)
    C=[0]*(len(B)+1)
    for i in (B):
       C[i]+=1     #zlicza ile jest tych samych liczb i zapisuje je do elementu o odpowiednim indeksie


    j=0
    for i in range(n+1):
        while(C[i]>0):
            B[j]= i
            C[i]-=1
            j+=1
    return B



"""
tmp=0
for i in range(9):
    B=A
    if(tmp==0):C=bubblesort(B)
    elif(tmp==1):C=Insertion_sort(B)
    elif(tmp==2):C=Select_Sort(B)
    elif(tmp==3):C=MergeSort(B,0,len(B)-1)
    elif(tmp==4):C=QuickSort(B,0,len(B)-1)
    elif(tmp==5):C=heapsort(B)
    elif(tmp==6):C=BucketSort(B)
    elif(tmp==7):C=radixsort( B )
    elif(tmp==8):C=CountingSort(B)
    print("metoda numer",tmp )

    print(C)
    tmp+=1
 """
B=A
C=Insertion_sort(B)
print(A)
print(B)
print(C)