Understanding sorting algorithm from "Computer Science Distilled" book

Question

What do I have: algorithm in pseudocode from the "Computer Science Distilled" book (p. 27)

function selection_sort(list)
    for current <- 1 ... list.length - 1
        smallest <- current
        for i <- current + 1 ... list.length
            if list[i] < list[smallest]
                smallest <- i
        list.swap_items(current, smallest)

I'm trying to understand it, so I wrote it in Go:

func main() {
    list := []int{5, 2, 7, 9}
    for current := 1; current < len(list)-1; current++ {
        smallest := current
        for i := current + 1; i < len(list); i++ {
            if list[i] < list[smallest] {
                smallest = i
            }
        }
        current_tmp := list[current]
        smallest_tmp := list[smallest]
        list[current], list[smallest] = smallest_tmp, current_tmp
    }
    fmt.Printf("%v\n", list)
}

Playground

And output is [5 2 7 9]. Am I missing something?

Sergey Romanovsky · Accepted Answer · 2020-04-03 07:36:59Z

1

I don't know Go, but googling confirms that Go has zero based numbering. In your example you start from 1 (should be 0).

Another thing -- why do you need current_tmp and smallest_tmp?

So I suggest the following:

func main() {
    list := []int{5, 2, 7, 9}
    for current := 0; current < len(list)-1; current++ {
        smallest := current
        for i := current + 1; i < len(list); i++ {
            if list[i] < list[smallest] {
                smallest = i
            }
        }
        list[current], list[smallest] = list[smallest], list[current]
    }
    fmt.Printf("%v\n", list)
}

answered Apr 3, 2020 at 7:36

Sergey Romanovsky

4,6045 gold badges28 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Understanding sorting algorithm from "Computer Science Distilled" book

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related