How to use moves logic in Go?

How to use moves logic in Golang? for example: I have an array = [1,2,3,4,5] so how can I create a function by using which all odd numbers come to the start of the array? and even number goes in the end in one move or at least in minimal moves?

3 Likes

Could this help you:

package main

import (
	"fmt"
)

func main() {
	list := []int{1, 2, 3, 4, 5, 6}
	even := []int{}
	odd := []int{}
    sorted := []int{}

	for i := range list {
		if list[i]%2 == 0 {
			even = append(even, list[i])
		}
	}
	for i := range list {
		if list[i]%2 != 0 {
			odd = append(odd, list[i])
		}
	}

	sorted = append(odd, even...)
	fmt.Println(sorted)
}
1 Like

I think the algorithm you’re looking for is “partition.” I wrote a naive implementation in the playground here that seems to work, but I wouldn’t put it into production without further testing:

https://play.golang.org/p/bBXucwR_Npg

To minimize moves, the partition is not stable. The pivot returned is the index that separates the values where the predicate evaluated to true vs. those where it was false, e.g.:

ints := []int{1, 2, 3, 4, 5}
pivot := partitionInts(ints, func(i int) bool { return i&1 == 1 })
odds := ints[:pivot]
evens := ints[pivot:]

A minimal move, efficient implementation:

package main

import "fmt"

func oddeven(a []int) {
	for i, j := 0, len(a)-1; i < j; i++ {
		if a[i]&1 == 0 {
			for ; i < j; j-- {
				if a[j]&1 != 0 {
					a[i], a[j] = a[j], a[i]
					break
				}
			}
		}
	}
}

func main() {
	a := []int{1, 2, 3, 4, 5, 0, -1, -2, -3, -4, -5}
	fmt.Println(a)
	oddeven(a)
	fmt.Println(a)
}

https://play.golang.org/p/2aIDNdkHDed

[1 2 3 4 5 0 -1 -2 -3 -4 -5]
[1 -5 3 -3 5 -1 0 -2 4 -4 2]
2 Likes