Movatterモバイル変換


[0]ホーム

URL:


Skip to content
DEV Community
Log in Create account

DEV Community

Cover image for Sorting Algorithms in Go
Adnan Babakan (he/him)
Adnan Babakan (he/him)

Posted on • Edited on

     

Sorting Algorithms in Go

Hey, Dev.to community!

As a little project, I've written some famous sort algorithms using Go. I hope this would be useful for you!

Table of contents

Bubble Sort

Bubble sort is a very easy algorithm to follow. You need to check every element of an array against the next element to see if it is larger, if so, you need to swap them. You should do this task as many times as finally there wouldn't be any swap action needed.

packagemainimport"fmt"funcmain(){varn=[]int{1,39,2,9,7,54,11}varisDone=falsefor!isDone{isDone=truevari=0fori<len(n)-1{ifn[i]>n[i+1]{n[i],n[i+1]=n[i+1],n[i]isDone=false}i++}}fmt.Println(n)}
Enter fullscreen modeExit fullscreen mode

Recursive Bubble Sort

Recursive bubble sort is a variation of the normal bubble sort (also knows as iterative bubble sort). This works the same as the iterative bubble sort with no extra advantages over time or complexity XD. But this will improve your understanding of bubble sort and recursion:

packagemainimport"fmt"funcbubbleSort(arr[]int,sizeint)[]int{ifsize==1{returnarr}vari=0fori<size-1{ifarr[i]>arr[i+1]{arr[i],arr[i+1]=arr[i+1],arr[i]}i++}bubbleSort(arr,size-1)returnarr}funcmain(){varn=[]int{1,39,2,9,7,54,11}fmt.Println(bubbleSort(n,len(n)))}
Enter fullscreen modeExit fullscreen mode

Insertion Sort

Insertion sort is a famous sorting algorithm that works like sorting a deck of cards in hand. As you proceed through the elements of an array you would move it back until it is in the correct place.

Insertion Sort

Credits to https://www.geeksforgeeks.org/
packagemainimport"fmt"funcmain(){varn=[]int{1,39,2,9,7,54,11}vari=1fori<len(n){varj=iforj>=1&&n[j]<n[j-1]{n[j],n[j-1]=n[j-1],n[j]j--}i++}fmt.Println(n)}
Enter fullscreen modeExit fullscreen mode

Selection Sort

Selection sort is quite interesting and yet simple. What you need to do is simply replace the current element in iteration by the lowest value on the right. As you go further the left part of the array is sorted, and you don't need to check for the last element.

Selection sort

packagemainimport"fmt"funcmain(){varn=[]int{1,39,2,9,7,54,11}vari=1fori<len(n)-1{varj=i+1varminIndex=iifj<len(n){ifn[j]<n[minIndex]{minIndex=j}j++}ifminIndex!=i{vartemp=n[i]n[i]=n[minIndex]n[minIndex]=temp}i++}fmt.Println(n)}
Enter fullscreen modeExit fullscreen mode

Merge Sort

Merge is a quite fast sorting algorithm. In a merge sort, you should utilize the divide-and-conquer practice. First, you'll divide the passed array by 2 recursively, until you reach the length of 1, then you should merge them. To merge two arrays that we know are already sorted themselves you can implement a simple function called merge.

Merge sort

packagemainimport"fmt"funcmerge(fp[]int,sp[]int)[]int{varn=make([]int,len(fp)+len(sp))varfpIndex=0varspIndex=0varnIndex=0forfpIndex<len(fp)&&spIndex<len(sp){iffp[fpIndex]<sp[spIndex]{n[nIndex]=fp[fpIndex]fpIndex++}elseifsp[spIndex]<fp[fpIndex]{n[nIndex]=sp[spIndex]spIndex++}nIndex++}forfpIndex<len(fp){n[nIndex]=fp[fpIndex]fpIndex++nIndex++}forspIndex<len(sp){n[nIndex]=sp[spIndex]spIndex++nIndex++}returnn}funcmergeSort(arr[]int)[]int{iflen(arr)==1{returnarr}varfp=mergeSort(arr[0:len(arr)/2])varsp=mergeSort(arr[len(arr)/2:])returnmerge(fp,sp)}funcmain(){varn=[]int{1,39,2,9,7,54,11,8}fmt.Println(mergeSort(n))}
Enter fullscreen modeExit fullscreen mode

Counting Sort

Counting sort is a really simple yet complicated sorting algorithm. To understand how counting sort works you can watch the video below from GeekforGeeks:

Here is the Go code:

packagemainimport"fmt"funccountSort(arr[]int)[]int{varmax=arr[0]vari=1fori<len(arr){ifarr[i]>max{max=arr[i]}i++}varindices=make([]int,max+1)varj=0forj<len(arr){indices[arr[j]]++j++}vark=1fork<len(indices){indices[k]+=indices[k-1]k++}varresult=make([]int,len(arr))varm=0form<len(arr){result[indices[arr[m]]-1]=arr[m]indices[arr[m]]--m++}returnresult}funcmain(){varn=[]int{1,39,2,9,7,54,11}fmt.Println(countSort(n))}
Enter fullscreen modeExit fullscreen mode

I will complete this list by time.

BTW! Check out my free Node.js Essentials E-book here:

Top comments(5)

Subscribe
pic
Create template

Templates let you quickly answer FAQs or store snippets for re-use.

Dismiss
CollapseExpand
 
jacobalberty profile image
Jacob Alberty
  • Joined

Your bubble sort contains an error. The output is[1 2 9 7 39 11 54] which is clearly not fully sorted. It only does one iteration. Just need to add anisDone = false inside of the if statement

packagemainimport"fmt"funcmain(){varn=[]int{1,39,2,9,7,54,11}varisDone=falsefor!isDone{isDone=truevari=0fori<len(n)-1{ifn[i]>n[i+1]{n[i],n[i+1]=n[i+1],n[i]isDone=false}i++}}fmt.Println(n)}
Enter fullscreen modeExit fullscreen mode
CollapseExpand
 
adnanbabakan profile image
Adnan Babakan (he/him)
I'm Adnan Babakan and I'm from Iran. I started programming since I was 8 and now I'm 24. I love programming!

Thank you so much for spotting the error. Don't know how missed that. :)

CollapseExpand
 
robert profile image
Robert Wallis
20/yr Software Developer, DevOps Full-Stack 3D AR/VR.

Nice article!

Go has swap withouttemp

n[i],n[i+1]=n[i+1],n[i]
Enter fullscreen modeExit fullscreen mode
CollapseExpand
 
adnanbabakan profile image
Adnan Babakan (he/him)
I'm Adnan Babakan and I'm from Iran. I started programming since I was 8 and now I'm 24. I love programming!

Oh nice, thanks for the tip. I just started to learn Go and it is fascinating. :)

CollapseExpand
 
blitzkriegcoding profile image
Yrvin Escorihuela
  • Joined

What it means those pronouns in your bio?

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment'spermalink.

For further actions, you may consider blocking this person and/orreporting abuse

I'm Adnan Babakan and I'm from Iran. I started programming since I was 8 and now I'm 24. I love programming!
  • Location
    Iran
  • Work
    Full-stack Web Developer
  • Joined

More fromAdnan Babakan (he/him)

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Log in Create account

[8]ページ先頭

©2009-2025 Movatter.jp