• API
• FAQ
• Tools
• Archive
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.
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.
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)
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.

Top