Buch Cover Buch Cover Buch Cover Buch Cover

Web-Code: - Webcode Help

Planetensortieren [Java] (Algorithmen)

Von einer Idee von Michael Weiß stammt die folgende Aufgabe.

Laden Sie die Datei „planetensortieren.zip“ herunter und
packe die Datei aus (unzip).
Ziel ist es, im Programmcode Sortierer
(src/ch/programmieraufgaben/planetensortieren/controller/Sortierer.java) eigene
Sortieralgorithmen einzubauen.
Öffnen Sie die Datei aufgabentext/Dokumentation.pdf und halten Sie sich an das dort beschriebene
"Vorgehen".
Zunächst soll der BubbleSort (ein Standard-Sortierverfahren) eingebaut werden. Danach kann der Algorithmus verbessert
werden (Merge-Sort, Heap-Sort, Insertion-Sort, …).

Dateien:

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

7 Lösung(en)

  @Sort
public void bubbleSort() {
        while(! istSortiert()) {
            int actPos = getFirstSortPos();
            while(actPos <= getLastSortPos() - 1) {                
                if(! istKleiner(actPos, actPos + 1)) {
                    tausche(actPos, actPos + 1);
                }
                actPos = actPos + 1;
            }
        }
     }
                
@Sort
public void quickSort() {
  quickSortRekursiv(getFirstSortPos(), getLastSortPos()); }

private void quickSortRekursiv(int firstSortPos, int lastSortPos) {
  // Rekursionsabbruch:
  if(firstSortPos >= lastSortPos) { return; }
  //Rekursion vorbereiten (Daten segmentieren)
  int pivot = quicksort_partitionierung(firstSortPos, lastSortPos);
  //sort rekursiv
  quickSortRekursiv(firstSortPos, pivot - 1);
  quickSortRekursiv(pivot + 1, lastSortPos) ;  }

// Partitiorierung im Quicksort.
// Der Array sieht wie folgt aus:
//  k    k    k    <pivot>      g            g    g   k     u
// [0] ..          [pivot]   [pivot + 1]    ...      [i]
// k = kleiner als [pivot]
// g = größer als [pivot]
// u = noch unbekannt.
private int quicksort_partitionierung(int firstSortPos, int lastSortPos) {
  int pivot = firstSortPos;
  int i = pivot + 1;
  while(i <= lastSortPos){
    if(! istKleiner(pivot, i)) {   
      tausche(i, pivot);
      if(i > pivot + 1) {
        tausche(pivot + 1, i); }
      pivot = pivot + 1;  }
    i =i + 1; }
  return pivot;  }
                
  /**
     * Gressly (2009)
     * Teste, ob sortiert.
     * Falls nicht: Wähle zwei beliebige Positionen und untersuche, ob
     * diese zwei Positionen auf Elemente zeigen, die nicht in Serie sind.
     * Tausche also nur, wenn nötig. ... und beginne dann von vorn.
     */
     @Sort
     public void randomPositionSort() {
        while(! istSortiert()) {
           rpSortTausche();   
        }
     }
    
     private void rpSortTausche() {
       int pos1 = (int) (Math.random() * (getLastSortPos() - getFirstSortPos() + 1)) + getFirstSortPos();  
       int pos2 = (int) (Math.random() * (getLastSortPos() - getFirstSortPos() + 1)) + getFirstSortPos();
       if(pos1 > pos2) {
           int tmp = pos1;
           pos1 = pos2;
           pos2 = tmp;   }
       if(! istKleiner(pos1, pos2)) {
         this.tausche(pos1, pos2); }
     }
                
/**
 * @author Daniel Huber {danney}
 */
@Sort
public void selectionSort() {
  int smaller = 1;
  for(int i = getFirstSortPos(); i < getLastSortPos(); i++) {
    smaller = i;
    if(smaller < getLastSortPos()) {
      while((smaller = getSmaller(i, smaller)) > 0) {
        tausche(i, smaller); 
       }   
    }
  }
} // end Method: SelectionSort

/**
 * @author Daniel Huber {danney}
 * @return next planet which is smaller than the current
 */
private int getSmaller(int current, int lastFound) {
  int ii = lastFound;
  while(++ii <= getLastSortPos()) {
    if(!istKleiner(current, ii)) { 
      return ii; 
    }
  }
  return 0;
} // end Method: getSmaller
                
@Sort
public void quickSort() {
    while (!istSortiert()) {
    	quick(getFirstSortPos(), getLastSortPos());
    }
}
     
public void quick(int links, int rechts) {
    int i = links;
    int j = rechts;
    int mitte = (int) (links + (rechts-links)/2);
    	 
    if (links == rechts) return;
    	 
    while (i < j) {
    	while (istKleiner(i, mitte)) {
    		i++;
    	}
    	while (istKleiner(mitte, j)) {
    		j--;
    	}
    		 
    	if (i < j) {
    		tausche(i, j);
    		i++;
    		j--;
    	}
    }
    	 
    if (links < j) {
    	quick(links, j-1);
    }
    if (i < rechts) {
    	quick(i+1, rechts);
    }
}
                

Lösung von: Mike Wong ()

@Sort
public void bubbleSortRekursiv() {
    int[] positions = {0, 1, 2, 3, 4, 5, 6, 7};
    while (!istSortiert()) {
    	bubble(positions);
    }
}
     
public void bubble(int[] positions) {
    for (int i=0;i<positions.length-1;i++) {
    	if (!istKleiner(i, i + 1)) {
    		tausche(i, i + 1);
    	}
    }
    int[] newPositions = Arrays.copyOf(positions, positions.length/2);
    if (newPositions.length > 1) {
    	bubble(newPositions);
    }
}
                

Lösung von: Mike Wong ()

    @Sort
    public void mergeSort() {
       mergeSort(getFirstSortPos(), getLastSortPos()); 
    }
    
    void mergeSort(int start, int end) {
        if(start >= end) { 
            return;
        }
        int mitte = (start + end) / 2;
        mergeSort(start    , mitte);
        mergeSort(mitte + 1, end  );
        
        merge(start, mitte + 1, end);
    }
    
    void merge(int list1, int list2, int end) {
        while(list1 < list2 && list2 <= end) {
            if(! istKleiner(list1, list2)) {
                rotate(list1, list2++);
            }
            list1++;
        }
    }
    
    void rotate(int links, int rechts) {
      for(int akt = rechts - 1; akt >= links; akt--) {
          tausche(akt, akt + 1);
      }
    }
                

Lösung von: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Aktionen

Bewertung

Durchschnittliche Bewertung:

Eigene Bewertung:
Bitte zuerst anmelden

Meta

Zeit: 2
Schwierigkeit: k.A.
Webcode: 6gqw-5zue
Autor: Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Download PDF

Download ZIP

Zu Aufgabenblatt hinzufügen