Last active
May 1, 2018 06:57
-
-
Save toVersus/4ffd86c3b29c194a879a6d258f0dc1a3 to your computer and use it in GitHub Desktop.
[AOJ: ALDS1] #2-B: Selection Sort (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 := selectionSort(A, N) | |
fmt.Println(String(result)) | |
fmt.Println(count) | |
} | |
func selectionSort(A []int, N int) ([]int, int) { | |
count := 0 | |
for i := 0; i < N-1; i++ { | |
minj := i | |
for j := i; j < N; j++ { | |
if A[j] < A[minj] { | |
minj = j | |
} | |
} | |
if i == minj { | |
continue | |
} | |
A[i], A[minj] = A[minj], A[i] | |
count++ | |
} | |
return A, count | |
} | |
func String(A []int) string { | |
text := "" | |
for i, val := range A { | |
if i > 0 { | |
text += " " | |
} | |
text += fmt.Sprint(val) | |
} | |
return text | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"bufio" | |
"os" | |
"reflect" | |
"strconv" | |
"strings" | |
"testing" | |
) | |
var selectionSortTests = []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: 3, | |
}, | |
{ | |
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: 9, | |
}, | |
{ | |
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: 95, | |
}, | |
} | |
func TestSelectionSort(t *testing.T) { | |
for _, testcase := range selectionSortTests { | |
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) | |
} | |
N := 0 | |
sc := bufio.NewScanner(f) | |
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) | |
} | |
} | |
f.Close() | |
result, counts := selectionSort(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 BenchmarkSelectionSort(b *testing.B) { | |
for _, testcase := range selectionSortTests { | |
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 selectionSortTests { | |
b.StopTimer() | |
f, _ := os.Open(testcase.file) | |
b.StartTimer() | |
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() | |
selectionSort(A, N) | |
} | |
} | |
for _, testcase := range selectionSortTests { | |
if err := os.Remove(testcase.file); err != nil { | |
b.Errorf("could not delete a file: %s\n %s\n", testcase.file, err) | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment