CODEWITHSUNDEEP
algorithmsorting
Tarasovych
Tarasovych

Reputation: 2398

Understanding sorting algorithm from "Computer Science Distilled" book

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?

Upvotes: 0

Views: 44

Answers (1)

Sergey Romanovsky
Sergey Romanovsky

Reputation: 4564

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)
}

Upvotes: 1

Related Questions