~2025-40783-41: /* Ada */

2025-12-15T08:34:18Z

Ada

Neue Seite

'''Swap-Sort''' ist ein [[Sortieralgorithmus]], der ein [[Feld (Datentyp)|Array]] aus paarweise verschiedenen Zahlen sortiert.

== Idee ==

Die Idee von Swap-Sort ist, von jedem Element eines Arrays ''A(1…n)'' die Anzahl ''m'' der kleineren Werte (die in ''A'' sind) zu zählen und das Element dann mit dem Element in ''A(m+1)'' zu vertauschen. Somit ist sichergestellt, dass das ausgetauschte Element bereits an der richtigen, also endgültigen Stelle steht.

Nachteil dieses [[Algorithmus]] ist, dass jedes Element nur einmal vorkommen darf, da sonst keine [[Terminiertheit|Terminierung]] erfolgt.

== Prinzip ==

''A'' ist ein Array mit ''n'' Elementen. Swap-Sort arbeitet in folgenden Schritten:
# Beginne mit <code>i = 1</code>
# Zähle, wie viele Elemente kleiner als ''A(i)'' sind, m sei diese Anzahl. Tausche danach ''A(i)'' mit ''A(m+1)''
# Ist <code>i = m+1</code>, so erhöhe ''i'' um 1
# Ist <code>i = n</code>, so ist die Sortierung beendet. Andernfalls gehe wieder zu Schritt 2.

== Beispiel ==

Es soll ein Array mit dem Inhalt {7,8,5,2,4,9,3,1} sortiert werden.

7 8 5 2 4 9 3 1 Mit dem Index 1 wird begonnen
^
9 8 5 2 4 7 3 1 7 wurde mit A(5+1) getauscht
^
1 8 5 2 4 7 3 9 9 wurde mit A(7+1) getauscht
^
1 8 5 2 4 7 3 9 der Index wurde erhöht, da die Anzahl m der
^ kleineren Elemente von A(1) gleich dem Index-1 war
1 3 5 2 4 7 8 9 8 wurde mit A(6+1) getauscht
^
1 5 3 2 4 7 8 9
^
1 4 3 2 5 7 8 9
^
1 2 3 4 5 7 8 9
^
1 2 3 4 5 7 8 9 der Index wurde erhöht, da die Anzahl m der
^ kleineren Elemente von A(2) gleich dem Index-1 war
1 2 3 4 5 7 8 9 ...usw.
^
1 2 3 4 5 7 8 9
^
1 2 3 4 5 7 8 9
^
1 2 3 4 5 7 8 9
^
1 2 3 4 5 7 8 9 Das Array wurde komplett durchlaufen,
^ das Sortieren ist somit beendet

== Komplexität ==

Für die Bestimmung der Anzahl kleinerer Einträge ist ein vollständiger Array-Durchlauf nötig. Ein solcher muss für jedes Element des Arrays durchgeführt werden. Es ergibt sich eine Komplexität von <math>\mathcal O(n^2)</math>.

== Implementierung ==
=== Ada ===
<syntaxhighlight lang="ada">
procedure swapsort (a: in out vector) is

z:integer;

function ziel_pos(z:integer) return natural is
anz:natural:=0;
begin
for i in a'range loop
if a(i) <= z then
anz:=anz+1;
end if;
end loop;
return anz;
end;

begin
for index in a'range loop
z:=ziel_pos(a(index));
while z /= index loop
< vertausche a(index) mit a(z) >;
z:=ziel_pos(a(index));
end loop;
end loop;
end;
</syntaxhighlight>

=== Haskell ===
<syntaxhighlight lang="Haskell">
swapSort x = swapSort' x 0 where

swapSort' x i | i == length x = x
| i == smaller = swapSort' x (i+1)
| otherwise = swapSort' (swap x i smaller) i where
smaller = countSmaller x (x !! i)

countSmaller = countSmaller' 0
countSmaller n [] _ = n
countSmaller n (x:xs) y | x < y = countSmaller (n+1) xs y
| otherwise = countSmaller n xs y

swap x i1 i2 = insert (remove (insert (remove x i1) e1 (i2-1)) i2) e2 i1 where
e1 = x !! i1
e2 = x !! i2

remove (x:xs) 0 = xs
remove (x:xs) n = x : remove xs (n-1)
remove [] _ = error "Index zu groß"

insert x y 0 = y:x
insert (x:xs) y n = x:insert xs y (n-1)
insert [] _ _ = error "Index zu groß"
</syntaxhighlight>

=== Java ===
<syntaxhighlight lang="java">
public class SwapSorter {

public void sort(int[] sortMe) {

int startwert = 0;

while (startwert < sortMe.length - 1) {

int kleinere = countSmallerOnes(sortMe, startwert);

if (kleinere > 0) {
int tmp = sortMe[startwert];
sortMe[startwert] = sortMe[startwert + kleinere];
sortMe[startwert + kleinere] = tmp;
}
else
{
startwert++;
}
}
}

private int countSmallerOnes(final int[] countHere, final int index) {
int counter = 0;
for (int i = index + 1; i < countHere.length; i++) {
if (countHere[index] > countHere[i]) {
counter++;
}
}
return counter;
}

// Testmain
public static void main(String[] args) {

int[] a = {3, 7, 45, 1, 33, 5, 2, 9};
System.out.print("unsorted: ");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
new SwapSorter().sort(a);
System.out.print("sorted: ");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
</syntaxhighlight>

=== Python ===
<syntaxhighlight lang="python">
def swap_sort(sortme):
index = 0
while index < len(sortme) - 1:
new_index = sum(x < sortme[index] for x in sortme)
if index == new_index:
index += 1
else:
sortme[index], sortme[new_index] = sortme[new_index], sortme[index]
</syntaxhighlight>

== Siehe auch ==
* [[Liste von Algorithmen]]

[[Kategorie:Sortieralgorithmus]]

Swap-Sort - Versionsgeschichte

~2025-40783-41: /* Ada */