## InsertionSort

# Python program for implementation of Insertion Sort

# Function to do insertion sort
def insertionSort(arr):

    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):

        key = arr[i]

        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key


# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
    print ("%d" %arr[i])


    # Worst Case = O(n²)

# This code is contributed by Mohit Kumra



//


# SelectionSort

# Python program for implementation of SelectionSort

import sys
A = [64, 25, 12, 22, 11]

# Traverse through all array elements
for i in range(len(A)):

    # Find the minimum element in remaining
    # unsorted array
    min_idx = i
    for j in range(i+1, len(A)):
        if A[min_idx] > A[j]:
            min_idx = j

    # Swap the found minimum element with
    # the first element
    A[i], A[min_idx] = A[min_idx], A[i]

# Driver code to test above
print ("Sorted array")
for i in range(len(A)):
    print("%d" %A[i]),

    # Worst-case performance O(n²)


//

# Python program for implementation of Bubble Sort

def bubbleSort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n):

        # Last i elements are already in place
        for j in range(0, n-i-1):

            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

print ("Sorted array is:")
for i in range(len(arr)):
    print ("%d" %arr[i]),

    # Worst-case perfomance O(n²)

//


# 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

# WorstCase Perfomance = O(n²)

//


# Python program for implementation of MergeSort

# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, m, r):
	n1 = m - l + 1
	n2 = r- m

	# create temp arrays
	L = [0] * (n1)
	R = [0] * (n2)

	# Copy data to temp arrays L[] and R[]
	for i in range(0 , n1):
		L[i] = arr[l + i]

	for j in range(0 , n2):
		R[j] = arr[m + 1 + j]

	# Merge the temp arrays back into arr[l..r]
	i = 0	 # Initial index of first subarray
	j = 0	 # Initial index of second subarray
	k = l	 # Initial index of merged subarray

	while i < n1 and j < n2 :
		if L[i] <= R[j]:
			arr[k] = L[i]
			i += 1
		else:
			arr[k] = R[j]
			j += 1
		k += 1

	# Copy the remaining elements of L[], if there
	# are any
	while i < n1:
		arr[k] = L[i]
		i += 1
		k += 1

	# Copy the remaining elements of R[], if there
	# are any
	while j < n2:
		arr[k] = R[j]
		j += 1
		k += 1

# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,l,r):
	if l < r:

		# Same as (l+r)/2, but avoids overflow for
		# large l and h
		m = (l+(r-1))/2

		# Sort first and second halves
		mergeSort(arr, l, m)
		mergeSort(arr, m+1, r)
		merge(arr, l, m, r)


# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print ("Given array is")
for i in range(n):
	print ("%d" %arr[i]),

mergeSort(arr,0,n-1)
print ("\n\nSorted array is")
for i in range(n):
	print ("%d" %arr[i]),

# This code is contributed by Mohit Kumra

# Worst Case = O(n log n)

//


# Python program for implementation of heap Sort

# To heapify subtree rooted at index i.
# n is size of heap
def heapify(arr, n, i):
	largest = i # Initialize largest as root
	l = 2 * i + 1	 # left = 2*i + 1
	r = 2 * i + 2	 # right = 2*i + 2

	# See if left child of root exists and is
	# greater than root
	if l < n and arr[i] < arr[l]:
		largest = l

	# See if right child of root exists and is
	# greater than root
	if r < n and arr[largest] < arr[r]:
		largest = r

	# Change root, if needed
	if largest != i:
		arr[i],arr[largest] = arr[largest],arr[i] # swap

		# Heapify the root.
		heapify(arr, n, largest)

# The main function to sort an array of given size
def heapSort(arr):
	n = len(arr)

	# Build a maxheap.
	for i in range(n, -1, -1):
		heapify(arr, n, i)

	# One by one extract elements
	for i in range(n-1, 0, -1):
		arr[i], arr[0] = arr[0], arr[i] # swap
		heapify(arr, i, 0)

# Driver code to test above
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
	print ("%d" %arr[i]),
# This code is contributed by Mohit Kumra


# Worst Case = O(n log n)


//

# Python3 program for implementation of Shell Sort

def shellSort(arr):

	# Start with a big gap, then reduce the gap
	n = len(arr)
	gap = n//2

	# Do a gapped insertion sort for this gap size.
	# The first gap elements a[0..gap-1] are already in gapped
	# order keep adding one more element until the entire array
	# is gap sorted
	while gap > 0:

		for i in range(gap,n):

			# add a[i] to the elements that have been gap sorted
			# save a[i] in temp and make a hole at position i
			temp = arr[i]

			# shift earlier gap-sorted elements up until the correct
			# location for a[i] is found
			j = i
			while j >= gap and arr[j-gap] >temp:
				arr[j] = arr[j-gap]
				j -= gap

			# put temp (the original a[i]) in its correct location
			arr[j] = temp
		gap //= 2


# Driver code to test above
arr = [ 12, 34, 54, 2, 3]

n = len(arr)
print ("Array before sorting:")
for i in range(n):
	print(arr[i]),

shellSort(arr)

print ("\nArray after sorting:")
for i in range(n):
	print(arr[i]),

# This code is contributed by Mohit Kumra

# Worst Case = O(n²)

//

# Python program for implementation of Radix Sort

# A function to do counting sort of arr[] according to
# the digit represented by exp.
def countingSort(arr, exp1):

	n = len(arr)

	# The output array elements that will have sorted arr
	output = [0] * (n)

	# initialize count array as 0
	count = [0] * (10)

	# Store count of occurrences in count[]
	for i in range(0, n):
		index = (arr[i]/exp1)
		count[ (index)%10 ] += 1

	# Change count[i] so that count[i] now contains actual
	# position of this digit in output array
	for i in range(1,10):
		count[i] += count[i-1]

	# Build the output array
	i = n-1
	while i>=0:
		index = (arr[i]/exp1)
		output[ count[ (index)%10 ] - 1] = arr[i]
		count[ (index)%10 ] -= 1
		i -= 1

	# Copying the output array to arr[],
	# so that arr now contains sorted numbers
	i = 0
	for i in range(0,len(arr)):
		arr[i] = output[i]

# Method to do Radix Sort
def radixSort(arr):

	# Find the maximum number to know number of digits
	max1 = max(arr)

	# Do counting sort for every digit. Note that instead
	# of passing digit number, exp is passed. exp is 10^i
	# where i is current digit number
	exp = 1
	while max1/exp > 0:
		countingSort(arr,exp)
		exp *= 10

# Driver code to test above
arr = [ 170, 45, 75, 90, 802, 24, 2, 66]
radixSort(arr)

for i in range(len(arr)):
	print(arr[i]),

# This code is contributed by Mohit Kumra

# Worst Case = O(w . n)


//

# Python program to implement Gnome Sort

# A function to sort the given list using Gnome sort
def gnomeSort( arr, n):
	index = 0
	while index < n:
		if index == 0:
			index = index + 1
		if arr[index] >= arr[index - 1]:
			index = index + 1
		else:
			arr[index], arr[index-1] = arr[index-1], arr[index]
			index = index - 1

	return arr

# Driver Code
arr = [ 34, 2, 10, -9]
n = len(arr)

arr = gnomeSort(arr, n)
print "Sorted seqquence after applying Gnome Sort :",
for i in arr:
	print i,

# Contributed By Harshit Agrawal

#Worst Case = O(n²)

//

# Python program for counting sort

# The main function that sort the given string arr[] in
# alphabetical order
def countSort(arr):

	# The output character array that will have sorted arr
	output = [0 for i in range(256)]

	# Create a count array to store count of inidividul
	# characters and initialize count array as 0
	count = [0 for i in range(256)]

	# For storing the resulting answer since the
	# string is immutable
	ans = ["" for _ in arr]

	# Store count of each character
	for i in arr:
		count[ord(i)] += 1

	# Change count[i] so that count[i] now contains actual
	# position of this character in output array
	for i in range(256):
		count[i] += count[i-1]

	# Build the output character array
	for i in range(len(arr)):
		output[count[ord(arr[i])]-1] = arr[i]
		count[ord(arr[i])] -= 1

	# Copy the output array to arr, so that arr now
	# contains sorted characters
	for i in range(len(arr)):
		ans[i] = output[i]
	return ans

# Driver program to test above function
arr = "geeksforgeeks"
ans = countSort(arr)
print "Sorted character array is %s" %("".join(ans))

# This code is contributed by Nikhil Kumar Singh

# WorstCase = O(N + k)

//

# Python3 program to sort an array
# using bucket sort
def insertionSort(b):
	for i in range(1, len(b)):
		up = b[i]
		j = i - 1
		while j >=0 and b[j] > up:
			b[j + 1] = b[j]
			j -= 1
		b[j + 1] = up
	return b

def bucketSort(x):
	arr = []
	slot_num = 10 # 10 means 10 slots, each
				# slot's size is 0.1
	for i in range(slot_num):
		arr.append([])

	# Put array elements in different buckets
	for j in x:
		index_b = int(slot_num * j)
		arr[index_b].append(j)

	# Sort individual buckets
	for i in range(slot_num):
		arr[i] = insertionSort(arr[i])

	# concatenate the result
	k = 0
	for i in range(slot_num):
		for j in range(len(arr[i])):
			x[k] = arr[i][j]
			k += 1
	return x

# Driver Code
x = [0.897, 0.565, 0.656,
	0.1234, 0.665, 0.3434]
print("Sorted Array is")
print(bucketSort(x))

# This code is contributed by
# Oneil Hsiao

#Worst Case = O(n²)


//

# Python program for implementation of Cocktail Sort

def cocktailSort(a):
	n = len(a)
	swapped = True
	start = 0
	end = n-1
	while (swapped == True):

		# reset the swapped flag on entering the loop,
		# because it might be true from a previous
		# iteration.
		swapped = False

		# loop from left to right same as the bubble
		# sort
		for i in range (start, end):
			if (a[i] > a[i + 1]) :
				a[i], a[i + 1]= a[i + 1], a[i]
				swapped = True

		# if nothing moved, then array is sorted.
		if (swapped == False):
			break

		# otherwise, reset the swapped flag so that it
		# can be used in the next stage
		swapped = False

		# move the end point back by one, because
		# item at the end is in its rightful spot
		end = end-1

		# from right to left, doing the same
		# comparison as in the previous stage
		for i in range(end-1, start-1, -1):
			if (a[i] > a[i + 1]):
				a[i], a[i + 1] = a[i + 1], a[i]
				swapped = True

		# increase the starting point, because
		# the last stage would have moved the next
		# smallest number to its rightful spot.
		start = start + 1

# Driver code to test above
a = [5, 1, 4, 2, 8, 0, 2]
cocktailSort(a)
print("Sorted array is:")
for i in range(len(a)):
	print ("% d" % a[i]),

#Worst Case = O(n²)

//

# Python3 program to perform TimSort.
RUN = 32

# This function sorts array from left index to
# to right index which is of size atmost RUN
def insertionSort(arr, left, right):

	for i in range(left + 1, right+1):

		temp = arr[i]
		j = i - 1
		while arr[j] > temp and j >= left:

			arr[j+1] = arr[j]
			j -= 1

		arr[j+1] = temp

# merge function merges the sorted runs
def merge(arr, l, m, r):

	# original array is broken in two parts
	# left and right array
	len1, len2 = m - l + 1, r - m
	left, right = [], []
	for i in range(0, len1):
		left.append(arr[l + i])
	for i in range(0, len2):
		right.append(arr[m + 1 + i])

	i, j, k = 0, 0, l
	# after comparing, we merge those two array
	# in larger sub array
	while i < len1 and j < len2:

		if left[i] <= right[j]:
			arr[k] = left[i]
			i += 1

		else:
			arr[k] = right[j]
			j += 1

		k += 1

	# copy remaining elements of left, if any
	while i < len1:

		arr[k] = left[i]
		k += 1
		i += 1

	# copy remaining element of right, if any
	while j < len2:
		arr[k] = right[j]
		k += 1
		j += 1

# iterative Timsort function to sort the
# array[0...n-1] (similar to merge sort)
def timSort(arr, n):

	# Sort individual subarrays of size RUN
	for i in range(0, n, RUN):
		insertionSort(arr, i, min((i+31), (n-1)))

	# start merging from size RUN (or 32). It will merge
	# to form size 64, then 128, 256 and so on ....
	size = RUN
	while size < n:

		# pick starting point of left sub array. We
		# are going to merge arr[left..left+size-1]
		# and arr[left+size, left+2*size-1]
		# After every merge, we increase left by 2*size
		for left in range(0, n, 2*size):

			# find ending point of left sub array
			# mid+1 is starting point of right sub array
			mid = left + size - 1
			right = min((left + 2*size - 1), (n-1))

			# merge sub array arr[left.....mid] &
			# arr[mid+1....right]
			merge(arr, left, mid, right)

		size = 2*size

# utility function to print the Array
def printArray(arr, n):

	for i in range(0, n):
		print(arr[i], end = " ")
	print()


# Driver program to test above function
if __name__ == "__main__":

	arr = [5, 21, 7, 23, 19]
	n = len(arr)
	print("Given Array is")
	printArray(arr, n)

	timSort(arr, n)

	print("After Sorting Array is")
	printArray(arr, n)

# This code is contributed by Rituraj Jain

# Worst Case = O(n log n)

//

# Python program for implementation of Quicksort Sort

# This function takes last element as pivot, places
# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
def partition(arr,low,high):
	i = ( low-1 )		 # index of smaller element
	pivot = arr[high]	 # pivot

	for j in range(low , high):

		# If current element is smaller than the pivot
		if arr[j] < pivot:

			# increment index of smaller element
			i = i+1
			arr[i],arr[j] = arr[j],arr[i]

	arr[i+1],arr[high] = arr[high],arr[i+1]
	return ( i+1 )

# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index

# Function to do Quick sort
def quickSort(arr,low,high):
	if low < high:

		# pi is partitioning index, arr[p] is now
		# at right place
		pi = partition(arr,low,high)

		# Separately sort elements before
		# partition and after partition
		quickSort(arr, low, pi-1)
		quickSort(arr, pi+1, high)

# Driver code to test above
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
	print ("%d" %arr[i]),

# This code is contributed by Mohit Kumra

#Worst Case = O(n²)