Implementierung eines grundlegenden Such- / Sortieralgorithmus in Java

Ich bin seit April ein neuer Diplomingenieur. Dies ist Qiitas erster Beitrag.

Einführung

Wie der Titel schon sagt, die grundlegenden Such- / Sortieralgorithmen Ich habe es in Java geschrieben. Ich habe es zuvor auf Blog veröffentlicht, aber ich habe es in 4 Teilen gepostet. Ich werde es in Qiita zusammenstellen. Der diesmal implementierte Such- / Sortieralgorithmus ist wie folgt.

Suchalgorithmus

• Lineare Suche
• Binäre Suche

Sortieralgorithmus

• Blasensortierung
• Auswahl sortieren
• Sortieren durch Einfügen
• Shell Sort
• Schnelle Sorte
• Zusammenführen, sortieren
• Heap Sort
• Bucket Sort
• Sortierung zählen

Lineare Suche

Durchschnittliche Berechnungsmenge: $ O (n) $

1. Extrahieren Sie Elemente aus dem Anfang der Liste
2. Vergleichen Sie den Wert des extrahierten Elements mit dem Wert des Elements, das Sie suchen möchten ・ Wenn sie übereinstimmen, ist die Suche abgeschlossen. ・ Wenn sie nicht übereinstimmen, gehen Sie zurück zu 1. und extrahieren Sie das nächste Element.

public class linearSearch {
    public static int execute(int[] data, int target){
        int notFound = -1;
        for(int i = 0; i < data.length; i++){
            if(data[i] == target){
                return i;
            }
        }
        return notFound;
    }
    public static void main(String[] args){
        int[] data = {1, 2, 3, 4, 5};
        int result;
        result = linearSearch.execute(data, 3);
        if(result != -1) {
            System.out.println("Found: index key = " + result);
        }
        else{
            System.out.println("Not found.");
        }

    }

}

Binäre Suche

Durchschnittliche Berechnungsmenge: $ O (\ log_2 {n}) $

1. Sortieren Sie das Array (vorausgesetzt, es ist in aufsteigender Reihenfolge sortiert).
2. Untersuchen Sie das Element in der Mitte des Arrays
3. Das zentrale Element ist nicht der gewünschte Wert und die gewünschten Daten sind größer als der zentrale Wert Wenn ja, überprüfen Sie das Teil nach der Mitte. Das zentrale Element ist nicht der gewünschte Wert und die gewünschten Daten sind kleiner als der zentrale Wert Wenn ja, überprüfen Sie die erste Hälfte von der Mitte
4. Kehren Sie zu 2 zurück.

public class binarySearch {
    public static boolean execute(int[] data, int target) {
        int low = 0;
        int high = data.length - 1;
        while (low <= high) {
            int middle = (low + high) >>> 1;
            if (data[middle] == target) {
                return true;
            } else if (data[middle] < target) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] data = {23, 25, 53, 444, 5466, 12646};
        boolean result;
        result = binarySearch.execute(data, 25);
        if (result){
            System.out.println("Found!");
        }
        else {
            System.out.println("Not Found.");
        }
    }

}

Blasensortierung

Durchschnittliche Berechnungsmenge: $ O (n ^ 2) $

1. Vergleichen Sie die Werte des ersten Elements 'A' und des benachbarten nächsten Elements 'B'.
2. Wenn das Element 'A' größer als das Element 'B' ist, tauschen Sie die Werte von Element 'A' und Element 'B' aus.
3. Bewegen Sie das erste Element nach 'B' und vergleichen / tauschen Sie die Werte von Element 'B' und benachbartem Element 'C' aus.
4. Wiederholen Sie den Vergleich / Austausch bis zum Ende der Liste und verschieben Sie das erste Element nach 'C', 'D', 'E' ...
5. Das Element mit dem höchsten Wert erscheint am Ende der Liste
6. Da das Ende der Liste den größten Wert enthält, verschieben Sie die Position des Listenendes (reduzieren Sie die Anzahl der Elemente um eins) und wiederholen Sie die Schritte 1 bis 6.

public class bubbleSort {
    public static void sort(int[] array){
        int temp;
        for(int i = 0; i < array.length; i++){
            for(int j = 0; j< array.length -i -1; j ++){
                if(array[j] > array[j + 1]){
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }

    }
    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        bubbleSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Auswahl Sortieren

Durchschnittliche Berechnungsmenge: $ O (n ^ 2) $

1. Setzen Sie das erste Element des Arrays als Element "A0" mit einem temporären Mindestwert.
2. Vergleichen Sie die Werte anderer Elemente als "A0" und "A0". Wenn das Element "A1" mit einem Wert kleiner als "A0" gefunden wird, tauschen Sie die Werte von "A0" und "A0" aus.
3. Durch Wiederholen von 2. wird "A0" auf den Mindestwert im Array gesetzt.
4. Vergleichen / tauschen Sie als Nächstes die anderen Elemente als "A1" und "A1" mit Ausnahme von "A0" und die anderen Elemente als "A2" und "A2" mit Ausnahme von "A1" aus, um die Ausrichtung abzuschließen.

public class selectionSort {
    public static void sort(int[] array){
        for(int i = 0; i < array.length; i++ ){
            int index = i;
            for(int j = i + 1; j < array.length; j++){
                if(array[j] < array[index]){
                    index = j;
                }
            }
            if(i != index){
                int tmp = array[index];
                array[index] = array[i];
                array[i] = tmp;

            }
        }
    }
    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        selectionSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Sortieren durch Einfügen

Durchschnittliche Berechnungsmenge: $ O (n ^ 2) $

1. Bestimmen Sie den ausgerichteten Index 'A'
2. Machen Sie das nächste Element 'B' nach 'A'the nicht ausgerichteten Teil
3. Fügen Sie 'B'in'A' ein.
4. Vergleichen Sie die Werte von A'und'B '. Wenn der Wert von' B'kleiner ist, ersetzen Sie ihn durch 'A'.
5. 'A' und 'B' werden zum ausgerichteten Teil
6. Sei 'C', das nächste Element von 'B', der nicht ausgerichtete Teil
7. Fügen Sie 'C' in die ausgerichteten Teile 'A', 'B' ein.
8. Vergleichen Sie die Werte von "C" und "B" und tauschen Sie sie gegen "B" aus, wenn der Wert von "C" kleiner ist.
9. Vergleichen Sie außerdem die Werte von 'C' und 'A'. Wenn der Wert von 'C' kleiner ist, tauschen Sie ihn gegen 'A' aus.

public class insertionSort {

    public static void sort(int[] array){
        for(int i = 1; i < array.length; i++){
            int j = i;
            while(j >= 1 && array[j-1] > array[j]){
                int tmp = array[j];
                array[j] = array[j - 1];
                array[j-1] = tmp;
                j --;

            }
        }

    }

    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        insertionSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Shell Sort

Durchschnittliche Berechnungsmenge: $ O (n ^ 1,25) $

Einfügesortierung vergleicht und tauscht benachbarte Elemente aus, und Shell-Sortierung vergleicht / tauscht Elemente aus, die durch h getrennt sind. Das Ausrichten von h auseinander liegenden Elementen wird als h-Sortieren bezeichnet. Einfügesortierung wird für die Ausrichtungslogik der h-Sortierung verwendet. Bei der Shell-Sortierung ist das Endergebnis durch Reduzieren der Anzahl von h in der h-Sortierung eine einfache Insert-Sortierung (h = 1). Wenn es zu einer Einfügesortierung wird, befindet es sich in einem Zustand, in dem es "fast ausgerichtet" ist, so dass es möglich ist, eine Ausrichtung durchzuführen, die die Einfügungssortierung nutzt.

public class shellSort {
    public static void sort(int[] array){
        int h = array.length / 2;

        while(h > 0){
            for(int i=h; i < array.length; i++){
                int j = i;
                while(j >= h && array[j - h] > array[j]){
                    int tmp = array[j];
                    array[j] = array[j-h];
                    array[j-h] = tmp;
                    j --;
                }
            }
            h /= 2;
        }

    }


    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        shellSort.sort(test);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Schnelle Sorte

Durchschnittliche Berechnungsmenge: $ O (n \ log {n}) $

1. Wenn die Anzahl der Elemente 1 oder weniger beträgt, wird dies als ausgerichtet betrachtet und die Sortierverarbeitung wird nicht durchgeführt.
2. Nehmen Sie das Element auf, das der Drehpunkt sein soll
3. Teilen Sie in zwei Teile, die auf dem Drehpunkt zentriert sind - ein Element mit einem Wert, der größer oder kleiner als der Wert des Drehpunkts ist
4. Wenden Sie diesen Algorithmus rekursiv auf die unterteilten Teile (Unterlisten) an.

public class quickSort {

    public static void sort(int[] array, int left, int right){
        if(left <= right){
            int p = array[(left + right) >>> 1];
            int l = left;
            int r = right;
            while(l <= r){
                while (array[l] < p){
                    l ++;
                }
                while (array[r] > p){
                    r --;
                }
                if (l <= r){
                    int tmp = array[l];
                    array[l] = array[r];
                    array[r] = tmp;
                    l++ ;
                    r-- ;
                }
            }
            quickSort.sort(array, left, r);
            quickSort.sort(array, l, right);
        }
    }

    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        quickSort.sort(test, 0, test.length-1);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Zusammenführen, sortieren

Durchschnittliche Berechnungsmenge: $ O (n \ log {n}) $

1. Teilen Sie die ungeordnete Liste in zwei Unterlisten auf
2. Richten Sie die Unterliste aus
3. Führen Sie Unterlisten zu einer sortierten Liste zusammen

public class mergeSort {

    public static void sort(int[] array, int low, int high){
        if(low < high){
            int middle = (low + high) >>> 1;
            mergeSort.sort(array, low , middle);
            mergeSort.sort(array, middle+1, high);
            mergeSort.merge(array, low, middle, high);
        }

    }
    public static void merge(int[] array, int low, int middle, int high){
        int[] helper = new int[array.length];

        for (int i = low; i <= high; i++){
            helper[i] = array[i];
        }
        int helperLeft = low;
        int helperRight = middle + 1;
        int current = low;

        while (helperLeft <= middle && helperRight <= high){
            if (helper[helperLeft] <= helper[helperRight]){
                array[current] = helper[helperLeft];
                helperLeft ++;
            }
            else {
                array[current] = helper[helperRight];
                helperRight ++;

            }
            current ++;
        }
        int remaining = middle - helperLeft;
        for (int i = 0; i <= remaining; i++){
            array[current + i] = helper[helperLeft + i];
        }



    }

    public static void main(String[] args){
        int[] test
                = { 10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62,  2, 12, 82,
        };
        mergeSort.sort(test, 0, test.length-1);
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }

    }
}

Heap Sort

Durchschnittliche Berechnungsmenge: $ O (n \ log {n}) $

1. Erstellen Sie einen Bottom-Up-Heap in dem auszurichtenden Array
2. Tauschen Sie das erste Element [1] und das letzte Element [N] des erstellten Heaps aus
3. Rekonstruieren Sie den Heap von Element [1] zu Element [N-1].
4. Tauschen Sie das erste Element [1] und das letzte Element [N-1] des Heaps aus
5. Kehren Sie zu 3 zurück. (Das letzte Element in 4. wechselt zu [N-2], [N-3] ...)
6. Die Ausrichtung ist abgeschlossen, wenn die Heap-Struktur nicht mehr vorhanden ist

public class heapSort {

    public static void sort(int[] array) {
        int n = array.length;

        for (int i = n /2 -1; i>=0; i--){
            heap(array, n, i);
        }
        
        for (int i = n-1 ; i>=0; i --){
            if (array[0] > array[i]) {
                int tmp = array[0];
                array[0] = array[i];
                array[i] = tmp;

                heap(array, i-1, 0);
            }

        }
    }
    
    public static void heap(int[] array, int n , int root){
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;

        if (left < n && array[left] > array[largest]){
            largest = left;
        }

        if (right < n && array[right] > array[largest]){
            largest = right;
        }

        if (largest != root){
            int swap = array[root];
            array[root] = array[largest];
            array[largest] = swap;

            heap(array, n ,largest);
        }
    }


    public static void main(String[] args) {
        int[] test
                = {10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62, 2, 12, 82,
        };
        heapSort.sort(test);
        for (int i = 0; i < test.length; i++) {
            System.out.println((i + 1) + ":" + test[i]);
        }
    }
}

Eimersortierung

Durchschnittliche Berechnungsmenge: $ O (n + k) $

Voraussetzung ist, dass die zu sortierenden Daten eine Ganzzahl von 1 bis 10 sind.

1. Bereiten Sie 10 Eimer vor, die 1 bis 10 nebeneinander entsprechen.
2. Legen Sie die Daten in den entsprechenden Eimer
3. Extrahieren Sie die Daten der Reihe nach aus dem Bucket

public class bucketSort {

    public static void sort(int[] array, int maxValue){
        int[] bucket = new int[maxValue + 1];

        for (int i = 0; i < bucket.length; i++){
            bucket[i] = 0;
        }

        for (int i = 0; i < array.length; i++){
            bucket[array[i]] ++;
        }

        int outPos = 0;
        for (int i = 0; i < bucket.length; i++){
            for (int j = 0; j < bucket[i]; j++){
                array[outPos++] = i;
            }
        }
    }


    public static void main(String[] args) {
        int[] test
                = {10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62, 2, 12, 82,
        };
        bucketSort.sort(test, 100);
        for (int i = 0; i < test.length; i++) {
            System.out.println((i + 1) + ":" + test[i]);
        }
    }
}

Sortierung zählen

Durchschnittliche Berechnungsmenge: $ O (nk) $

Voraussetzung ist, dass die zu sortierenden Daten eine Ganzzahl von 0 bis 5 sind. Das zu sortierende Array A sei {5,3,3,1,4}.

1. Bereiten Sie Array C zum Zählen der Schlüssel vor (Daten in Array A) und 2. Bereiten Sie das Arbeitsarray B zum Sortieren vor.
2. Zählen Sie die Häufigkeit des Auftretens von Daten in Sequenz A (unter Verwendung von Sequenz C).
3. Ermitteln Sie die kumulative Häufigkeitsverteilung der Schlüssel (gehalten von Array C).
4. Kopieren Sie die Daten von Array A nach Array B gemäß der kumulativen Häufigkeitsverteilung (von Array C) (kopieren Sie gegebenenfalls Daten von Array B auf das ursprüngliche Array A).

public class countingSort {

    public static int[] sort(int[] array, int maxValue){
        int[] counts = new int[maxValue + 1];

        for (int i = 0; i < array.length; i ++){
            counts[array[i]] ++;
        }

        int total = 0;
        for (int i =0 ;i <= maxValue; i++){
            int count = counts[i];
            counts[i] = total;
            total += count;
        }

        int[] sortedValues = new int[array.length];
        for (int i = 0; i < array.length; i++){
            sortedValues[counts[array[i]]] = array[i];
            counts[array[i]] ++ ;
        }
        return sortedValues;


    }

    public static void main(String[] args) {
        int[] test
                = {10, 75, 24, 32, 98,
                72, 88, 43, 60, 35,
                54, 62, 2, 12, 82, 2, 12, 12
        };
        test = countingSort.sort(test, 100);
        for (int i = 0; i < test.length; i++) {
            System.out.println((i + 1) + ":" + test[i]);
        }
    }

}

Github

Code für die Java-Implementierung dieses Such- und Sortieralgorithmus Ich habe es auf Github zusammengefasst. Wenn Sie Bedenken haben, machen Sie diese bitte bekannt (ich lerne, weil ich wahrscheinlich Java im Training verwende).

https://github.com/takaaki82/algorithm-training-java

abschließend

Wir planen, im Oktober die Prüfung zum Ingenieur für angewandte Informationstechnologie abzulegen. Denn dieser Bereich ist auch der Fragenbereich Wenn Sie Vorschläge oder andere Dinge haben, sollten Sie tun Bitte kommentieren!