Tri par gobelet / beaker sort

Soyez le premier à donner votre avis sur cette source.

Vue 2 225 fois - Téléchargée 100 fois

Description

The idea behind this algorithm is to swap two random positions until the array is sorted. We have absolutely no warranty that the algorithm terminates. However, when the array is not too large and if we are quite lucky, it takes no more than a few seconds. Furthermore, as we are sure that the world as we know it will ends one day, we could expect that the algorithm stops as well.

L'idée derrière cet algorithme est d'inverser deux éléments au hasard jusqu'à ce que le tableau soit trié. Il n'existe absolument aucune garantie que l'algorithme se termine. Cependant, quand le tableau n'est pas trop grand et si nous sommes assez chanceux, cela ne prend pas plus de quelques secondes. De plus, puisque nous savons que le monde tel que nous le connaissons a une fin, on peut s'attendre à ce que l'algorithme se termine, au plus tard, en même temps que lui.

Source / Exemple :


package pataprogramming;

import java.util.Random;

public class BeakerSort {

    public static int[] sort(int[] tab) {
        // Initiate pos1 and pos2 with arbitrary values to avoid the error "variable might now have been initialized"
        int pos1 = -1;
        int pos2 = -1;
        boolean c;

        // While the array is still unsorted
        while (!isSorted(tab)) {
            // Choose randomly two different positions in the tab
            c = true;
            while (c) {
                pos1 = new Random().nextInt(tab.length);
                pos2 = new Random().nextInt(tab.length);
                c = (pos1 == pos2);
            }
            // Swap tab[pos1] and tab[pos2]
            tab[pos1] += tab[pos2];
            tab[pos2] = tab[pos1] - tab[pos2];
            tab[pos1] -= tab[pos2];
        }
        return tab;
    }

    public static boolean isSorted(int[] tab) {
        int previousValue = -1;
        for (int i = 0; i < tab.length; i++) {
            if (!(tab[i] >= previousValue))
                return false;
            previousValue = tab[i];
        }
        return true;
    }

    public static void main(String[] args) {
        // Initiate the array with random positive values
        final int l = 10;
        int[] tab = new int[l];
        for (int i = 0; i < l; i++)
            tab[i] = Math.abs(new Random().nextInt(20));

        int[] sortedTab = sort(tab);
        for (int i = 0; i < l; i++)
            System.out.println("t[" + i + "] = " + sortedTab[i]);
    }
}

Conclusion :


et voilà !

Codes Sources

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.