Commit9f982a8

authored and

committed

add pigeon hole sort (TheAlgorithms#833)

1 parenta0ab3ce commit9f982a8Copy full SHA for 9f982a8

File tree

+50

-0

lines changed

+50

-0

lines changed

Lines changed: 50 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,50 @@`
	`1`	`+'''`
	`2`	`+ This is an implementation of Pigeon Hole Sort.`
	`3`	`+'''`
	`4`	`+`
	`5`	`+from __future__importprint_function`
	`6`	`+`
	`7`	`+defpigeon_sort(array):`
	`8`	`+# Manually finds the minimum and maximum of the array.`
	`9`	`+min=array[0]`
	`10`	`+max=array[0]`
	`11`	`+`
	`12`	`+foriinrange(len(array)):`
	`13`	`+if(array[i]<min):min=array[i]`
	`14`	`+elif(array[i]>max):max=array[i]`
	`15`	`+`
	`16`	`+# Compute the variables`
	`17`	`+holes_range=max-min+1`
	`18`	`+holes= [0for_inrange(holes_range)]`
	`19`	`+holes_repeat= [0for_inrange(holes_range)]`
	`20`	`+`
	`21`	`+# Make the sorting.`
	`22`	`+foriinrange(len(array)):`
	`23`	`+index=array[i]-min`
	`24`	`+if(holes[index]!=array[i]):`
	`25`	`+holes[index]=array[i]`
	`26`	`+holes_repeat[index]+=1`
	`27`	`+else:holes_repeat[index]+=1`
	`28`	`+`
	`29`	`+# Makes the array back by replacing the numbers.`
	`30`	`+index=0`
	`31`	`+foriinrange(holes_range):`
	`32`	`+while(holes_repeat[i]>0):`
	`33`	`+array[index]=holes[i]`
	`34`	`+index+=1`
	`35`	`+holes_repeat[i]-=1`
	`36`	`+`
	`37`	`+# Returns the sorted array.`
	`38`	`+returnarray`
	`39`	`+`
	`40`	`+if__name__=='__main__':`
	`41`	`+try:`
	`42`	`+raw_input# Python2`
	`43`	`+exceptNameError:`
	`44`	`+raw_input=input# Python 3`
	`45`	`+`
	`46`	`+user_input=raw_input('Enter numbers separated by comma:\n')`
	`47`	`+unsorted= [int(x)forxinuser_input.split(',')]`
	`48`	`+sorted=pigeon_sort(unsorted)`
	`49`	`+`
	`50`	`+print(sorted)`

Comments

(0)