SHARE
TWEET

MichalKowalczyk_sort

michalkowalczyk Dec 9th, 2018 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # -*- coding: utf-8 -*-
  2. """
  3. Created on Sun Dec  9 11:05:17 2018
  4.  
  5. @author: micha
  6. """
  7. print("Michal Kowalczyk -> przykladowe metody sortowania danych!")
  8.  
  9.  
  10. import math
  11.  
  12. A=[]
  13. from random import randint    
  14. for i in range(0,100):
  15.     A.append(randint(1,100))
  16. print(A)
  17. print()
  18.  
  19. def bubblesort(B):
  20.     for i in range(len(B) - 1, 0, -1):
  21.         for j in range(i):
  22.             if B[j] > B[j + 1]:
  23.                 z=B[j+1]
  24.                 B[j+1]=B[j]
  25.                 B[j]=z
  26.     return B
  27.                
  28. def Insertion_sort(B):
  29.     for i in range(1,len(B)):
  30.         klucz = B[i]
  31.         j = i - 1
  32.         while j>=0 and B[j]>klucz:
  33.             B[j + 1] = B[j]
  34.             j = j - 1
  35.         B[j + 1] = klucz
  36.     return B
  37.        
  38. def Select_Sort(B):    
  39.     for i in range (0,len(B)):
  40.         min = i
  41.         for j in range (i,len(B)):
  42.             if (B[j]<B[min]):
  43.                 min=j
  44.         if (max!=i):    
  45.             B[i],B[min] =  B[min],B[i]
  46.     return B
  47.            
  48. def MergeSort(B,p,k):
  49.     if(p<k):
  50.         q=(p+k)//2
  51.         #q = floor((p+k)/2)
  52.         MergeSort(B,p,q)
  53.         MergeSort(B,q+1,k)
  54.         Merge(B,p,q,k)
  55.     return B
  56.        
  57. def Merge(B,p,q,k):
  58.     n1=q-p+1
  59.     n2=k-q
  60.     L=[0]*(n1)
  61.     R=[0]*(n2)
  62.    
  63.    
  64.  
  65.     """for i in range(0,n1):
  66.        L.append(A[p+i-1])
  67.    for j in range(0,n2):
  68.        R.append(A[q+j+1])
  69.       """
  70.     for i in range(0,n1):
  71.         L[i]=B[p+i]
  72.     for j in range(0,n2):
  73.        R[j]=B[q+1+j]
  74.    
  75.    
  76.     i=j=0
  77.     z=p
  78.     while(i<len(L) and j<len(R)):
  79.         if(L[i]<R[j]):
  80.             B[z]=L[i]
  81.             i+=1
  82.            
  83.         else:
  84.             B[z]=R[j]
  85.             j+=1
  86.         z+=1
  87.     while(i<len(L)):
  88.         B[z]=L[i]
  89.         i+=1
  90.         z+=1
  91.     while(j<len(R)):
  92.         B[z]=R[j]
  93.         j+=1
  94.         z+=1
  95.  
  96. def QuickSort(B,p,k):
  97.     if(p<k):
  98.         r = Partition(B,p,k)
  99.         QuickSort(B,p,r-1)
  100.         QuickSort(B,r+1,k)
  101.     return B
  102. def Partition(B,p,k):
  103.     x=B[k]
  104.     i=p-1
  105.    
  106.     for j in range(p,k):
  107.         if(B[j]<=x):
  108.             i+=1
  109.             B[i],B[j] = B[j],B[i]
  110.     B[i+1],B[k] = B[k],B[i+1]
  111.     return i+1
  112.  
  113. def heapify(B,n,i):
  114.     largest = i
  115.     left = 2*i+1
  116.     right = 2*i+2
  117.    
  118.     if(left<n and B[i]<B[left]):
  119.         largest = left
  120.        
  121.     if(right<n and B[largest]<B[right]):
  122.         largest = right
  123.            
  124.     if(largest != i):
  125.         B[i],B[largest] = B[largest],B[i]
  126.        
  127.         heapify(B,n, largest)
  128.        
  129. def heapsort(B):
  130.     n = len(B)
  131.    
  132.     #budowanie kopca maksymalnego
  133.     for i in range(n,-1,-1):
  134.         heapify(B,n,i)
  135.        
  136.     for i in range(n-1,0,-1):
  137.         B[i],B[0] = B[0],B[i]
  138.        
  139.         heapify(B,i,0)
  140.  
  141. def BucketSort(B):
  142.     max=0
  143.     min=0
  144.     for i in range(0, len(B)):
  145.         if B[i] < min:
  146.             min = B[i]
  147.         elif B[i] > max:
  148.             max = B[i]
  149.     bucketCount = (max - min) + 1
  150.     buckets = []
  151.     for i in range(0, bucketCount):
  152.         buckets.append([])
  153.  
  154.     for i in range(0, len(B)):
  155.         buckets[math.floor(B[i] - min)].append(B[i])
  156.  
  157.     sortedArray = []
  158.     for i in range(0, len(buckets)):
  159.         Insertion_sort(buckets[i])
  160.         for j in range(0, len(buckets[i])):
  161.             sortedArray.append(buckets[i][j])
  162.     return sortedArray
  163.  
  164. def radixsort( B ):
  165.   RADIX = 10
  166.   maxLength = False
  167.   tmp , place = -1, 1
  168.  
  169.   while not maxLength:
  170.     maxLength = True
  171.    
  172.     buckets = [list() for _ in range( RADIX )]
  173.  
  174.    
  175.     for  i in (B):
  176.       tmp = i // place
  177.      
  178.       buckets[tmp % RADIX].append( i )
  179.       if maxLength and tmp > 0:
  180.         maxLength = False
  181.  
  182.    
  183.     a = 0
  184.     for b in range( RADIX ):
  185.       buck = buckets[b]
  186.       for i in buck:
  187.         B[a] = i
  188.         a += 1
  189.  
  190.    
  191.     place *= RADIX
  192.   return B
  193.  
  194. def CountingSort(B):
  195.     n=len(B)
  196.     C=[0]*(len(B)+1)
  197.     for i in (B):
  198.        C[i]+=1     #zlicza ile jest tych samych liczb i zapisuje je do elementu o odpowiednim indeksie
  199.        
  200.        
  201.     j=0
  202.     for i in range(n+1):
  203.         while(C[i]>0):
  204.             B[j]= i
  205.             C[i]-=1
  206.             j+=1
  207.     return B        
  208.  
  209.        
  210.          
  211. """            
  212. tmp=0            
  213. for i in range(9):
  214.    B=A
  215.    if(tmp==0):C=bubblesort(B)
  216.    elif(tmp==1):C=Insertion_sort(B)
  217.    elif(tmp==2):C=Select_Sort(B)
  218.    elif(tmp==3):C=MergeSort(B,0,len(B)-1)
  219.    elif(tmp==4):C=QuickSort(B,0,len(B)-1)
  220.    elif(tmp==5):C=heapsort(B)
  221.    elif(tmp==6):C=BucketSort(B)
  222.    elif(tmp==7):C=radixsort( B )
  223.    elif(tmp==8):C=CountingSort(B)
  224.    print("metoda numer",tmp )
  225.  
  226.    print(C)
  227.    tmp+=1
  228. """
  229. B=A  
  230. C=Insertion_sort(B)
  231. print(A)
  232. print(B)
  233. print(C)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top