Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Sorting From 1 to n

Understand and analyze two efficient Go solutions for sorting arrays containing elements from 1 to n. Learn how nested loops and swap operations reposition elements correctly in linear time, improving your array manipulation and algorithm skills in Go.

We'll cover the following...

First solution

This solution consists of two nested loops. The outer loop will replace the value at index i with -1. The inner loop will do the following:

  • Store the current value temporarily.
  • Set the required value at the proper index.
  • Set value for the next iteration.
  • Set the cursor for the next iteration.

Let’s look more through illustrations.

Solution code

Go (1.6.2)
package main
import "fmt"
func Sort1toN(arr []int, size int) { 
    curr, value, next := 0, 0, 0
    for i := 0; i < size; i++ {
      curr = i
      value = -1
      /* swaps to move elements in the proper position. */ 
      for curr >= 0 && curr < size && arr[curr] != curr+1 {
        next = arr[curr] 
        arr[curr] = value 
        value = next  
        curr = next - 1 
              
      } 
    }
}
//Testing code
func main() {
    arr := []int{5, 3, 2, 1, 4}
    size := len(arr)
    Sort1toN(arr, size)
    fmt.Println(arr)
}

Time complexity

The time complexity is O(n ...