sorting

[polska]

Boas pessoal, tenho uma dúvida em relação a fazer sort a dois arrays, por exemplo:

Eu tenho o array list1, e list2 :

list1 = { 5, 9, 3, 8, 6 }

list2 = { 20, 40, 10, 80, 30 }

Eu quero usar um algoritmo de sorting tipo o merge sort ou o quick sort, mas quero que ao ordenar por ordem crescente a list1, ao mesmo tempo tem que ordenar a list2, ou seja, se na list um vou colocar o 3 em primeiro lugar, o 10 também tem que ir para primeiro lugar na list2 ...

Eu sei usar o merge sort e o qsort , mas não estou a perceber se conssigo fazer o que quero, e como fazer..

[HappyHippyHippo]

a única coisa que necessitas é que o processo de troca de lista1 e lista1[j] faças também a mesma troca na lista2

do género

int sort(...)
{
 // algoritmo
 troca(lista1, lista2, i, j);
}

void troca(int * lista1, int * lista2, int i, int j)
{
 // troca na lista1
 // troca na lista2
}

ps : ou tens o mais simples

struct Elem {
 int elem_lista_1;
 int elem_lista_2;
}

struct Elem * lista_unica;

Edited July 3, 2012 at 02:26 PM by HappyHippyHippo

[polska]

a única coisa que necessitas é que o processo de troca de lista1 e lista1[j] faças também a mesma troca na lista2

do género

int sort(...)
{
 // algoritmo
 troca(lista1, lista2, i, j);
}

void troca(int * lista1, int * lista2, int i, int j)
{
 // troca na lista1
 // troca na lista2
}

ps : ou tens o mais simples

struct Elem {
 int elem_lista_1;
 int elem_lista_2;
}

struct Elem * lista_unica;

Ou seja, por exemplo neste código de merge sort:

void mergesort( int A[], int B[], int inicio, int final )
{

int esquerda = 0, direita = 0, meio = 0;
int i = 0;

if( inicio == final )
 return;

meio = ( inicio+final ) / 2;

mergesort( A, B, inicio, meio );
mergesort( A, B, meio+1, final );

esquerda = inicio;
direita = meio+1;

for( i=inicio; i<=final; i++ )
{
 if( direita > final  || ( esquerda <= meio && A[esquerda] <= A[direita] ) )
 {
      B[i] = A[esquerda];
   esquerda++;
 }
 else
 {
   B[i] = A[direita];
   direita++;
 }
}

for( i=inicio; i<=final; i++ )
 A[i] = B[i];
}

Tenho que passar como argumento a list1 e um vector auxiliar para troca, e a list2 e um vector auxiliar para troca, e depois na parte final, no último for, por exemplo, quando faz B = A[direita]; , faço isto também para a list2, certo?

Edited July 3, 2012 at 02:33 PM by polska

[HappyHippyHippo]

se a lista A e a lista B são listas independentes, porque raio o teu código está cheio de atribuições entre A e B ??

[polska]

se a lista A e a lista B são listas independentes, porque raio o teu código está cheio de atribuições entre A e B ??

Isto é um programa que usa o merge sort, mais nada... Não é o programa onde quero implementar as listas... Tava-te a perguntar se ao por o merge no outro programa, envio a list1 como A, envio a list2 como B, e depois envio dois arrays auxiliares para fazerem as trocas..

[mogers]

No fundo, quando estás a mexer nos elementos durante a ordenação, tens de tratar as 2 listas como um bloco, isto é, ao ordenares os elementos da primeira lista, fazes também os swaps correspondentes na 2ª lista.

Usar um struct é capaz de ser a forma mais simples pois moves blocos de uma vez só.

Outra hipótese é ordenares uma lista de indices e quando fazes os testes if (lista1[ i ] < lista2[ j ] ) passas a ter if (lista1[ ind[ i ] ] < lista1[ind[ j] ]

[polska]

void mergesort( int list1[], int B[], int list2[], int B1[], int inicio, int final )
{

int esquerda = 0, direita = 0, meio = 0;
int i = 0;

if( inicio == final )
 return;

meio = ( inicio+final ) / 2;

mergesort( list1, B, list2, B1, inicio, meio );
mergesort( list1, B, list2, B1, meio+1, final );

esquerda = inicio;
direita = meio+1;

for( i=inicio; i<=final; i++ )
{
 if( direita > final  || ( esquerda <= meio && list1[esquerda] <= list1[direita] ) )
 {
	    B[i] = list1[esquerda];
		esquerda++;
	    B1[i] = list2[esquerda];
  }
  else
  {
		 B[i] = list1[direita];
	     direita++;
            B1[i] = list2[direita];
   }
}

for( i=inicio; i<=final; i++ )
{
  list1[i] = B[i];
  list2[i] = B1[i];
 }
}

Porque é que este código não funciona? Quando eu faço alterações na list1, faço na list2 ...

Edited July 3, 2012 at 06:37 PM by polska

[polska]

Já conssegui, deixo aqui o sort 😄

void mergesort( int list1[], int B[], int list2[], int B1[], int inicio, int final )
{
int esquerda = 0, direita = 0, meio = 0;
int i = 0;
if( inicio == final )
return;
meio = ( inicio+final ) / 2;
mergesort( list1, B, list2, B1, inicio, meio );
mergesort( list1, B, list2, B1, meio+1, final );
esquerda = inicio;
direita = meio+1;
for( i=inicio; i<=final; i++ )
{
if( direita > final || ( esquerda <= meio && list1[esquerda] <= list1[direita] ) )
 {
B[i] = list1[esquerda];
B1[i] = list2[esquerda];
esquerda++;
 }
 else
{
	 B[i] = list1[direita];
B1[i] = list2[direita];
direita++;
 }
 }
 for( i=inicio; i<=final; i++ )
{
list1[i] = B[i];
list2[i] = B1[i];
}
}

Edited July 3, 2012 at 07:06 PM by polska

[mogers]

É bom aprenderes o mergesort porque tem aplicações muito úteis, mas, de um modo geral, a ordenação pode ser feita simplesmente com as bibliotecas. Só para te dar uma ideia, poderias fazer isso em C++ com

#include <algorithm>
using namespace std;
pair<int,int> nums[100000];
// input
for (i = 0 ; i < n ; i++) 
   scanf("%d %d", &nums[i].first , &nums[i].second);  // par de numeros.  ".first" é o primeiro, ".second" é o segundo
// ordernar
sort( nums, nums + n );  // uso do introsort O(N log N)

[pikax]

Um simples bubble sort nao resolveria a coisa?

[polska]

É bom aprenderes o mergesort porque tem aplicações muito úteis, mas, de um modo geral, a ordenação pode ser feita simplesmente com as bibliotecas. Só para te dar uma ideia, poderias fazer isso em C++ com

#include <algorithm>
using namespace std;
pair<int,int> nums[100000];
// input
for (i = 0 ; i < n ; i++)
scanf("%d %d", &nums[i].first , &nums[i].second);  // par de numeros.  ".first" é o primeiro, ".second" é o segundo
// ordernar
sort( nums, nums + n );  // uso do introsort O(N log N)

Aindo só aprendi a usar o merge e o qsort do stdlib.h , mas vou aprender a usar esse, mas o exemplo que tem no cplusplus é muito mais complexo do que o que deste ai.. xD

Um simples bubble sort nao resolveria a coisa?

Resolvia, mas já é tempo de aprender os algoritmos mais eficientes.. E como nunca os tinha usado experimentei desta vez, em vez do bubble sort.

[pikax]

Resolvia, mas já é tempo de aprender os algoritmos mais eficientes.. E como nunca os tinha usado experimentei desta vez, em vez do bubble sort.

O merge sort diminuias a complexidade(no termo de estares a complicar) se juntasses as duas listas numa so' e aplicasses o mergesort, seria mais simples de implementar

[polska]

O merge sort diminuias a complexidade(no termo de estares a complicar) se juntasses as duas listas numa so' e aplicasses o mergesort, seria mais simples de implementar

Tipo uma matriz ?

[Rui Carlos]

Tipo uma matriz ?

Ou tipo a struct que o HappyHippyHippo sugeriu.

[polska]

Ja percebi, obrigado a todos 🙂