Swap sort
Swap-Sort is a sorting algorithm that sorts an array of numbers that are different in pairs.
idea
The idea of swap sort is to count the number m of the smaller values (which are in A ) of each element of an array A (1 ... n) and then to swap the element with the element in A (m + 1) . This ensures that the replaced element is already in the correct, i.e. final position.
The disadvantage of this algorithm is that each element can only appear once, otherwise there is no termination .
principle
A is an array with n elements. Swap sort works in the following steps:
- Start with
i = 1 - Count how many elements are smaller than A (i) , let m be that number. Then swap A (i) for A (m + 1)
- Is
i = m+1, then increase i by 1 - If
i = nthe sorting is finished. Otherwise go back to step 2.
example
An array with the content {7,8,5,2,4,9,3,1} is to be sorted.
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 2 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
complexity
A complete array run is required to determine the number of smaller entries. This must be done for each element of the array. There is a complexity of .
implementation
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;
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ß"
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] + " ");
}
}
}
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]