Ordenar Vetor subdividindo em partes usando recursão!

[femoutela 0]

Caros preciso de uma ajuda nesse exercício não achei nada parecido, e gostaria de uma luz para começar!!!

 

 

Suponha um vetor armazenando dados de alunos associando a matrícula ao nome do aluno,

como por exemplo:

$alunos = array(

12345 => "João da Silva",

12567 => "Maria Almeida",

12677 => "Bernardo Nóbrega",

13567 => "Arnaldo Albuquerque"

);

Escreva uma função PHP que recebe o vetor de alunos desordenado e ordena o mesmo pelo

número de matrícula usando recursão. Sua função deve subdividir o vetor em duas metades

durante a recursão. Considere uma maneira eficiente de dividir o vetor durante o processo de

ordenação recursiva.

 

[Marcos Xavier 189]

Dá uma lida:

http://php.net/manual/pt_BR/function.ksort.php

http://php.net/manual/pt_BR/control-structures.foreach.php

[femoutela 0]

Obrigada amigo ,o problema é que o ksort não ordena recursivamente, e não reparte o array em duas metades.

[femoutela 0]

Comecei a escrever mas acho que não consegui chegar muito longe!!

 

<? php

function mergeSort(int[] array, int inicio, int fim) {

if (fim <= inicio) {

return;

}

int meio = (inicio + fim) / 2;

mergeSort(array, inicio, meio);

mergeSort(array, meio + 1, fim);

int[] A = new int[meio - inicio + 1];

int[] B = new int[fim - meio];

for (int i = 0; i <= meio - inicio; i++) {

A = array[inicio + i];

}

for (int i = 0; i <= fim - meio - 1; i++) {

B = array[meio + 1 + i];

}

int i = 0;

int j = 0;

for (int k = inicio; k <= fim; k++) {

if (i < A.length && j < B.length) {

if (A < B[j]) {

array[k] = A[i++];

} else {

array[k] = B[j++];

}

} else if (i < A.length) {

array[k] = A[i++];

} else if (j < B.length) {

array[k] = B[j++];

}

}

}

mergeSort($alunos = array(

12770 => "João da Silva",

12567 => "Maria Almeida",

13677 => "Bernardo Nóbrega",

11567 => "Arnaldo Albuquerque"

);

)

?>

[Williams Duarte 431]

Dividido o resto é com vc, so usar o ksort

 

<?php

$alunos = array(
12345=>'João da Silva', 
12567=>'Maria Almeida', 
12677=> 'Bernardo Nóbrega', 
13567=> 'Arnaldo Albuquerque'
); 



echo '<pre>';
print_r($alunos);
echo '</pre>';


echo '<pre>';
print_r(array_chunk($alunos, 2));
echo '</pre>';
echo '<pre>';
print_r(array_chunk($alunos, 2, true));
echo '</pre>';

[(RNU) Ruan Silva 61]

O algoritmo merge sort deve resolver seu problema.

 

em C ele fica assim:

#include 

void lerVet( int *p, int t ){

	int i;

	for ( i=0; i 1 ) {

		meio = t / 2;
		mergeSort(p, meio);
		mergeSort(p + meio, t - meio);
		merge(p, t);

	}
}


void main(){

	int *p, tam;

	printf("Quantidade de elementos do vetor?");
	scanf("%d",&tam);

	p = (int*) malloc(tam * sizeof(int));
	
	printf("\nDigite o conteudo do vetor:\n");
	lerVet(p, tam);

	printf("\nConteudo digitado para o vetor:\n");
	mostrarVet(p, tam);

	printf("\nOrdenando o vetor...\n");
	mergeSort(p, tam);

	printf("\nConteudo do vetor ja ordenado:\n");
	mostrarVet(p, tam);

	free(p);

}

Basta adaptar ao php ;)