Data Structures & Algorithms In Go/

...

/

Solution Review: Sorting From 1 to n

Solution Review: Sorting From 1 to n

This review provides a detailed analysis of the different ways to sort numbers from 1 to n.

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

Press + to interact
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 ...