FilesExpand file tree

master

/

P52_BucketSort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (43 loc) · 1.97 KB

master

/

P52_BucketSort.py

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (43 loc) · 1.97 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

# Author: OMKAR PATHAK

# This program will illustrate how to implement bucket sort algorithm

# Wikipedia says: Bucket sort, or bin sort, is a sorting algorithm that works by distributing the

# elements of an array into a number of buckets. Each bucket is then sorted individually, either using

# a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a

# distribution sort, and is a cousin of radix sort in the most to least significant digit flavour.

# Bucket sort is a generalization of pigeonhole sort. Bucket sort can be implemented with comparisons

# and therefore can also be considered a comparison sort algorithm. The computational complexity estimates

# involve the number of buckets.

# Time Complexity of Solution:

# Best Case O(n); Average Case O(n); Worst Case O(n)

from P26_InsertionSort import insertionSort

import math

DEFAULT_BUCKET_SIZE = 5

def bucketSort(myList, bucketSize=DEFAULT_BUCKET_SIZE):

if(len(myList) == 0):

print('You don\'t have any elements in array!')

minValue = myList[0]

maxValue = myList[0]

# For finding minimum and maximum values

for i in range(0, len(myList)):

if myList[i] < minValue:

minValue = myList[i]

elif myList[i] > maxValue:

maxValue = myList[i]

# Initialize buckets

bucketCount = math.floor((maxValue - minValue) / bucketSize) + 1

buckets = []

for i in range(0, bucketCount):

buckets.append([])

# For putting values in buckets

for i in range(0, len(myList)):

buckets[math.floor((myList[i] - minValue) / bucketSize)].append(myList[i])

# Sort buckets and place back into input array

sortedArray = []

for i in range(0, len(buckets)):

insertionSort(buckets[i])

for j in range(0, len(buckets[i])):

sortedArray.append(buckets[i][j])

return sortedArray

if __name__ == '__main__':

sortedArray = bucketSort([12, 23, 4, 5, 3, 2, 12, 81, 56, 95])

print(sortedArray)