• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Oct 21st, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. ## InsertionSort
2.
3. # Python program for implementation of Insertion Sort
4.
5. # Function to do insertion sort
6. def insertionSort(arr):
7.
8.     # Traverse through 1 to len(arr)
9.     for i in range(1, len(arr)):
10.
11.         key = arr[i]
12.
13.         # Move elements of arr[0..i-1], that are
14.         # greater than key, to one position ahead
15.         # of their current position
16.         j = i-1
17.         while j >=0 and key < arr[j] :
18.                 arr[j+1] = arr[j]
19.                 j -= 1
20.         arr[j+1] = key
21.
22.
23. # Driver code to test above
24. arr = [12, 11, 13, 5, 6]
25. insertionSort(arr)
26. print ("Sorted array is:")
27. for i in range(len(arr)):
28.     print ("%d" %arr[i])
29.
30.
31.     # Worst Case = O(n²)
32.
33. # This code is contributed by Mohit Kumra
34.
35.
36.
37. //
38.
39.
40. # SelectionSort
41.
42. # Python program for implementation of SelectionSort
43.
44. import sys
45. A = [64, 25, 12, 22, 11]
46.
47. # Traverse through all array elements
48. for i in range(len(A)):
49.
50.     # Find the minimum element in remaining
51.     # unsorted array
52.     min_idx = i
53.     for j in range(i+1, len(A)):
54.         if A[min_idx] > A[j]:
55.             min_idx = j
56.
57.     # Swap the found minimum element with
58.     # the first element
59.     A[i], A[min_idx] = A[min_idx], A[i]
60.
61. # Driver code to test above
62. print ("Sorted array")
63. for i in range(len(A)):
64.     print("%d" %A[i]),
65.
66.     # Worst-case performance O(n²)
67.
68.
69. //
70.
71. # Python program for implementation of Bubble Sort
72.
73. def bubbleSort(arr):
74.     n = len(arr)
75.
76.     # Traverse through all array elements
77.     for i in range(n):
78.
79.         # Last i elements are already in place
80.         for j in range(0, n-i-1):
81.
82.             # traverse the array from 0 to n-i-1
83.             # Swap if the element found is greater
84.             # than the next element
85.             if arr[j] > arr[j+1] :
86.                 arr[j], arr[j+1] = arr[j+1], arr[j]
87.
88. # Driver code to test above
89. arr = [64, 34, 25, 12, 22, 11, 90]
90.
91. bubbleSort(arr)
92.
93. print ("Sorted array is:")
94. for i in range(len(arr)):
95.     print ("%d" %arr[i]),
96.
97.     # Worst-case perfomance O(n²)
98.
99. //
100.
101.
102. # Python program for implementation of CombSort
103.
104. # To find next gap from current
105. def getNextGap(gap):
106.
107.     # Shrink gap by Shrink factor
108.     gap = (gap * 10)/13
109.     if gap < 1:
110.         return 1
111.     return gap
112.
113. # Function to sort arr[] using Comb Sort
114. def combSort(arr):
115.     n = len(arr)
116.
117.     # Initialize gap
118.     gap = n
119.
120.     # Initialize swapped as true to make sure that
121.     # loop runs
122.     swapped = True
123.
124.     # Keep running while gap is more than 1 and last
125.     # iteration caused a swap
126.     while gap !=1 or swapped == 1:
127.
128.         # Find next gap
129.         gap = getNextGap(gap)
130.
131.         # Initialize swapped as false so that we can
132.         # check if swap happened or not
133.         swapped = False
134.
135.         # Compare all elements with current gap
136.         for i in range(0, n-gap):
137.             if arr[i] > arr[i + gap]:
138.                 arr[i], arr[i + gap]=arr[i + gap], arr[i]
139.                 swapped = True
140.
141.
142. # Driver code to test above
143. arr = [ 8, 4, 1, 3, -44, 23, -6, 28, 0]
144. combSort(arr)
145.
146. print ("Sorted array:")
147. for i in range(len(arr)):
148.     print (arr[i]),
149.
150.
151. # This code is contributed by Mohit Kumra
152.
153. # WorstCase Perfomance = O(n²)
154.
155. //
156.
157.
158. # Python program for implementation of MergeSort
159.
160. # Merges two subarrays of arr[].
161. # First subarray is arr[l..m]
162. # Second subarray is arr[m+1..r]
163. def merge(arr, l, m, r):
164.     n1 = m - l + 1
165.     n2 = r- m
166.
167.     # create temp arrays
168.     L =  * (n1)
169.     R =  * (n2)
170.
171.     # Copy data to temp arrays L[] and R[]
172.     for i in range(0 , n1):
173.         L[i] = arr[l + i]
174.
175.     for j in range(0 , n2):
176.         R[j] = arr[m + 1 + j]
177.
178.     # Merge the temp arrays back into arr[l..r]
179.     i = 0    # Initial index of first subarray
180.     j = 0    # Initial index of second subarray
181.     k = l    # Initial index of merged subarray
182.
183.     while i < n1 and j < n2 :
184.         if L[i] <= R[j]:
185.             arr[k] = L[i]
186.             i += 1
187.         else:
188.             arr[k] = R[j]
189.             j += 1
190.         k += 1
191.
192.     # Copy the remaining elements of L[], if there
193.     # are any
194.     while i < n1:
195.         arr[k] = L[i]
196.         i += 1
197.         k += 1
198.
199.     # Copy the remaining elements of R[], if there
200.     # are any
201.     while j < n2:
202.         arr[k] = R[j]
203.         j += 1
204.         k += 1
205.
206. # l is for left index and r is right index of the
207. # sub-array of arr to be sorted
208. def mergeSort(arr,l,r):
209.     if l < r:
210.
211.         # Same as (l+r)/2, but avoids overflow for
212.         # large l and h
213.         m = (l+(r-1))/2
214.
215.         # Sort first and second halves
216.         mergeSort(arr, l, m)
217.         mergeSort(arr, m+1, r)
218.         merge(arr, l, m, r)
219.
220.
221. # Driver code to test above
222. arr = [12, 11, 13, 5, 6, 7]
223. n = len(arr)
224. print ("Given array is")
225. for i in range(n):
226.     print ("%d" %arr[i]),
227.
228. mergeSort(arr,0,n-1)
229. print ("\n\nSorted array is")
230. for i in range(n):
231.     print ("%d" %arr[i]),
232.
233. # This code is contributed by Mohit Kumra
234.
235. # Worst Case = O(n log n)
236.
237. //
238.
239.
240. # Python program for implementation of heap Sort
241.
242. # To heapify subtree rooted at index i.
243. # n is size of heap
244. def heapify(arr, n, i):
245.     largest = i # Initialize largest as root
246.     l = 2 * i + 1    # left = 2*i + 1
247.     r = 2 * i + 2    # right = 2*i + 2
248.
249.     # See if left child of root exists and is
250.     # greater than root
251.     if l < n and arr[i] < arr[l]:
252.         largest = l
253.
254.     # See if right child of root exists and is
255.     # greater than root
256.     if r < n and arr[largest] < arr[r]:
257.         largest = r
258.
259.     # Change root, if needed
260.     if largest != i:
261.         arr[i],arr[largest] = arr[largest],arr[i] # swap
262.
263.         # Heapify the root.
264.         heapify(arr, n, largest)
265.
266. # The main function to sort an array of given size
267. def heapSort(arr):
268.     n = len(arr)
269.
270.     # Build a maxheap.
271.     for i in range(n, -1, -1):
272.         heapify(arr, n, i)
273.
274.     # One by one extract elements
275.     for i in range(n-1, 0, -1):
276.         arr[i], arr = arr, arr[i] # swap
277.         heapify(arr, i, 0)
278.
279. # Driver code to test above
280. arr = [ 12, 11, 13, 5, 6, 7]
281. heapSort(arr)
282. n = len(arr)
283. print ("Sorted array is")
284. for i in range(n):
285.     print ("%d" %arr[i]),
286. # This code is contributed by Mohit Kumra
287.
288.
289. # Worst Case = O(n log n)
290.
291.
292. //
293.
294. # Python3 program for implementation of Shell Sort
295.
296. def shellSort(arr):
297.
299.     n = len(arr)
300.     gap = n//2
301.
302.     # Do a gapped insertion sort for this gap size.
303.     # The first gap elements a[0..gap-1] are already in gapped
304.     # order keep adding one more element until the entire array
305.     # is gap sorted
306.     while gap > 0:
307.
308.         for i in range(gap,n):
309.
310.             # add a[i] to the elements that have been gap sorted
311.             # save a[i] in temp and make a hole at position i
312.             temp = arr[i]
313.
314.             # shift earlier gap-sorted elements up until the correct
315.             # location for a[i] is found
316.             j = i
317.             while j >= gap and arr[j-gap] >temp:
318.                 arr[j] = arr[j-gap]
319.                 j -= gap
320.
321.             # put temp (the original a[i]) in its correct location
322.             arr[j] = temp
323.         gap //= 2
324.
325.
326. # Driver code to test above
327. arr = [ 12, 34, 54, 2, 3]
328.
329. n = len(arr)
330. print ("Array before sorting:")
331. for i in range(n):
332.     print(arr[i]),
333.
334. shellSort(arr)
335.
336. print ("\nArray after sorting:")
337. for i in range(n):
338.     print(arr[i]),
339.
340. # This code is contributed by Mohit Kumra
341.
342. # Worst Case = O(n²)
343.
344. //
345.
346. # Python program for implementation of Radix Sort
347.
348. # A function to do counting sort of arr[] according to
349. # the digit represented by exp.
350. def countingSort(arr, exp1):
351.
352.     n = len(arr)
353.
354.     # The output array elements that will have sorted arr
355.     output =  * (n)
356.
357.     # initialize count array as 0
358.     count =  * (10)
359.
360.     # Store count of occurrences in count[]
361.     for i in range(0, n):
362.         index = (arr[i]/exp1)
363.         count[ (index)%10 ] += 1
364.
365.     # Change count[i] so that count[i] now contains actual
366.     # position of this digit in output array
367.     for i in range(1,10):
368.         count[i] += count[i-1]
369.
370.     # Build the output array
371.     i = n-1
372.     while i>=0:
373.         index = (arr[i]/exp1)
374.         output[ count[ (index)%10 ] - 1] = arr[i]
375.         count[ (index)%10 ] -= 1
376.         i -= 1
377.
378.     # Copying the output array to arr[],
379.     # so that arr now contains sorted numbers
380.     i = 0
381.     for i in range(0,len(arr)):
382.         arr[i] = output[i]
383.
384. # Method to do Radix Sort
386.
387.     # Find the maximum number to know number of digits
388.     max1 = max(arr)
389.
390.     # Do counting sort for every digit. Note that instead
391.     # of passing digit number, exp is passed. exp is 10^i
392.     # where i is current digit number
393.     exp = 1
394.     while max1/exp > 0:
395.         countingSort(arr,exp)
396.         exp *= 10
397.
398. # Driver code to test above
399. arr = [ 170, 45, 75, 90, 802, 24, 2, 66]
401.
402. for i in range(len(arr)):
403.     print(arr[i]),
404.
405. # This code is contributed by Mohit Kumra
406.
407. # Worst Case = O(w . n)
408.
409.
410. //
411.
412. # Python program to implement Gnome Sort
413.
414. # A function to sort the given list using Gnome sort
415. def gnomeSort( arr, n):
416.     index = 0
417.     while index < n:
418.         if index == 0:
419.             index = index + 1
420.         if arr[index] >= arr[index - 1]:
421.             index = index + 1
422.         else:
423.             arr[index], arr[index-1] = arr[index-1], arr[index]
424.             index = index - 1
425.
426.     return arr
427.
428. # Driver Code
429. arr = [ 34, 2, 10, -9]
430. n = len(arr)
431.
432. arr = gnomeSort(arr, n)
433. print "Sorted seqquence after applying Gnome Sort :",
434. for i in arr:
435.     print i,
436.
437. # Contributed By Harshit Agrawal
438.
439. #Worst Case = O(n²)
440.
441. //
442.
443. # Python program for counting sort
444.
445. # The main function that sort the given string arr[] in
446. # alphabetical order
447. def countSort(arr):
448.
449.     # The output character array that will have sorted arr
450.     output = [0 for i in range(256)]
451.
452.     # Create a count array to store count of inidividul
453.     # characters and initialize count array as 0
454.     count = [0 for i in range(256)]
455.
456.     # For storing the resulting answer since the
457.     # string is immutable
458.     ans = ["" for _ in arr]
459.
460.     # Store count of each character
461.     for i in arr:
462.         count[ord(i)] += 1
463.
464.     # Change count[i] so that count[i] now contains actual
465.     # position of this character in output array
466.     for i in range(256):
467.         count[i] += count[i-1]
468.
469.     # Build the output character array
470.     for i in range(len(arr)):
471.         output[count[ord(arr[i])]-1] = arr[i]
472.         count[ord(arr[i])] -= 1
473.
474.     # Copy the output array to arr, so that arr now
475.     # contains sorted characters
476.     for i in range(len(arr)):
477.         ans[i] = output[i]
478.     return ans
479.
480. # Driver program to test above function
481. arr = "geeksforgeeks"
482. ans = countSort(arr)
483. print "Sorted character array is %s" %("".join(ans))
484.
485. # This code is contributed by Nikhil Kumar Singh
486.
487. # WorstCase = O(N + k)
488.
489. //
490.
491. # Python3 program to sort an array
492. # using bucket sort
493. def insertionSort(b):
494.     for i in range(1, len(b)):
495.         up = b[i]
496.         j = i - 1
497.         while j >=0 and b[j] > up:
498.             b[j + 1] = b[j]
499.             j -= 1
500.         b[j + 1] = up
501.     return b
502.
503. def bucketSort(x):
504.     arr = []
505.     slot_num = 10 # 10 means 10 slots, each
506.                 # slot's size is 0.1
507.     for i in range(slot_num):
508.         arr.append([])
509.
510.     # Put array elements in different buckets
511.     for j in x:
512.         index_b = int(slot_num * j)
513.         arr[index_b].append(j)
514.
515.     # Sort individual buckets
516.     for i in range(slot_num):
517.         arr[i] = insertionSort(arr[i])
518.
519.     # concatenate the result
520.     k = 0
521.     for i in range(slot_num):
522.         for j in range(len(arr[i])):
523.             x[k] = arr[i][j]
524.             k += 1
525.     return x
526.
527. # Driver Code
528. x = [0.897, 0.565, 0.656,
529.     0.1234, 0.665, 0.3434]
530. print("Sorted Array is")
531. print(bucketSort(x))
532.
533. # This code is contributed by
534. # Oneil Hsiao
535.
536. #Worst Case = O(n²)
537.
538.
539. //
540.
541. # Python program for implementation of Cocktail Sort
542.
543. def cocktailSort(a):
544.     n = len(a)
545.     swapped = True
546.     start = 0
547.     end = n-1
548.     while (swapped == True):
549.
550.         # reset the swapped flag on entering the loop,
551.         # because it might be true from a previous
552.         # iteration.
553.         swapped = False
554.
555.         # loop from left to right same as the bubble
556.         # sort
557.         for i in range (start, end):
558.             if (a[i] > a[i + 1]) :
559.                 a[i], a[i + 1]= a[i + 1], a[i]
560.                 swapped = True
561.
562.         # if nothing moved, then array is sorted.
563.         if (swapped == False):
564.             break
565.
566.         # otherwise, reset the swapped flag so that it
567.         # can be used in the next stage
568.         swapped = False
569.
570.         # move the end point back by one, because
571.         # item at the end is in its rightful spot
572.         end = end-1
573.
574.         # from right to left, doing the same
575.         # comparison as in the previous stage
576.         for i in range(end-1, start-1, -1):
577.             if (a[i] > a[i + 1]):
578.                 a[i], a[i + 1] = a[i + 1], a[i]
579.                 swapped = True
580.
581.         # increase the starting point, because
582.         # the last stage would have moved the next
583.         # smallest number to its rightful spot.
584.         start = start + 1
585.
586. # Driver code to test above
587. a = [5, 1, 4, 2, 8, 0, 2]
588. cocktailSort(a)
589. print("Sorted array is:")
590. for i in range(len(a)):
591.     print ("% d" % a[i]),
592.
593. #Worst Case = O(n²)
594.
595. //
596.
597. # Python3 program to perform TimSort.
598. RUN = 32
599.
600. # This function sorts array from left index to
601. # to right index which is of size atmost RUN
602. def insertionSort(arr, left, right):
603.
604.     for i in range(left + 1, right+1):
605.
606.         temp = arr[i]
607.         j = i - 1
608.         while arr[j] > temp and j >= left:
609.
610.             arr[j+1] = arr[j]
611.             j -= 1
612.
613.         arr[j+1] = temp
614.
615. # merge function merges the sorted runs
616. def merge(arr, l, m, r):
617.
618.     # original array is broken in two parts
619.     # left and right array
620.     len1, len2 = m - l + 1, r - m
621.     left, right = [], []
622.     for i in range(0, len1):
623.         left.append(arr[l + i])
624.     for i in range(0, len2):
625.         right.append(arr[m + 1 + i])
626.
627.     i, j, k = 0, 0, l
628.     # after comparing, we merge those two array
629.     # in larger sub array
630.     while i < len1 and j < len2:
631.
632.         if left[i] <= right[j]:
633.             arr[k] = left[i]
634.             i += 1
635.
636.         else:
637.             arr[k] = right[j]
638.             j += 1
639.
640.         k += 1
641.
642.     # copy remaining elements of left, if any
643.     while i < len1:
644.
645.         arr[k] = left[i]
646.         k += 1
647.         i += 1
648.
649.     # copy remaining element of right, if any
650.     while j < len2:
651.         arr[k] = right[j]
652.         k += 1
653.         j += 1
654.
655. # iterative Timsort function to sort the
656. # array[0...n-1] (similar to merge sort)
657. def timSort(arr, n):
658.
659.     # Sort individual subarrays of size RUN
660.     for i in range(0, n, RUN):
661.         insertionSort(arr, i, min((i+31), (n-1)))
662.
663.     # start merging from size RUN (or 32). It will merge
664.     # to form size 64, then 128, 256 and so on ....
665.     size = RUN
666.     while size < n:
667.
668.         # pick starting point of left sub array. We
669.         # are going to merge arr[left..left+size-1]
670.         # and arr[left+size, left+2*size-1]
671.         # After every merge, we increase left by 2*size
672.         for left in range(0, n, 2*size):
673.
674.             # find ending point of left sub array
675.             # mid+1 is starting point of right sub array
676.             mid = left + size - 1
677.             right = min((left + 2*size - 1), (n-1))
678.
679.             # merge sub array arr[left.....mid] &
680.             # arr[mid+1....right]
681.             merge(arr, left, mid, right)
682.
683.         size = 2*size
684.
685. # utility function to print the Array
686. def printArray(arr, n):
687.
688.     for i in range(0, n):
689.         print(arr[i], end = " ")
690.     print()
691.
692.
693. # Driver program to test above function
694. if __name__ == "__main__":
695.
696.     arr = [5, 21, 7, 23, 19]
697.     n = len(arr)
698.     print("Given Array is")
699.     printArray(arr, n)
700.
701.     timSort(arr, n)
702.
703.     print("After Sorting Array is")
704.     printArray(arr, n)
705.
706. # This code is contributed by Rituraj Jain
707.
708. # Worst Case = O(n log n)
709.
710. //
711.
712. # Python program for implementation of Quicksort Sort
713.
714. # This function takes last element as pivot, places
715. # the pivot element at its correct position in sorted
716. # array, and places all smaller (smaller than pivot)
717. # to left of pivot and all greater elements to right
718. # of pivot
719. def partition(arr,low,high):
720.     i = ( low-1 )        # index of smaller element
721.     pivot = arr[high]    # pivot
722.
723.     for j in range(low , high):
724.
725.         # If current element is smaller than the pivot
726.         if arr[j] < pivot:
727.
728.             # increment index of smaller element
729.             i = i+1
730.             arr[i],arr[j] = arr[j],arr[i]
731.
732.     arr[i+1],arr[high] = arr[high],arr[i+1]
733.     return ( i+1 )
734.
735. # The main function that implements QuickSort
736. # arr[] --> Array to be sorted,
737. # low --> Starting index,
738. # high --> Ending index
739.
740. # Function to do Quick sort
741. def quickSort(arr,low,high):
742.     if low < high:
743.
744.         # pi is partitioning index, arr[p] is now
745.         # at right place
746.         pi = partition(arr,low,high)
747.
748.         # Separately sort elements before
749.         # partition and after partition
750.         quickSort(arr, low, pi-1)
751.         quickSort(arr, pi+1, high)
752.
753. # Driver code to test above
754. arr = [10, 7, 8, 9, 1, 5]
755. n = len(arr)
756. quickSort(arr,0,n-1)
757. print ("Sorted array is:")
758. for i in range(n):
759.     print ("%d" %arr[i]),
760.
761. # This code is contributed by Mohit Kumra
762.
763. #Worst Case = O(n²)
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