Wednesday, March 16, 2016

Bucket Sort in python

I make buckets as many as size of arr
and put data.

arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
def bucketSort(arr, size):
    buckets = [[] for i in range(size)]

    # put arr in bucket        
    for i in range(len(arr)):
        num = size*arr[i]
        buckets[int(num)].append(arr[i])

    output = []
    # use insertion sort        
    for i in range(len(buckets)):
        insertionSort(buckets[i])

    # concat all data        
    for i in range(len(buckets)):
        while len(buckets[i]) > 0:
            output.append(buckets[i].pop(0))

    return output


def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def insertionSort(arr):
    for i in range(1, len(arr)):
        index= i
        print("index : " + str(i))
        while index!=0:
            if arr[index] < arr[index-1]:
                temp = arr[index]
                arr[index]= arr[index-1]
                arr[index-1] = temp
                index = index-1                print(arr)
            else :
                break
print(bucketSort(arr, len(arr)))

1 comment:

  1. how would your sort a list of strings (words) using bucket sort?

    ReplyDelete