def bubbleSort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n-1):
        # 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]

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print("Sorted array is:")
for i in range(len(arr)):
    print("%d" % arr[i], end=" ")

def quick_sort(arr):
    # Base case: an array with 0 or 1 elements is already sorted
    if len(arr) <= 1:
        return arr

    # Choosing the pivot element from the array
    pivot = arr[len(arr) // 2]

    # Elements less than pivot
    left = [x for x in arr if x < pivot]

    # Elements equal to pivot
    middle = [x for x in arr if x == pivot]

    # Elements greater than pivot
    right = [x for x in arr if x > pivot]

    # Recursively sort the left and right parts and combine them with the middle
    return quick_sort(left) + middle + quick_sort(right)

# Example usage
array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quick_sort(array)
print(sorted_array)

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1     # left child
    right = 2 * i + 2    # right child

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

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

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

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

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

    # Build a maxheap.
    for i in range(n // 2 - 1, -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)

# Example usage
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is:", arr)

def bucketSort(arr):
    # Find maximum value in the array and use length of the array to determine which value in the array goes into which bucket
    max_value = max(arr)
    size = max_value/len(arr)

    # Create n empty buckets where n is equal to the length of the array
    buckets_list= [[] for _ in range(len(arr))]

    # Put array elements in different buckets based on size
    for i in range(len(arr)):
        j = int(arr[i] / size)
        if j != len (arr):
            buckets_list[j].append(arr[i])
        else:
            buckets_list[len(arr) - 1].append(arr[i])

    # Sort elements within the buckets using Insertion Sort
    for z in range(len(arr)):
        insertionSort(buckets_list[z])
            
    # Concatenate buckets with sorted elements into a single array
    final_output = []
    for x in range(len(arr)):
        final_output = final_output + buckets_list[x]
    return final_output

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    

# Example usage
arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
print("Sorted Array is")
print(bucketSort(arr))