Sorting algorithms/Bubble sort: Difference between revisions
Content added Content deleted
m (fix tags) |
|||
| Line 654: | Line 654: | ||
END</lang> |
END</lang> |
||
=={{header|Icon}}== |
=={{header|Icon and Unicon}}== |
||
While bubble sort is a basic algorithm it also illustrates a difference in the way Icon handles types. The built-in operators for comparing data types make a syntactic distinction between numeric and string types. Consequently, when writing something like a bubble sort you must (a) write two versions, (b) have the sort figure it out dynamically as in this example. In practice this is unnecessary as there are built-in sort functions for basic data types and records. |
|||
<lang Icon>procedure bubblesort(X,op) #: simple bubble sort |
|||
local i,sorted |
|||
==={{header|Icon}}=== |
|||
op := case op of { # select how to sort |
|||
"<<"|">>"|"<<="|">>="|"<"|">"|"<="|">=": proc(op,2) |
|||
"string": proc("<<",2) |
|||
"numeric": proc("<",2) |
|||
&null: if type(X[1]) == "string" then proc("<<",2) |
|||
else proc("<",2) |
|||
default: runerr(123,op) |
|||
} |
|||
While bubble sort is a basic algorithm it also illustrates a difference in the way Icon handles types. Built-in |
|||
while /sorted := 1 do # the sort |
|||
operators for comparing data types make a syntactic distinction between numeric and string types, and sorting |
|||
every i := 2 to *X do |
|||
structured and user-defined types requires custom code. The following code |
|||
if op(X[i],X[i-1]) then { |
|||
allows the user to specify the type of comparison to use but handles integer |
|||
X[i-1] :=: X[i] |
|||
or string lists automatically. |
|||
sorted := &null |
|||
<lang icon>invocable all |
|||
} |
|||
return X |
|||
end</lang> |
|||
procedure bubblesort(X,op) #: simple bubble sort |
|||
This code will demonstrate the bubble sort using arguments supplied as arguments. The last sort call on a string rather than a list illustrates how many Icon operators work on different types. The example could be made more general to deal with coercion of types like cset to sting (admittedly an uninteresting example as csets are already sorted). |
|||
local i,sorted |
|||
<lang Icon>procedure main(l2) #: demo bubblesort |
|||
op := case op of { # select how to sort |
|||
"string": "<<" |
|||
"numeric": "<" |
|||
&null: if type(X[1]) == "string" then "<<" else "<" |
|||
default: op |
|||
} |
|||
op := proc(op, 2) | runerr(123, image(op)) |
|||
while /sorted := "yes" do # the sort |
|||
every i := 2 to *X do |
|||
if op(X[i],X[i-1]) then { |
|||
X[i-1] :=: X[i] |
|||
sorted := &null |
|||
} |
|||
return X |
|||
end</lang> |
|||
This code demonstrates the bubble sort using arguments supplied as arguments. The last sort |
|||
l1 := copy(l2) # list of strings |
|||
call on a string rather than a list illustrates how many Icon operators work on different types. |
|||
l2[1] := numeric(l2[1]) # force list with leading numeric |
|||
The example could be made more general to deal with coercion of types like cset to string |
|||
(admittedly an uninteresting example as csets are already sorted). |
|||
<lang icon>procedure main(l1) #: demo bubblesort |
|||
writes("Sorting : ") |
|||
writex(l1) |
|||
displaysort(copy(l1)) # default string sort |
|||
displaysort(copy(l1),"numeric") # explicit numeric sort |
|||
displaysort(copy(l1),"string") # explicit string sort |
|||
displaysort(copy(l1),"<<") # descending string sort |
|||
displaysort(copy(l1),"<") # descending numeric sort |
|||
displaysort(copy(l1),cmp) # ascending custom comparison |
|||
displaysort(copy(l1),"cmp") # ascending custom comparison |
|||
writes("Sorting string: ") |
|||
writex("qwerty") |
|||
displaysort(copy(l2)) # default numeric sort |
|||
displaysort( |
displaysort("qwerty") # sort characters in a string |
||
end |
|||
displaysort(copy(l1),"numeric") # explicit numeric sort |
|||
displaysort(copy(l2),"<<") # descending string sort |
|||
displaysort(copy(l2),"<") # descending numeric sort |
|||
procedure cmp(a,b) |
|||
displaysort("qwerty") # sort characters in a string |
|||
return a > b # Imagine a complex comparsion test here! |
|||
end |
end |
||
procedure displaysort(X,op) #: show bubblesort behavior |
procedure displaysort(X,op) #: show bubblesort behavior |
||
writes("--- bubblesort with op = ",left(image(op)||":",15)) |
|||
writex(bubblesort(X,op)) |
|||
write("op = ",image(op)) |
|||
writex("before = ",X) |
|||
writex("after = ",bubblesort(X,op)) |
|||
write() |
|||
return |
|||
end |
end |
||
procedure writex( |
procedure writex(X) #: helper for displaysort |
||
if type(X) == "string" then write(image(X)) |
|||
writes(\tag) |
|||
else { |
|||
if type(X) == "string" then write(image(X)) |
|||
writes("[") |
|||
else { |
|||
writes(" |
every writes(" ",image(!X)) |
||
write(" ]") |
|||
} |
|||
} |
|||
return |
|||
end</lang> |
end</lang> |
||
Sample output: |
Sample output: |
||
<pre>- |
<pre>->bubblesort 3 1 4 1 5 9 2 6 3 |
||
Sorting : [ "3" "1" "4" "1" "5" "9" "2" "6" "3" ] |
|||
op = "<<" |
|||
--- bubblesort with op = &null: [ "1" "1" "2" "3" "3" "4" "5" "6" "9" ] |
|||
--- bubblesort with op = "numeric": [ "1" "1" "2" "3" "3" "4" "5" "6" "9" ] |
|||
--- bubblesort with op = "string": [ "1" "1" "2" "3" "3" "4" "5" "6" "9" ] |
|||
--- bubblesort with op = "<<": [ "1" "1" "2" "3" "3" "4" "5" "6" "9" ] |
|||
--- bubblesort with op = "<": [ "1" "1" "2" "3" "3" "4" "5" "6" "9" ] |
|||
--- bubblesort with op = procedure cmp: [ "9" "6" "5" "4" "3" "3" "2" "1" "1" ] |
|||
--- bubblesort with op = "cmp": [ "9" "6" "5" "4" "3" "3" "2" "1" "1" ] |
|||
Sorting string: "qwerty" |
|||
--- bubblesort with op = &null: "eqrtwy" |
|||
-></pre> |
|||
==={{header|Unicon}}=== |
|||
--- bubblesort --- |
|||
op = "<" |
|||
before = [ 3 "4" "5" "6" "22" "1" "7" "9" ] |
|||
after = [ "1" 3 "4" "5" "6" "7" "9" "22" ] |
|||
The Icon solution also works in Unicon. |
|||
--- bubblesort --- |
|||
op = &null |
|||
before = "qwerty" |
|||
after = "eqrtwy" |
|||
</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
||