Sortierverfahren

				
					
/**
 * Beschreiben Sie hier die Klasse Zeitmessungen.
 * 
 * @author (Philip Dong) 
 * @version (06.12.2021)
 */
public class Zeitmessungen
{
    List<Integer> zahlenfolgeInsertionSort;
    List<Integer> zahlenfolgeSelectionSort;
    List<Integer> zahlenfolgeQuickSort;

    Zeitmessungen()
    {
        zahlenfolgeInsertionSort = new List<Integer>();
        zahlenfolgeSelectionSort = new List<Integer>();
        zahlenfolgeQuickSort = new List<Integer>();
    }

    public void datenErzeugen(int pAnzahl)
    {
        zahlenfolgeInsertionSort = new List<Integer>();
        zahlenfolgeSelectionSort = new List<Integer>();
        zahlenfolgeQuickSort = new List<Integer>();
        for(int i=0; i<pAnzahl; i++)
        {
            int temp= (int) (Math.random()*10*pAnzahl) +1;
            zahlenfolgeInsertionSort.append(temp);
            zahlenfolgeSelectionSort.append(temp);
            zahlenfolgeQuickSort.append(temp);
        }

    }

    public void datenAusgeben()
    {
        System.out.print(" Zahlenfolge InsertionSort: ");
        listeAusgeben(zahlenfolgeInsertionSort);
        System.out.println();
        System.out.print(" Zahlenfolge SelectionSort: ");
        listeAusgeben(zahlenfolgeSelectionSort);
        System.out.println();
        System.out.print(" Zahlenfolge QuickSort:     ");
        listeAusgeben(zahlenfolgeQuickSort);
        System.out.println();

    }

    public void listeAusgeben(List<Integer> zahlenfolge)
    {
        zahlenfolge.toFirst();
        while(zahlenfolge.hasAccess())
        {
            System.out.print(zahlenfolge.getContent() + " ");
            zahlenfolge.next();
        }

    }

    public void messungenStarten()
    {

        long timeStart;
        long timeEnd;

        // Dauer InsertionSort
        timeStart = System.currentTimeMillis();
        insertionSort();
        timeEnd = System.currentTimeMillis();
        System.out.println("Laufzeit InsertionSort: " + (timeEnd - timeStart) + " Millisek.");

        // Dauer SelectionSort
        timeStart = System.currentTimeMillis();
        selectionSort();
        timeEnd = System.currentTimeMillis();
        System.out.println("Laufzeit SelectionSort: " + (timeEnd - timeStart) + " Millisek.");

        // Dauer QuickSort
        timeStart = System.currentTimeMillis();
        quickSort();
        timeEnd = System.currentTimeMillis();
        System.out.println("Laufzeit QuickSort: " + (timeEnd - timeStart) + " Millisek.");

    }

    public void insertionSort()
    {
        List <Integer> sortierteZahlenfolgeInsertionSort = new List<Integer>();
        while(!zahlenfolgeInsertionSort.isEmpty())
        {
            zahlenfolgeInsertionSort.toFirst();
            int aktuelles = zahlenfolgeInsertionSort.getContent();
            sortierteZahlenfolgeInsertionSort.toFirst();
            while(sortierteZahlenfolgeInsertionSort.hasAccess() && sortierteZahlenfolgeInsertionSort.getContent() < aktuelles)
            {
                sortierteZahlenfolgeInsertionSort.next();
            }

            if(sortierteZahlenfolgeInsertionSort.hasAccess())
            {
                sortierteZahlenfolgeInsertionSort.insert(aktuelles);
            }
            else
            {
                sortierteZahlenfolgeInsertionSort.append(aktuelles);
            }
            zahlenfolgeInsertionSort.remove();
        }
        zahlenfolgeInsertionSort = sortierteZahlenfolgeInsertionSort;
    }

    public void selectionSort()
    {
        List <Integer> sortierteZahlenfolgeSelectionSort = new List<Integer>();
        while(!zahlenfolgeSelectionSort.isEmpty())
        {
            zahlenfolgeSelectionSort.toFirst();
            int minimum = zahlenfolgeSelectionSort.getContent();

            //Minimum finden
            while(zahlenfolgeSelectionSort.hasAccess())
            {
                if(zahlenfolgeSelectionSort.getContent() < minimum)
                {
                    minimum = zahlenfolgeSelectionSort.getContent();
                }
                zahlenfolgeSelectionSort.next();
            }

            // Minimum in sortierte Liste einfuegen
            sortierteZahlenfolgeSelectionSort.append(minimum);

            // Minimum aus unsortierter Liste loeschen
            zahlenfolgeSelectionSort.toFirst();
            while(zahlenfolgeSelectionSort.hasAccess())
            {
                if(zahlenfolgeSelectionSort.getContent() == minimum)
                {
                    zahlenfolgeSelectionSort.remove();
                    break;
                }
                zahlenfolgeSelectionSort.next();
            }
        }
        zahlenfolgeSelectionSort = sortierteZahlenfolgeSelectionSort;
    }

    public void quickSort()
    {
        quickSortRek(zahlenfolgeQuickSort);
    }

    public void quickSortRek(List<Integer> zahlenfolge)
    {
        //Hat die Liste höchstens ein Element?
        if(!zahlenfolge.isEmpty())
        {
            //Rekursionsanker, überprüft, ob die Liste einelementig ist, wenn ja, dann wurde alles sortiert.
            zahlenfolge.toFirst();
            zahlenfolge.next();
            if(zahlenfolge.hasAccess())
            {
                List<Integer> kleinere = new List<Integer>();
                List<Integer> groessere = new List<Integer>();
                zahlenfolge.toFirst();
                int pivot = zahlenfolge.getContent();
                zahlenfolge.remove();

                //Verschiebt die Datensätze in die List "kleinere" bzw. "groessere".
                while(!zahlenfolge.isEmpty())
                {
                    int akt = zahlenfolge.getContent();
                    if(akt < pivot)
                    {
                        kleinere.append(akt);
                    } else
                    {
                        groessere.append(akt);
                    }
                    zahlenfolge.remove();
                }

                //Macht das Selbe mit den Listen "kleinere" und "groessere" (Rekursionsschritt)
                quickSortRek(kleinere);
                quickSortRek(groessere);

                // Fügt die Listen zusammen, zuerst die kleinere Liste, dann pivot, dann die größere Liste
                zahlenfolge.concat(kleinere);
                zahlenfolge.append(pivot);
                zahlenfolge.concat(groessere);
            }
        }
    }
}