1. A test harness program fro testing sorting methods is provided with the rest
ID: 3764658 • Letter: 1
Question
1. A test harness program fro testing sorting methods is provided with the rest of the textbook program files. It is the file Sorts.java in the ch10 package. The program includes a swap method that is used by all of the sorting methods to swap array elements.
Describe an approach to modifying the program so that after calling a sorting method the program prints out the number of swaps needed by the sorting method.
Implement your approach.
Test your new program by running the selectionSort method. Your program should report 49 swaps.
Explanation / Answer
def selection_sort!(a)
for i in 0..a.size-2 do
# Invariant: a[0..i-1] contain smallest values in order
smallest = i
for j in i+1..a.size-1 do
# Invariant: a[smallest] is the smallest value in a[i..j-1]
if a[j] < a[smallest]
smallest = j
end
end
a[i], a[smallest] = a[smallest], a[i]
end
end
def selection_sort!(a)
for i in 0..a.size-2 do
# Invariant: a[0..i-1] contain smallest values in order
smallest = i
for j in i+1..a.size-1 do
# Invariant: a[smallest] is the smallest value in a[i..j-1]
if a[j] < a[smallest]
smallest = j
end
end
a[i], a[smallest] = a[smallest], a[i]
end
end
def selection_sort!(a)
for i in 0..a.size-2 do
# Invariant: a[0..i-1] contain smallest values in order
smallest = i
for j in i+1..a.size-1 do
# Invariant: a[smallest] is the smallest value in a[i..j-1]
if a[j] < a[smallest]
smallest = j
end
end
a[i], a[smallest] = a[smallest], a[i]
end
end
tests = [
[],
[ 0 ],
[ 0, 0 ],
[ 0, 0, 0 ],
[ 0, 1 ],
[ 1, 0 ],
[ 0, 1, 2 ],
[ 0, 2, 1 ],
[ 1, 0, 2 ],
[ 1, 2, 0 ],
[ 2, 0, 1 ],
[ 2, 1, 0 ],
[ 0, 1, 1 ],
[ 1, 0, 1 ],
[ 1, 1, 0 ],
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ],
[ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ],
[ 42, 9, 17, 54, 602, -3, 54, 999, -11 ],
[ -11, -3, 9, 17, 42, 54, 54, 602, 999 ],
]
random_tests = []
10.times do
a = []
rand(100).times do
a << rand(1000000)-500000
end
random_tests << a
end
ntests = 0
nok = 0
(tests + random_tests).each_with_index do |a, i|
copy = a.clone
selection_sort!(copy)
if (copy == a.sort)
nok += 1
else
puts "failed test #{i}: [#{a.join(' ')}] -> [#{copy.join(' ')}]"
end
ntests += 1
end
printf "passed %d of %d tests (%d%%) ", nok, ntests, 100*nok/ntests
I suggest that this is a pretty good set of tests (especially if you turn up the number, size and range of the randomly generated arrays), and I’d like to humbly suggest that those of you who have claimed success for your routines might like to translate this test suite into your implementation language and check that your routines really do work.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.