[AOJ: ALDS1] #2-A: Bubble Sort (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A)

bubble_sort.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	N := 0
	sc := bufio.NewScanner(os.Stdin)
	if sc.Scan() {
		N, _ = strconv.Atoi(sc.Text())
	}
	A := make([]int, N)
	if sc.Scan() {
		for i, val := range strings.Fields(sc.Text()) {
			A[i], _ = strconv.Atoi(val)
		}
	}
	result, count := bubbleSort(A, N)
	fmt.Println(String(result))
	fmt.Printf("%#v\n", result)
	fmt.Println(count)
}

func bubbleSort(A []int, N int) ([]int, int) {
	flag := true
	count := 0
	for flag {
		flag = false
		for j := N - 1; j > 0; j-- {
			if A[j] < A[j-1] {
				A[j], A[j-1] = A[j-1], A[j]
				count++
				flag = true
			}
		}
	}
	return A, count
}

func String(A []int) string {
	text := ""
	for i, val := range A {
		if i > 0 {
			text += " "
		}
		text += fmt.Sprint(val)
	}
	return text
}

bubble_sort_test.go

package main

import (
	"bufio"
	"os"
	"reflect"
	"strconv"
	"strings"
	"testing"
)

var bubbleSortTests = []struct {
	name     string
	file     string
	text     string
	want     []int
	attempts int
}{
	{
		name: "just print out the single input number without sorting",
		file: "in1.txt",
		text: `1
100
`,
		want:     []int{100},
		attempts: 0,
	},
	{
		name: "should print out the input numbers without sorting",
		file: "in2.txt",
		text: `5
1 2 3 4 5
`,
		want:     []int{1, 2, 3, 4, 5},
		attempts: 0,
	},
	{
		name: "should print out the sorted input numbers in maximum number of attempts",
		file: "in3.txt",
		text: `6
6 5 4 3 2 1
`,
		want:     []int{1, 2, 3, 4, 5, 6},
		attempts: 15,
	},
	{
		name: "should print out the sorted 10 input numbers",
		file: "in4.txt",
		text: `10
9 5 10 3 6 7 4 1 2 8
`,
		want:     []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
		attempts: 29,
	},
	{
		name: "should print out the sorted bunch of numbers getting from large input",
		file: "in10.txt",
		text: `100
0 33 43 62 29 0 8 52 56 56 19 11 51 43 5 8 93 30 66 69 32 17 47 72 68 80 23 49 92 64 69 51 27 90 24 35 20 44 10 62 84 63 1 10 36 76 31 29 97 75 91 90 44 34 25 29 30 27 26 43 34 4 60 49 20 56 32 72 13 90 9 19 5 95 49 27 19 97 24 96 49 56 84 93 45 7 6 9 54 52 65 83 38 1 90 30 37 95 56 63
`,
		want:     []int{0, 0, 1, 1, 4, 5, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 13, 17, 19, 19, 19, 20, 20, 23, 24, 24, 25, 26, 27, 27, 27, 29, 29, 29, 30, 30, 30, 31, 32, 32, 33, 34, 34, 35, 36, 37, 38, 43, 43, 43, 44, 44, 45, 47, 49, 49, 49, 49, 51, 51, 52, 52, 54, 56, 56, 56, 56, 56, 60, 62, 62, 63, 63, 64, 65, 66, 68, 69, 69, 72, 72, 75, 76, 80, 83, 84, 84, 90, 90, 90, 90, 91, 92, 93, 93, 95, 95, 96, 97, 97},
		attempts: 2264,
	},
}

func TestBubbleSort(t *testing.T) {
	for _, testcase := range bubbleSortTests {
		t.Log(testcase.name)

		f, err := os.Create(testcase.file)
		if err != nil {
			t.Errorf("could not create a file: %s\n  %s", testcase.file, err)
		}
		f.WriteString(testcase.text)
		f.Close()

		f, err = os.Open(testcase.file)
		if err != nil {
			t.Errorf("could not open a file: %s\n  %s", testcase.file, err)
		}

		sc := bufio.NewScanner(f)
		N := 0
		if sc.Scan() {
			N, _ = strconv.Atoi(sc.Text())
		}
		A := make([]int, N)
		if sc.Scan() {
			for i, s := range strings.Fields(sc.Text()) {
				A[i], _ = strconv.Atoi(s)
			}
		}
		f.Close()

		result, counts := bubbleSort(A, N)
		if !reflect.DeepEqual(result, testcase.want) {
			t.Errorf("result => %#v\n, want => %#v", result, testcase.want)
		}
		if !reflect.DeepEqual(counts, testcase.attempts) {
			t.Errorf("result => %#v\n, want => %#v", counts, testcase.attempts)
		}

		if err := os.Remove(testcase.file); err != nil {
			t.Errorf("could not delete a file: %s\n  %s\n", testcase.file, err)
		}
	}
}

func BenchmarkBubbleSort(b *testing.B) {
	for _, testcase := range bubbleSortTests {
		f, err := os.Create(testcase.file)
		if err != nil {
			b.Errorf("could not create a file: %s\n  %s", testcase.file, err)
		}
		f.WriteString(testcase.text)
		f.Close()
	}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for _, testcase := range bubbleSortTests {
			f, _ := os.Open(testcase.file)

			sc := bufio.NewScanner(f)
			N := 0
			if sc.Scan() {
				N, _ = strconv.Atoi(sc.Text())
			}
			A := make([]int, N)
			if sc.Scan() {
				for i, s := range strings.Fields(sc.Text()) {
					A[i], _ = strconv.Atoi(s)
				}
			}
			f.Close()

			bubbleSort(A, N)
		}
	}

	for _, testcase := range bubbleSortTests {
		if err := os.Remove(testcase.file); err != nil {
			b.Errorf("could not delete a file: %s\n  %s\n", testcase.file, err)
		}
	}
}