[RUBY] Insérer l'implémentation du tri

Préface

Un article qu'un débutant en programmation implémentera l'algorithme d'une extrémité. Cette fois, le tri par insertion est écrit en C, Java, Ruby, Python. S'il y a des améliorations dans le code, je vous serais reconnaissant si vous pouviez m'apprendre.

Insérer des fonctionnalités de tri

・ Efficace pour les tableaux avec un petit nombre d'éléments -Efficace pour les tableaux qui sont presque alignés ou qui ont de nombreux éléments qui se chevauchent (Parce que le nombre de remplacements d'éléments est réduit) ・ Le montant moyen du calcul [^ 1] est de $ O $ ($ n ^ 2 $) [^ 2] (Pour remplacer chacun des n éléments en moyenne par un multiple constant de n)

[^ 1]: Montant de calcul: Critères d'évaluation de l'algorithme Obtenu sur la base des instructions constitutives. [^ 2]: Notation d'ordre: Notation indiquant le montant du calcul. Ignorez les termes et coefficients autres que les termes de l'ordre le plus élevé.

Langage C

/*size est la taille du tableau*/
void insertionSort(int data[10], int size) {
	int i, j;
	for(i = 1; i < size; i++) {
		j = i;
		while(j > 0 && data[j - 1] > data[j]) {
			swap(&data[j - 1], &data[j]);
			j--; 
		}
	}
}

void swap(int *a, int *b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

Java

public static void insertionSort(int[] data) {	
	int i, j;
	for(i = 1; i < data.length; i++) {
        j = i;
        while(j > 0 && data[j - 1] > data[j]) {
            swap(data, j);
            j--; 
        }
    }
}

public static void swap(int[] data, int j) {
	int tmp;
	tmp = data[j];
	data[j] = data[j - 1];
	data[j - 1] = tmp;
}

Ruby

def insertionSort(data)
	(1...data.length).each do |i|
		j = i
		while j > 0 && data[j - 1] > data[j]
			data[j - 1], data[j] = data[j], data[j - 1]
			j -= 1
		end
	end
end

Python

def insertionSort(data):
	for i in range(1, len(data)):
		j = i
		while j > 0 and data[j - 1] > data[j]:
				data[j - 1], data[j] = data[j], data[j - 1]
				j -=1

Ce que j'ai remarqué

-Les variables de type de référence Java sont "String", "Array", "Class" ・ En Ruby et Python, les éléments peuvent être remplacés sur une seule ligne. ・ Ruby for statement est interprété comme chaque méthode (Lorsque la méthode each est modifiée, le comportement de l'instruction for change également) ・ "&&" et "et" sont différents dans Ruby etc. Référence: Différence entre && et et

Références / Sites

Recommended Posts

Insérer l'implémentation du tri
Insérer un tri
visualiser le tri par insertion
Trier
SélectionSort
Mise en œuvre de la fermeture
[Python] Trier
Tri naturel
Tri à bulles
Tri à bulles