Sortieren durch Auswahl

Struktogramm - Direkte Auswahl (Straight selection)

Im Gegensatz zu den Einfügeverfahren sucht man bei den Auswahlverfahren ein bestimmtes, z.B. das kleinste oder größte Element und ordnet es entsprechend ein.

Grobalgorithmus:

Suche kleinstes Element MIN der unsortierten Teilfolge und vertausche es mit dem ersten Element der unsortierten Folge, sofern es kleiner als dieses ist.

INDEX I	1	2	3	4	5	I	MIN	MININDEX	VI
ELEMENT E[I]	17	9	10	6	12	1	17	1	2
							9	2
									3
							6	4	4
	6	9	10	17	12				5
						2	9	2	3
									4
	6	9	10	17	12				5
						3	10	3	4
	6	9	10	17	12				5
						4	17	4	5
	6	9	10	12	17		12	5

Beachte: Bei der Suche nach dem kleinsten Element der unsortierten Teilfolge muss man sich den Index des aktuellen Minimums merken, da dieser für einen eventuellen Austausch erforderlich ist.

Programm-Code (in Java)

/*
 * Created on 11.01.2004
 */
import straight_selection.Straight_selection;
/**
 * @author Florian Ercevic
 */
public class mainEx {
  public static void main(String[] args) {
    Straight_selection SI = new Straight_selection();
    SI.fillArray();
    System.out.println("unsortiert für Straight Insertion");
    for(int i=1;i<6;i++)
    {
      System.out.print(SI.Array1[i]+" ");
    }
    SI.sortArray();
    System.out.println();
    System.out.println("sortiert nach Straight Insertion");
    for(int i=1;i<6;i++)
    {
      System.out.print(SI.Array1[i]+" ");
    }
    System.out.println();
  }
}

/*
 * Created on 11.01.2004
 */
package straight_selection;
/**
 * @author Florian Ercevic
 */
import java.util.Random;
public class Straight_selection
{
  Random generator = new Random();
  int N=5;
  public int [] Array1 = new int[N+1];
  public int [] fillArray()
  {
    for(int i=1;i<N+1;i++)
    {
      Array1[i] = 1 + generator.nextInt(100);
    }
    return Array1;
  }
  public int [] sortArray()
  {
    int MIN=0, MININD=0;
    for(int i=1;i<N+1;i++)
    {
      MIN=Array1[i];
      MININD=i;
      for(int VI=i+1;VI<N+1;VI++)
      {
        if(Array1[VI]<MIN)
        {
          MIN=Array1[VI];
          MININD=VI;
        }
        Array1[MININD]=Array1[i];
        Array1[i]=MIN;
      }
    }
    return Array1;
  }
}