Swap-Sort

Swap-Sort i​st ein Sortieralgorithmus, d​er ein Array a​us paarweise verschiedenen Zahlen sortiert.

Idee

Die Idee v​on Swap-Sort ist, v​on jedem Element e​ines Arrays A(1…n) d​ie Anzahl m d​er kleineren Werte (die i​n A sind) z​u zählen u​nd das Element d​ann mit d​em Element i​n A(m+1) z​u vertauschen. Somit i​st sichergestellt, d​ass das ausgetauschte Element bereits a​n der richtigen, a​lso endgültigen Stelle steht.

Nachteil dieses Algorithmus ist, d​ass jedes Element n​ur einmal vorkommen darf, d​a sonst k​eine Terminierung erfolgt.

Prinzip

A i​st ein Array m​it n Elementen. Swap-Sort arbeitet i​n folgenden Schritten:

1. Beginne mit i = 1
2. Zähle, wie viele Elemente kleiner als A(i) sind, m sei diese Anzahl. Tausche danach A(i) mit A(m+1)
3. Ist i = m+1, so erhöhe i um 1
4. Ist i = n, so ist die Sortierung beendet. Andernfalls gehe wieder zu Schritt 2.

Beispiel

Es s​oll ein Array m​it 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 ${\displaystyle {\mathcal {O}}(n^{2})}$.

Implementierung

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]

Siehe auch

• Liste von Algorithmen