Implémentation d'un algorithme de recherche / tri de base en Java

Je suis un nouvel ingénieur diplômé d'avril. C'est le premier message de Qiita.

introduction

Comme le titre l'indique, les algorithmes de recherche / tri de base Je l'ai écrit en Java. Je l'ai publié sur Blog avant, mais je l'ai posté en 4 parties. Je vais le mettre en place dans Qiita. L'algorithme de recherche / tri mis en œuvre cette fois est le suivant.

Algorithme de recherche

Algorithme de tri

Recherche linéaire

Montant moyen du calcul: O $ (n) $

  1. Extraire les éléments du haut de la liste
  2. Comparez la valeur de l'élément extrait avec la valeur de l'élément que vous souhaitez rechercher ・ S'ils correspondent, la recherche est terminée. ・ S'ils ne correspondent pas, retournez à 1. et extrayez l'élément suivant.

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.");
        }

    }

}

Recherche binaire

Montant moyen du calcul: $ O (\ log_2 {n}) $

  1. Triez le tableau (en supposant qu'il soit trié par ordre croissant)
  2. Examinez l'élément au centre du tableau
  3. L'élément central n'est pas la valeur souhaitée et les données souhaitées sont supérieures à la valeur centrale Si tel est le cas, vérifiez la pièce après le centre. L'élément central n'est pas la valeur souhaitée et les données souhaitées sont plus petites que la valeur centrale Si c'est le cas, vérifiez la première moitié du centre
  4. Revenez à 2.
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.");
        }
    }

}

Tri à bulles

Montant moyen du calcul: $ O (n ^ 2) $

  1. Comparez les valeurs du premier élément "A" et de l'élément suivant adjacent "B"
  2. Si l'élément "A" est supérieur à l'élément "B", échangez les valeurs de l'élément "A" et de l'élément "B".
  3. Déplacez le premier élément vers "B" et comparez / échangez les valeurs de l'élément "B" et de l'élément adjacent "C"
  4. Répétez la comparaison / échange jusqu'à la fin de la liste, en déplaçant le premier élément vers 'C', 'D', 'E' ...
  5. L'élément avec la valeur la plus élevée apparaît à la fin de la liste
  6. Puisque la fin de la liste contient la plus grande valeur, décalez la position de la fin de la liste (réduisez le nombre d'éléments de un) et répétez les étapes 1 à 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] );
        }

    }
}



Tri par sélection

Montant moyen du calcul: $ O (n ^ 2) $

  1. Définissez le premier élément du tableau comme l'élément "A0" avec une valeur minimale temporaire.
  2. Comparez les valeurs d'éléments autres que "A0" et "A0", et si l'élément "A1" avec une valeur inférieure à "A0" est trouvé, échangez les valeurs de "A0" et "A0".
  3. En répétant 2., "A0" est défini sur la valeur minimale du tableau.
  4. Ensuite, comparez / échangez les éléments autres que "A1" et "A1" sauf "A0", et les éléments autres que "A2" et "A2" sauf "A1" pour terminer l'alignement.
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] );
        }

    }
}

Tri par insertion

Montant moyen du calcul: $ O (n ^ 2) $

  1. Déterminez l'indice aligné "A"
  2. Laissez l'élément suivant "B" après "A" être la partie non alignée
  3. Insérez 'B'in'A'
  4. Comparez les valeurs de A "et" B "et si la valeur de" B "est plus petite, remplacez-la par" A " 5.'A 'et'B' deviennent la partie alignée
  5. Soit "C", l'élément à côté de "B" la partie non alignée
  6. Insérez "C" dans les parties alignées "A", "B"
  7. Comparez les valeurs de «C» et «B» adjacents et remplacez-les par «B» si la valeur de «C» est plus petite.
  8. De plus, comparez les valeurs de "C" et "A", et si la valeur de "C" est plus petite, remplacez-la par "A".
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] );
        }

    }
}


Tri de coquille

Montant moyen du calcul: O $ (n ^ 1,25) $

Le tri par insertion compare et échange les éléments adjacents, et le tri par shell compare / échange les éléments séparés par h. Le processus d'alignement de h éléments séparés est appelé tri-h. Le tri par insertion est utilisé pour la logique d'alignement du tri-h. En tri shell, en réduisant le nombre de h dans h-sort, le résultat final est un tri par insertion simple (h = 1). Au moment où il devient un tri d'insert, il est dans un état d'être "presque aligné", il est donc possible d'effectuer un alignement qui tire parti du tri d'insert.


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] );
        }

    }
}

Tri rapide

Montant moyen du calcul: $ O (n \ log {n}) $

  1. Si le nombre d'éléments est égal ou inférieur à 1, il est considéré comme aligné et le traitement de tri n'est pas effectué.
  2. Prenez l'élément qui sera le pivot
  3. Divisez en deux parties centrées sur le pivot - un élément avec une valeur supérieure ou inférieure à la valeur du pivot
  4. Appliquer cet algorithme de manière récursive aux parties divisées (sous-listes)
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] );
        }

    }
}

Tri par fusion

Montant moyen du calcul: $ O (n \ log {n}) $

  1. Divisez la liste non ordonnée en deux sous-listes
  2. Alignez la sous-liste
  3. Fusionner les sous-listes en une seule liste triée
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] );
        }

    }
}


Tri de tas

Montant moyen du calcul: $ O (n \ log {n}) $

  1. Créez un tas de bas en haut dans le tableau à aligner
  2. Permutez le premier élément [1] et le dernier élément [N] du tas construit
  3. Reconstruisez le tas de l'élément [1] à l'élément [N-1]
  4. Permutez le premier élément [1] et le dernier élément [N-1] du tas
  5. Retournez à 3. (Le dernier élément de 4. passe à [N-2], [N-3] ...)
  6. L'alignement est terminé lorsque la structure du tas a disparu
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]);
        }
    }
}

Tri de seau

Montant moyen du calcul: O $ (n + k) $

En principe, les données à trier sont un entier de 1 à 10.

  1. Préparez 10 seaux correspondant à 1 à 10 côte à côte.
  2. Placez les données dans le compartiment correspondant
  3. Extraire les données du bucket dans l'ordre
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]);
        }
    }
}


Tri de comptage

Montant moyen du calcul: O $ (nk) $

En principe, les données à trier sont un entier de 0 à 5. Soit le tableau A à trier {5,3,3,1,4}.

  1. Préparez le tableau C pour compter les clés (données du tableau A) et 2. préparez le tableau de travail B pour le tri.
  2. Comptez la fréquence d'apparition des données dans la séquence A (en utilisant la séquence C)
  3. Trouvez la distribution de fréquence cumulative des touches (détenues par le tableau C)
  4. Copiez les données du tableau A vers le tableau B en fonction de la distribution de fréquence cumulée (du tableau C) (copiez les données du tableau B vers le tableau d'origine A si nécessaire)
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 pour l'implémentation Java de cet algorithme de recherche et de tri Je l'ai résumé sur Github. Si vous avez des inquiétudes, faites-en la publicité (j'étudie car je suis susceptible d'utiliser Java en formation).

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

en conclusion

Nous prévoyons de passer l'examen d'ingénieur en technologie de l'information appliquée en octobre. Parce que cette plage est également la plage de questions Si vous avez des suggestions ou d'autres choses à faire Commentez s'il vous plaît!

Recommended Posts

Implémentation d'un algorithme de recherche / tri de base en Java
[Neta] Sleep Sort en Java
Implémenter l'authentification de base en Java
[Java] Termes de base en programmation
Méthode de concurrence en Java avec exemple de base
tri de bulles java
Partition en Java
Grammaire de base Java
Grammaire Java de base
Changements dans Java 11
Échantillon de bibliothèque d'algorithmes Java
Connaissances de base Java 1
[Java] Structure de base
java sélectionner le tri
Implémentez l'algorithme dans Ruby: Day 4-Linear search-
Grammaire de base Java
java insert tri
Taux circonférentiel à Java
Exercice Java [basique]
[Angoisse du débutant Java] Code difficile à tester implémenté dans Junit
FizzBuzz en Java
Implémentez l'algorithme dans Ruby: Jour 2 -Bubble Sort-
Trier les valeurs de la carte par ordre croissant des clés dans Java TreeMap
J'ai essayé d'implémenter la méthode de division mutuelle d'Eugrid en Java
Lire JSON en Java
Implémentation de l'interpréteur par Java
Faites un blackjack avec Java
Application Janken en Java
Programmation par contraintes en Java
Mettez java8 dans centos7
NVL-ish guy en Java
Joindre des tableaux en Java
Interface appelable en Java
Commentaires dans la source Java
[Java] Type de données ①-Type de base
Fonctions Azure en Java
Formater XML en Java
Simple htmlspecialchars en Java
Manipulation de base de la date Java
Implémentation Boyer-Moore en Java
Hello World en Java
Utiliser OpenCV avec Java
Conventions de dénomination Java de base
Mémorandum WebApi avec Java
[Note] Java: recherche de chaînes de caractères
Exécuter des commandes en Java (ping)
Mémo d'apprentissage Java (basique)
Divers threads en java
Implémentation du tri de tas (en java)
API Zabbix en Java
Art ASCII à Java
Comparer des listes en Java
POST JSON en Java
Exprimer l'échec en Java
Créer JSON en Java
Manipulation de la date dans Java 8
Utiliser PreparedStatement en Java
Nouveautés de Java 9,10,11
Types de données de base Java