Simplificando o radix sort

Programação
#1

Olá, bom dia!!!
Fiz esse código para implementar o radix sort, porém acredito que possa simplifica-lo, alguém teria alguma idéia? Grato!!

import java.util.Random;

public class ExercicioRadixSort {

public static void main(String[] args) {

	int vetor1[] = new int [1000];
	int matriz1[][] = new int [1000][10];
	int f0=0, f1=0, f2=0, f3=0, f4=0, f5=0, f6=0, f7=0, f8=0, f9=0;
			
Random gerador = new Random();
System.out.println("Vetor Gerado: ");
for(int i=0;i<1000;i++) 
{
	vetor1[i] = gerador.nextInt(1000);	
	System.out.print(" "+vetor1[i]);
}
// Analisando valores e preenchendo a matriz de acordo com o número da unidade
for (int i=0; i<1000;i++) 
{
	switch (vetor1[i] % 10) {			// Resto da divisão por 10
	case 0:
		matriz1[f0++][0] = vetor1[i];
		break;			
	case 1:
		matriz1[f1++][1] = vetor1[i];
		break;		
	case 2:
		matriz1[f2++][2] = vetor1[i];
		break;			
	case 3:
		matriz1[f3++][3] = vetor1[i];
		break;					
	case 4:
		matriz1[f4++][4] = vetor1[i];
	break;		
	case 5:
		matriz1[f5++][5] = vetor1[i];
		break;		
	case 6:
		matriz1[f6++][6] = vetor1[i];
		break;		
	case 7:
		matriz1[f7++][7] = vetor1[i];
		break;			
	case 8:
		matriz1[f8++][8] = vetor1[i];
		break;					
	case 9:
		matriz1[f9++][9] = vetor1[i];
	break;		
	}
}

// Reconstrução do vetor após 1ª interação
int k=0;
for(int j=0; j<10;j++) {
	for(int i=0; i<1000; i++) {
		if(matriz1[i][j]>0) {
			vetor1[k++]=matriz1[i][j];
		}
	}
}

System.out.println("\n");
System.out.println("\nVetor após primeira interação: ");
for(int i=0;i<1000;i++) {
	System.out.print(" "+vetor1[i]);
}

// Zerando a matriz


for(int j=0; j<10;j++) 
{
	for(int i=0; i<1000; i++) 
	{
		matriz1[i][j]=0;
	}		
}

// Zerando as filas

f0=0; f1=0; f2=0; f3=0; f4=0; f5=0; f6=0; f7=0; f8=0; f9=0;

// Segunda Interação (Dezenas)

	for (int i=0; i<100;i++) {
		switch ((vetor1[i] % 100/10)) {
		case 0:
			matriz1[f0++][0] = vetor1[i];
			break;
			
		case 1:
			matriz1[f1++][1] = vetor1[i];
			break;
		
		case 2:
			matriz1[f2++][2] = vetor1[i];
			break;
			
		case 3:
			matriz1[f3++][3] = vetor1[i];
			break;
					
		case 4:
			matriz1[f4++][4] = vetor1[i];
		break;
		
		case 5:
			matriz1[f5++][5] = vetor1[i];
			break;
		
		case 6:
			matriz1[f6++][6] = vetor1[i];
			break;
		
		case 7:
			matriz1[f7++][7] = vetor1[i];
			break;
			
		case 8:
			matriz1[f8++][8] = vetor1[i];
			break;
					
		case 9:
			matriz1[f9++][9] = vetor1[i];
		break;
		}		
	}
	
	
	// Reconstrução do vetor após 2ª interação
	int m=0;
	for(int j=0; j<10;j++) 
	{
		for(int i=0; i<1000; i++) 
		{
			if(matriz1[i][j]>0) 
			{
				vetor1[m++]=matriz1[i][j];
			}
		}			
	}
	
	// Imprimindo vetor após 2ª interação
	
	System.out.println("\n");
	System.out.println("\nVetor após segunda interação: ");
	
	for(int n=0;n<1000;n++) 
	{
		System.out.print(" "+vetor1[n]);
	}
	
	
	// Zerando a matriz
	
	
	for(int j=0; j<10;j++) 
	{
		for(int i=0; i<1000; i++) 
		{
			matriz1[i][j]=0;
		}		
	}
	
	// Zerando as filas
	
	f0=0; f1=0; f2=0; f3=0; f4=0; f5=0; f6=0; f7=0; f8=0; f9=0;
	
	// Terceira Interação (Centenas)
	
		for (int i=0; i<1000;i++) {
			switch (vetor1[i] /100) {
			case 0:
				matriz1[f0++][0] = vetor1[i];
				break;
				
			case 1:
				matriz1[f1++][1] = vetor1[i];
				break;
			
			case 2:
				matriz1[f2++][2] = vetor1[i];
				break;
				
			case 3:
				matriz1[f3++][3] = vetor1[i];
				break;
						
			case 4:
				matriz1[f4++][4] = vetor1[i];
			break;
			
			case 5:
				matriz1[f5++][5] = vetor1[i];
				break;
			
			case 6:
				matriz1[f6++][6] = vetor1[i];
				break;
			
			case 7:
				matriz1[f7++][7] = vetor1[i];
				break;
				
			case 8:
				matriz1[f8++][8] = vetor1[i];
				break;
						
			case 9:
				matriz1[f9++][9] = vetor1[i];
			break;
			}		
		}
		
		
		// Reconstrução do vetor após 3ª interação
		int p=0;
		for(int j=0; j<10;j++) 
		{
			for(int i=0; i<1000; i++) 
			{
				if(matriz1[i][j]>0) 
				{
					vetor1[p++]=matriz1[i][j];
				}
			}			
		}
		
		// Imprimindo vetor após 3ª interação
		
		System.out.println("\n");
		System.out.println("\nVetor após terceira interação: ");
		
		for(int n=0;n<1000;n++) 
		{
			System.out.print(" "+vetor1[n]);
		}
	
	
	
}

}

#2

Uma ideia de refatoração:

for (int i=0; i<1000;i++) 
{
	switch (vetor1[i] % 10) {			// Resto da divisão por 10
	case 0:
		matriz1[f0++][0] = vetor1[i];
		break;			
	case 1:
		matriz1[f1++][1] = vetor1[i];
		break;		
	case 2:
		matriz1[f2++][2] = vetor1[i];
		break;			
	case 3:
		matriz1[f3++][3] = vetor1[i];
		break;					
	case 4:
		matriz1[f4++][4] = vetor1[i];
	break;		
	case 5:
		matriz1[f5++][5] = vetor1[i];
		break;		
	case 6:
		matriz1[f6++][6] = vetor1[i];
		break;		
	case 7:
		matriz1[f7++][7] = vetor1[i];
		break;			
	case 8:
		matriz1[f8++][8] = vetor1[i];
		break;					
	case 9:
		matriz1[f9++][9] = vetor1[i];
	break;		
	}
}

A mesma ideia pode ser expressada com:

for (int i=0; i<1000;i++) 
{
	matriz1[f0++][vetor1[i] % 10] = vetor1[i];
}

Pode copiar essa ideia pra todos os fors com switch que vc fez.

1 curtida
#3

Um detalhe importante: percorrer a matriz pelas colunas ao invés de linhas como você faz no loop abaixo é extremamente ineficiente.

// Reconstrução do vetor após 1ª interação
int k=0;
for(int j=0; j<10;j++) {
	for(int i=0; i<1000; i++) {
		if(matriz1[i][j]>0) {
			vetor1[k++]=matriz1[i][j];
		}
	}
}

Isso acontece porque quando você carrega um elemento de uma matriz na memória, o processador coloca no cache os elementos próximos do que você acessou, que são os elementos da mesma linha. Toda vez que você troca de linha, ocorre um cache miss e o processador tem que ir até a memória para ler a informação que você precisa. Se conseguir inverter essa lógica pra percorrer as linhas ao invés das colunas, vai ficar mais rápido.

Mais informações: https://en.wikipedia.org/wiki/Row-_and_column-major_order

1 curtida