# Write a Python Program for Comb Sort 
# Python program for implementation of CombSort
  
# To find next gap from current
def getNextGap(gap):
  
    # Shrink gap by Shrink factor
    gap = (gap * 10)/13
    if gap < 1:
        return 1
    return gap
  
# Function to sort arr[] using Comb Sort
def combSort(arr):
    n = len(arr)
  
    # Initialize gap
    gap = n
  
    # Initialize swapped as true to make sure that
    # loop runs
    swapped = True
  
    # Keep running while gap is more than 1 and last
    # iteration caused a swap
    while gap !=1 or swapped == 1:
  
        # Find next gap
        gap = getNextGap(gap)
  
        # Initialize swapped as false so that we can
        # check if swap happened or not
        swapped = False
  
        # Compare all elements with current gap
        for i in range(0, n-gap):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap]=arr[i + gap], arr[i]
                swapped = True
  
  
# Driver code to test above
arr = [ 8, 4, 1, 3, -44, 23, -6, 28, 0]
combSort(arr)
  
print ("Sorted array:")
for i in range(len(arr)):
    print (arr[i]),
  
  
# This code is contributed by Mohit Kumra