7 sorting algorithms

Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quicksort, Heapsort, Counting Sort

Here are 7 sorting algorithms implementations in Go that we are going to cover in this post:

  1. Bubble Sort
  2. Selection Sort
  3. Insertion Sort
  4. Merge Sort
  5. Quicksort
  6. Heapsort
  7. Counting Sort

Bubble Sort

Approach:

Repeatedly swap the adjacent elements if they are in the wrong order in the
array, one item at a time.

Cost:

O(n^2) time and O(1) space.

Solution:

func bubbleSort(in []int) {
	length := len(in)

	// for each element in the list, check it with almost every other element.
	for i := 0; i < length; i++ {
		// since the last i element is already in place, only iterate through
		// the item before the last one.
		for j := 0; j < length-i-1; j++ {
			// swap the adjacent elements if they are not in ascending order.
			if in[j] > in[j+1] {
				common.Swap(in, j, j+1)
			}
		}
	}
}

Selection Sort

Approach:

Repeatedly select the next smallest element from the unsorted array and move it
to the front.

Cost:

O(n^2) time and O(1) space.

Solution:

func selectionSort(in []int) {
	minIndex := 0
	for i := 0; i < len(in)-1; i++ {
		minIndex = i
		// find the minimum in the rest of the array.
		for j := i + 1; j < len(in); j++ {
			if in[j] < in[minIndex] {
				minIndex = j
			}
		}

		// swap the minimum value with the first value.
		common.Swap(in, i, minIndex)
	}
}

Insertion Sort

Approach:

Insert elements from an unsorted array into a sorted subsection of the
array, one item at a time.

Cost:

O(n^2) time and O(1) space.

Solution:

func insertionSort(in []int) {
	// iterate through the list from position 1.
	for i := 1; i < len(in); i++ {
		// shift each one to the left by swapping it with the one before until
		// it's in the right spot.
		current := in[i]
		j := i - 1

		for j >= 0 && current < in[j] {
			in[j+1] = in[j]
			j--
		}

		in[j+1] = current
	}
}

Merge Sort

Approach:

Split the input in half, recursively sorts each half, then merge the
sorted halves back together.

Cost:

O(nlogn) time and O(n) space.

Solution:

func mergeSort(in []int) []int {
	// base case
	if len(in) <= 1 {
		return in
	}

	// split the input in half.
	middleIndex := len(in) / 2
	left := in[:middleIndex]
	right := in[middleIndex:]

	// sort each half.
	leftSorted := mergeSort(left)
	rightSorted := mergeSort(right)

	// merge the sorted halves.
	return mergeSortedArray(leftSorted, rightSorted)
}

func mergeSortedArray(a1, a2 []int) []int {
	out := []int{}

	// keep two "pointer" at index 0 and move up accordingly as one get
	// merged in.
	i, j := 0, 0
	for i < len(a1) && j < len(a2) {
		if a1[i] < a2[j] {
			out = append(out, a1[i])
			i++
		} else {
			out = append(out, a2[j])
			j++
		}
	}

	// if we get here, one array must have bigger size than the other. could
	// figure out which one is it then copy the rest of its to our final one.
	if i < len(a1) {
		out = append(out, a1[i:]...)
	}

	if j < len(a2) {
		out = append(out, a2[j:]...)
	}

	return out
}

Quicksort

Approach:

Recursively divide the input into two smaller arrays around a pivot, where
one half has items smaller than the pivot, other half has items bigger than
the pivot.

Cost:

O(nlogn) time and O(nlogn) space.

Solution:

func quicksort(in []int, start, end int) {
	if start < end {
		// pi is the pivot/partition index.
		pi := partition(in, start, end)

		// sort the items before and after partition.
		quicksort(in, start, pi-1)
		quicksort(in, pi+1, end)
	}
}

func partition(in []int, start, end int) int {
	pivot := in[end]

	left := start
	right := end - 1

	for left <= right {
		// keep going until we find something on the left that belongs to the
		// right.
		for left <= end && in[left] < pivot {
			left++
		}

		// keep going until we find something on the right that belongs to the
		// left.
		for right >= start && in[right] >= pivot {
			right--
		}

		// by swapping the item at left and right index, we move the item that
		// is smaller than the pivot to the left half and vice versa.
		if left < right {
			common.Swap(in, left, right)
		} else {
			// once the partition is finished, move the pivot back to its final
			// position by swapping the item at left and end index.
			common.Swap(in, left, end)
		}
	}

	return left
}

Heapsort

Approach:

Similar to selection sort, repeatedly choose the largest item and move it to
the end of the array using a max heap.

Cost:

O(nlogn) time and O(1) space.

Solution:

func heapsort(in []int) {
	heapify(in)

	size := len(in)
	for size > 0 {
		// repeatedly remove the largest item.
		largest := removeLargest(in, size)

		// update the heap size.
		size--

		// store the removed value at the end of the list.
		in[size] = largest
	}
}

// heapify transform the input into a max heap.
func heapify(in []int) {
	for i := len(in) - 1; i > -1; i-- {
		bubbleDown(in, len(in), i)
	}
}

// bubbleDown allow larger values to reach the top.
func bubbleDown(heap []int, heapSize int, index int) {
	for index < heapSize {
		// fast-calculate the children left and right index.
		left := index*2 + 1
		right := index*2 + 2

		// stop if there is no child node.
		if left >= heapSize {
			break
		}

		// find the larger index
		larger := left
		if right < heapSize && heap[left] < heap[right] {
			larger = right
		}

		// if the current item is larger than both children, we're done.
		// if not, swap with the larger child.
		if heap[index] < heap[larger] {
			common.Swap(heap, index, larger)
		} else {
			break
		}
	}
}

// removeLargest remove and return the largest item from the heap.
func removeLargest(heap []int, heapSize int) int {
	// largest item is at the top of our max heap.
	largest := heap[0]

	// move the last item into the root position.
	heap[0] = heap[heapSize-1]

	// bubble down from the root to restore the heap.
	bubbleDown(heap, heapSize-1, 0)

	return largest
}

Counting Sort

Approach:

Iterate through the input, count the number of times each item occurs, use
these counts to compute each item's index in the final sorted array.

Cost:

O(n) time and O(n) space.

Solution:

func countingSort(in []int, max int) []int {
	// utilize max value to create a fix-sized list of item counts.
	counts := make([]int, max+1)
	out := make([]int, 0)

	// populate the array where its indices represent items themselves and
	// its values represent how many time the item appears.
	for _, item := range in {
		counts[item]++
	}

	// iterate through the counts and add the item to the output list.
	for i := 0; i < len(counts); i++ {
		count := counts[i]

		for j := 0; j < count; j++ {
			out = append(out, i)
		}
	}

	return out
}

For more coding problems, please visit https://github.com/hoanhan101/algo.



Tagged: #algorithm, #sorting