Anonymous user
Sorting algorithms/Bubble sort: Difference between revisions
Added entry for Eiffel.
m (moving S(ather) up after ruby :/) |
(Added entry for Eiffel.) |
||
Line 485:
(Uses the primitive __loop directly because it happens to map to the termination test for this algorithm well.)
=={{header|Eiffel}}==
This solution is presented in two classes. The first is a simple application that creates a set, an instance of <code lang="eiffel">MY_SORTED_SET</code>, and adds elements to the set in unsorted order. It iterates across the set printing the elements, then it sorts the set, and reprints the elements.
<lang eiffel>class
APPLICATION
create
make
feature
make
-- Create and print sorted set
do
create my_set.make
my_set.put_front (2)
my_set.put_front (6)
my_set.put_front (1)
my_set.put_front (5)
my_set.put_front (3)
my_set.put_front (9)
my_set.put_front (8)
my_set.put_front (4)
my_set.put_front (10)
my_set.put_front (7)
print ("Before: ")
across my_set as ic loop print (ic.item.out + " ") end
print ("%NAfter : ")
my_set.sort
across my_set as ic loop print (ic.item.out + " ") end
end
my_set: MY_SORTED_SET [INTEGER]
-- Set to be sorted
end</lang>
The second class is <code lang="eiffel">MY_SORTED_SET</code>.
<lang eiffel>class
MY_SORTED_SET [G -> COMPARABLE]
inherit
TWO_WAY_SORTED_SET [G]
redefine
sort
end
create
make
feature
sort
-- Sort with bubble sort
local
l_unchanged: BOOLEAN
l_item_count: INTEGER
l_temp: G
do
from
l_item_count := count
until
l_unchanged
loop
l_unchanged := True
l_item_count := l_item_count - 1
across 1 |..| l_item_count as ic loop
if Current [ic.item] > Current [ic.item + 1] then
l_temp := Current [ic.item]
Current [ic.item] := Current [ic.item + 1]
Current [ic.item + 1] := l_temp
l_unchanged := False
end
end
end
end
end</lang>
This class inherits from the Eiffel library class <code lang="eiffel">TWO_WAY_SORTED_SET</code>, which implements sets whose elements are comparable. Therefore, the set can be ordered and in fact is kept so under normal circumstances.
<code lang="eiffel">MY_SORTED_SET</code> redefines only the routine <code lang="eiffel">sort</code> which contains the implementation of the sort algorithm. The implementation in the redefined version of <code lang="eiffel">sort</code> in <code lang="eiffel">MY_SORTED_SET</code> uses a bubble sort.
Output:
<pre>
Before: 7 10 4 8 9 3 5 1 6 2
After : 1 2 3 4 5 6 7 8 9 10
</pre>
<code lang="eiffel">TWO_WAY_SORTED_SET</code> is implemented internally as a list. For this example, we use the feature <code lang="eiffel">put_front</code> which explicitly adds each new element to the beginning of the list, allowing us to show that the elements are unordered until we sort them. It also causes, in the "Before" output, the elements to be printed in the reverse of the order in which they were added. Under normal circumstances, we would use the feature <code lang="eiffel">extend</code> (rather than <code lang="eiffel">put_front</code>) to add elements to the list. This would assure that the order was maintained even as elements were added.
=={{header|Factor}}==
| |||