packagemainimport("fmt""time")//works when the array is sortedfuncbinarySearch(arr[]int,xint)int{i:=0j:=len(arr)fori!=j{varm=(i+j)/2ifx==arr[m]{returnm}ifx<arr[m]{j=m}else{i=m+1}}return-1}funcmain(){items:=[]int{2,3,5,7,11,13,17}fmt.Println(binarySearch(items,1))//print -1fmt.Println(binarySearch(items,7))//print 3fmt.Println(binarySearch(items,19))//print -1// *** simplified speed test ***items=make([]int,10000000)fori:=0;i<len(items);i++{items[i]=i}count:=100start:=time.Now()fori:=0;i<count;i++{binarySearch(items,7777777)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()/int64(count)fmt.Println(nanoseconds)// about 88 nanoseconds}
Fast linear search
packagemainimport("fmt""time")funcfastLinearSearch(arr[]int,xint)int{i:=0count:=len(arr)arr=append(arr,x)fortrue{ifarr[i]==x{ifi<count{returni}return-1}i++}return-1}funcmain(){items:=[]int{2,3,5,7,11,13,17}fmt.Println(fastLinearSearch(items,1))//print -1fmt.Println(fastLinearSearch(items,7))//print 3fmt.Println(fastLinearSearch(items,19))//print -1// *** simplified speed test ***items=make([]int,10000000)fori:=0;i<len(items);i++{items[i]=i}count:=100start:=time.Now()fori:=0;i<count;i++{fastLinearSearch(items,7777777)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()/int64(count)fmt.Println(nanoseconds)// about 34 148 000 nanoseconds}
Interpolation search
packagemainimport("fmt""time")//works when the array is sortedfuncinterpolationSearch(arr[]int,xint)int{low:=0high:=len(arr)-1for(arr[low]<x)&&(x<arr[high]){varmid=low+((x-arr[low])*(high-low))/(arr[high]-arr[low])ifarr[mid]<x{low=mid+1}elseifarr[mid]>x{high=mid-1}else{returnmid}}ifarr[low]==x{returnlow}ifarr[high]==x{returnhigh}return-1}funcmain(){items:=[]int{2,3,5,7,11,13,17}fmt.Println(interpolationSearch(items,1))//print -1fmt.Println(interpolationSearch(items,7))//print 3fmt.Println(interpolationSearch(items,19))//print -1// *** simplified speed test ***items=make([]int,10000000)fori:=0;i<len(items);i++{items[i]=i}count:=100start:=time.Now()fori:=0;i<count;i++{interpolationSearch(items,7777777)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()/int64(count)fmt.Println(nanoseconds)// about 41 nanoseconds}
Linear search
packagemainimport("fmt""time")funclinearSearch(arr[]int,xint)int{i:=0count:=len(arr)fori<count{ifarr[i]==x{returni}i++}return-1}funcmain(){items:=[]int{2,3,5,7,11,13,17}fmt.Println(linearSearch(items,1))//print -1fmt.Println(linearSearch(items,7))//print 3fmt.Println(linearSearch(items,19))//print -1// *** simplified speed test ***items=make([]int,10000000)fori:=0;i<len(items);i++{items[i]=i}count:=100start:=time.Now()fori:=0;i<count;i++{linearSearch(items,7777777)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()/int64(count)fmt.Println(nanoseconds)// about 20 910 000 nanoseconds}
Bubble sort
packagemainimport("fmt""time")// Time Complexity O(n^2)// Space Complexity O(1)funcbubbleSort(arr[]int)[]int{length:=len(arr)items:=make([]int,length)copy(items,arr)fori:=0;i<length;i++{forj:=i+1;j<length;j++{ifitems[j]<items[i]{vartmp=items[j]items[j]=items[i]items[i]=tmp}}}returnitems}funcmain(){items:=[]int{4,1,5,3,2}sortItems:=bubbleSort(items)// sortItems is {1, 2, 3, 4, 5}// *** simplified speed test ***items=make([]int,200)fori:=0;i<len(items);i++{items[i]=i}vartmp=items[5]items[5]=items[6]items[6]=tmpcount:=10000start:=time.Now()fori:=0;i<count;i++{bubbleSort(items)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()fmt.Println(sortItems)fmt.Println(nanoseconds)// about 683 000 000 nanoseconds}
Counting sort
packagemainimport("fmt""math""time")// Time Complexity O(n+k)// Space Complexity O(k)funccountingSort(arr[]int)[]int{length:=len(arr)items:=make([]int,length)copy(items,arr)varmin=math.MaxInt32varmax=math.MinInt32for_,x:=rangearr{ifx>max{max=x}ifx<min{min=x}}varcounts=make([]int,max-min+1)for_,x:=rangearr{counts[x-min]++}vartotal=0fori:=min;i<=max;i++{varoldCount=counts[i-min]counts[i-min]=totaltotal+=oldCount}for_,x:=rangearr{items[counts[x-min]]=xcounts[x-min]++}returnitems}funcmain(){items:=[]int{4,1,5,3,2}sortItems:=countingSort(items)// sortItems is {1, 2, 3, 4, 5}// *** simplified speed test ***items=make([]int,200)fori:=0;i<len(items);i++{items[i]=i}vartmp=items[5]items[5]=items[6]items[6]=tmpcount:=10000start:=time.Now()fori:=0;i<count;i++{countingSort(items)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()fmt.Println(sortItems)fmt.Println(nanoseconds)// about 58 000 000 nanoseconds}
Merge sort
packagemainimport("fmt""time")// Time Complexity O(n log(n)))// Space Complexity O(n)funcmergeSort(arr[]int)[]int{items:=make([]int,len(arr))copy(items,arr)doMergeSort(items)returnitems}funcdoMergeSort(items[]int){length:=len(items)iflength==1{return}varlLeft=length/2varleft=make([]int,lLeft)copy(left,items[:lLeft])varlRight=length-lLeftvarright=make([]int,lRight)copy(right,items[lLeft:])doMergeSort(left)doMergeSort(right)merge(left,right,items)}funcmerge(left[]int,right[]int,result[]int){l:=0r:=0i:=0forl<len(left)&&r<len(right){ifleft[l]<right[r]{result[i]=left[l]l++}else{result[i]=right[r]r++}i++}varlength=len(left)-lcopy(result[i:i+length],left[l:])i=i+lengthlength=len(right)-rcopy(result[i:i+length],right[r:])}funcmain(){items:=[]int{4,1,5,3,2}sortItems:=mergeSort(items)// sortItems is {1, 2, 3, 4, 5}// *** simplified speed test ***items=make([]int,200)fori:=0;i<len(items);i++{items[i]=i}vartmp=items[5]items[5]=items[6]items[6]=tmpcount:=10000start:=time.Now()fori:=0;i<count;i++{mergeSort(items)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()fmt.Println(sortItems)fmt.Println(nanoseconds)// about 439 000 000 nanoseconds}
Quick sort
packagemainimport("fmt""time")// Time Complexity from O(n log(n)) to O(n^2)// Space Complexity O(log(n))funcdoSort(items[]int,fstint,lstint){iffst>=lst{return}i:=fstj:=lstx:=items[(fst+lst)/2]fori<j{foritems[i]<x{i++}foritems[j]>x{j--}ifi<=j{vartmp=items[i]items[i]=items[j]items[j]=tmpi++j--}}doSort(items,fst,j)doSort(items,i,lst)}funcquicksort(arr[]int)[]int{length:=len(arr)items:=make([]int,length)copy(items,arr)doSort(items,0,length-1)returnitems}funcmain(){items:=[]int{4,1,5,3,2}sortItems:=quicksort(items)// sortItems is {1, 2, 3, 4, 5}// *** simplified speed test ***items=make([]int,200)fori:=0;i<len(items);i++{items[i]=i}vartmp=items[5]items[5]=items[6]items[6]=tmpcount:=10000start:=time.Now()fori:=0;i<count;i++{quicksort(items)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()fmt.Println(sortItems)fmt.Println(nanoseconds)// about 83 000 000 nanoseconds}
Redix sort
packagemainimport("fmt""math""time")// Time Complexity O(nk)// Space Complexity O(n+k)funclistToBuckets(items[]int,cBaseint,iint)[][]int{varbuckets=make([][]int,cBase)varpBase=int(math.Pow(float64(cBase),float64(i)))for_,x:=rangeitems{//Isolate the base-digit from the numbervardigit=(x/pBase)%cBase//Drop the number into the correct bucketbuckets[digit]=append(buckets[digit],x)}returnbuckets}funcbucketsToList(buckets[][]int)[]int{result:=[]int{}for_,bucket:=rangebuckets{result=append(result,bucket...)}returnresult}funcradixSort(arr[]int,cBaseint)[]int{maxVal:=0fori,value:=rangearr{ifi==0||value>maxVal{maxVal=value}}length:=len(arr)items:=make([]int,length)copy(items,arr)i:=0formath.Pow(float64(cBase),float64(i))<=float64(maxVal){items=bucketsToList(listToBuckets(items,cBase,i))i++}returnitems}funcmain(){items:=[]int{4,1,5,3,2}sortItems:=radixSort(items,10)// sortItems is {1, 2, 3, 4, 5}// *** simplified speed test ***items=make([]int,200)fori:=0;i<len(items);i++{items[i]=i}vartmp=items[5]items[5]=items[6]items[6]=tmpcount:=10000start:=time.Now()fori:=0;i<count;i++{radixSort(items,10)}delta:=time.Now().Sub(start)nanoseconds:=delta.Nanoseconds()fmt.Println(sortItems)fmt.Println(nanoseconds)// about 532 200 000 nanoseconds}
Top comments (0)
Subscribe
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)