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

• Recherche linéaire
• Recherche binaire

Algorithme de tri

• Tri à bulles
• Tri par sélection
• Tri par insertion
• Tri de coquille
• Tri rapide
• Tri par fusion
• Tri de tas
• Tri de seau
• Tri de comptage

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!