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 = [0] * (n1)
  169.     R = [0] * (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[0] = arr[0], 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.  
  298.     # Start with a big gap, then reduce the gap
  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 = [0] * (n)
  356.  
  357.     # initialize count array as 0
  358.     count = [0] * (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
  385. def radixSort(arr):
  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]
  400. radixSort(arr)
  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. OK, I Understand
 
Top