Fusion de deux tableaux triés

Version imprimable

11/03/2011, 15h08
krolis

Fusion de deux tableaux triés

Bonjour,
J'ai deux tableaux d'entiers int[] t1={2,4,13,24,25} et int[] t2={26,20,19,11,1}.
Le premier est trié dans un ordre croissant, et le 2ème dans un ordre décroissant. Je voudrais les fusionner dans un autre tableau qui serait trié dans un ordre croissant. J'ai déjà essayé mais je n'arrive pas, parce que j'ai essayé une méthode où je fais d'abord la fusion, puis le tri du tableau qui en résulte. Mais moi je veux faire les deux traitement en même temps.
Merci,
11/03/2011, 15h12
tchize_

Pourriez vous nous montrer le code de ce que vous avez essayé de faire et qui ne marche pas?

Sans supprimer les doubles

Un essai qui doit fonctionner (sans supprimer les doubles éventuels et sans chercher à optimiser quoi que ce soit):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
	public static void merge( int[] increasing, int[] decreasing, int[] merged )
	{
		int leftIndex = 0;
		int rightIndex = decreasing.length-1;
 
		int mergedIndex = 0;
		while ( leftIndex < increasing.length && rightIndex >= 0 )
		{
			int leftValue = increasing[leftIndex];
			int rightValue = decreasing[rightIndex];
			if ( leftValue <= rightValue )
			{
				merged[mergedIndex++] = leftValue;
				leftIndex++;
			}
			else
			{
				merged[mergedIndex++] = rightValue;
				rightIndex--;
			}
		}
 
		if ( leftIndex < increasing.length )
			System.arraycopy( increasing, leftIndex, merged, mergedIndex, increasing.length-leftIndex );
		else
			while ( rightIndex >= 0 )
				merged[mergedIndex++] = decreasing[rightIndex--];
	}

Citation:

Envoyé par tchize_

Pourriez vous nous montrer le code de ce que vous avez essayé de faire et qui ne marche pas?

Voilà mon code. Je pense qu'il ne marchera convenablement qui si les 2 tableaux sont triés dans un ordre croissant.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public static void triTab(){ int[] t1 = {2,4,13,24,25}; int[] t2 = {26,20,19,11,1}; //Arrays.sort(t2); int m=t1.length, n=t2.length; int[] t3 = new int[m+n]; int i=0, j=0, k=0; while(i<m && j<n){ if(t1[i]<t2[j]){ t3[k++]=t1[i++]; } else{ t3[k++]=t2[j++]; } } if(i<m) System.arraycopy(t1, i, t3, k, m-i); if(j<n) System.arraycopy(t2, j, t3, k, n-j); for(int p=0; p<t3.length; p++){ System.out.println(t3[p]); } }
Citation:

Envoyé par hlbnet

Un essai qui doit fonctionner (sans supprimer les doubles éventuels et sans chercher à optimiser quoi que ce soit)

Votre code me donne une erreur ArrayIndexOutOfBoundsException

12/03/2011, 18h56
tchize_

vous avez juste a changer vos critère dans votre code. Le deuxième tableau doit être lu de la fin au début. Ca veux dire valeur initiale de l'index = length-1, index-- au lieu de index++ et index>=0 comme condition ;)
13/03/2011, 14h54
krolis
oui j'ai essayé votre solution. Mais ça me donne encore la fameuse erreur ArrayIndexOutOfBoundsException ici :

Code:

if(j<n) System.arraycopy(t2, j, t3, k, n-j);

à savoir que j'utilise ces deux lignes
Code:

1 2 if(i<m) System.arraycopy(t1, i, t3, k, m-i); if(j<n) System.arraycopy(t2, j, t3, k, n-j);
pour copier les autre valeurs qui restent.
Si je les supprime, j'ai le résultat suivant:
1
2
4
11
13
19
20
24
25
0
donc la valeur 26 est négligée.
le problème c'est dans arraycopy, je ne sais pas comment l'utiliser pour copier les valeurs qui restent
13/03/2011, 17h56
tchize_

vous ne pourrez pas utiliser arraycopy sur la fin du tableau, puisque l'ordre n'est pas celui que vous voulez au final ;)
13/03/2011, 19h34
krolis

alors c'est quoi la solution :s
13/03/2011, 20h08
adiGuba

Salut,

Pourquoi se compliquer la vie à ce point ?
Il suffit de joindre les deux tableaux et de trier le résultat...

a++
13/03/2011, 20h19
krolis

J'ai déjà utilisé cette solution, mais je veux pas faire les 2 traitements chacun à part
13/03/2011, 20h54
adiGuba

Citation:

Envoyé par krolis

J'ai déjà utilisé cette solution, mais je veux pas faire les 2 traitements chacun à part

Pourquoi ??? :koi:

a++
13/03/2011, 22h02
tchize_

parce qu'avec des très grand tableau on gagne du temps.

Arrays.copy ne marche pas -> Faites donc la copie vous même, tout simplement :roll:
13/03/2011, 22h36
krolis

Citation:

Envoyé par tchize_

parce qu'avec des très grand tableau on gagne du temps.

Arrays.copy ne marche pas -> Faites donc la copie vous même, tout simplement :roll:

avez-vous une façon de le faire? :roll:
13/03/2011, 23h03
tchize_

ben comme dans votre boucle :/ C'est pas compliqué de transférer des élements d'un tableau vers un autre quand même 8O
14/03/2011, 11h32
adiGuba

Citation:

Envoyé par tchize_

parce qu'avec des très grand tableau on gagne du temps.

Humm ouais...
Les données à traiter sont réellement si grande ? A mon avis il faut quand même avoir un très grand nombre de données pour avoir une différence sensible :?

a++
14/03/2011, 14h13
tchize_

en même temps, pour le peu de temps que ça met de fusionner deux tableau en préservant leur ordre inversé :)

Mais bon, j'admet qu'on a probablement passé plus de temps à répondre à la question que n'en consommera jamais l'algorithme naif que tu propose ;)

Je ne vois pas d'erreur dans la solution que j'ai donné au début.
Voici le programme de test que j'utilise pour tester la fonction merge que j'ai donné plus haut.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package test;
 
import java.util.Arrays;
import java.util.Random;
 
public class MergeIncreasingDecreasing
{
    public static Random random = new Random( System.nanoTime() );
 
    private static final int NB_OF_TEST = 10;
 
    public static void main( String[] args )
    {
        int maxLength = 1;
        for ( int test = 0; test < NB_OF_TEST; test++, maxLength *= 2 )
        {
            int[] increasing = buildRandomSortedIntArray( true, random.nextInt( maxLength ) );
            int[] decreasing = buildRandomSortedIntArray( false, random.nextInt( maxLength ) );
 
            System.out.println( "===============================================================================" );
            System.out.println( "Croissant:"+ Arrays.toString( increasing ) );
            System.out.println( "Décroissant:"+ Arrays.toString( decreasing ) );
 
            int[] merged = new int[increasing.length+decreasing.length];
            merge( increasing, decreasing, merged );
            System.out.println( "Fusion:"+ Arrays.toString( merged ) );
        }
    }
 
 
    private static int[] buildRandomSortedIntArray( boolean increasing, int length )
    {
        int[] array = new int[length];
        for ( int i = 0; i < array.length; i++ )
            array[i] = random.nextInt( 10*length );
 
        Arrays.sort( array );
        if ( !increasing )
        {
            for ( int i = 0, max = array.length/2; i < max; i++ )
            {
                int tmp = array[array.length-i-1];
                array[array.length-i-1] = array[i];
                array[i] = tmp;
            }
        }
 
        return array;
    }
 
 
    public static void merge( int[] increasing, int[] decreasing, int[] merged )
    {
        int leftIndex = 0;
        int rightIndex = decreasing.length-1;
 
        int mergedIndex = 0;
        while ( leftIndex < increasing.length && rightIndex >= 0 )
        {
            int leftValue = increasing[leftIndex];
            int rightValue = decreasing[rightIndex];
            if ( leftValue <= rightValue )
            {
                merged[mergedIndex++] = leftValue;
                leftIndex++;
            }
            else
            {
                merged[mergedIndex++] = rightValue;
                rightIndex--;
            }
        }
 
        if ( leftIndex < increasing.length )
            System.arraycopy( increasing, leftIndex, merged, mergedIndex, increasing.length-leftIndex );
        else
            while ( rightIndex >= 0 )
                merged[mergedIndex++] = decreasing[rightIndex--];
    }
}

J'imagine que vous ne passez pas les bons paramètres.

15/03/2011, 12h37
hlbnet

Une exécution du programme précédent

Une exécution du programme précédent donne par exemple:
===============================================================================
Croissant:[]
Décroissant:[]
Fusion:[]
===============================================================================
Croissant:[9]
Décroissant:[]
Fusion:[9]
===============================================================================
Croissant:[5, 11]
Décroissant:[6, 1]
Fusion:[1, 5, 6, 11]
===============================================================================
Croissant:[]
Décroissant:[13, 12, 8]
Fusion:[8, 12, 13]
===============================================================================
Croissant:[21, 42, 56, 57, 58, 66, 66]
Décroissant:[15, 11, 10, 4]
Fusion:[4, 10, 11, 15, 21, 42, 56, 57, 58, 66, 66]
===============================================================================
Croissant:[0, 5, 26, 35, 42, 53, 64, 67, 76, 77, 85, 108, 123]
Décroissant:[246, 235, 224, 220, 214, 200, 164, 150, 139, 130, 123, 116, 113, 103, 102, 101, 96, 88, 67, 55, 52, 46, 40, 32, 14]
Fusion:[0, 5, 14, 26, 32, 35, 40, 42, 46, 52, 53, 55, 64, 67, 67, 76, 77, 85, 88, 96, 101, 102, 103, 108, 113, 116, 123, 123, 130, 139, 150, 164, 200, 214, 220, 224, 235, 246]
===============================================================================
Croissant:[5, 36, 58, 59, 65, 78, 82, 91, 94, 112, 112, 120, 129, 147, 154, 161, 173, 177, 188, 193, 195, 200]
Décroissant:[207, 192, 189, 187, 182, 160, 152, 148, 133, 125, 94, 92, 68, 68, 62, 49, 40, 25, 24, 4, 1]
Fusion:[1, 4, 5, 24, 25, 36, 40, 49, 58, 59, 62, 65, 68, 68, 78, 82, 91, 92, 94, 94, 112, 112, 120, 125, 129, 133, 147, 148, 152, 154, 160, 161, 173, 177, 182, 187, 188, 189, 192, 193, 195, 200, 207]
===============================================================================
Croissant:[7, 44, 44, 59, 65, 96, 98, 98, 103, 104, 116, 119]
Décroissant:[194, 186, 186, 177, 173, 163, 157, 147, 144, 142, 126, 115, 103, 96, 91, 81, 63, 62, 26, 16]
Fusion:[7, 16, 26, 44, 44, 59, 62, 63, 65, 81, 91, 96, 96, 98, 98, 103, 103, 104, 115, 116, 119, 126, 142, 144, 147, 157, 163, 173, 177, 186, 186, 194]
===============================================================================
Croissant:[9, 10, 10, 26, 29, 36, 52, 75, 81, 99, 110, 128, 131, 141, 147, 162, 169, 184, 215, 218, 227, 240, 254, 264, 266, 271, 275, 283, 289, 301, 312, 323, 329, 341, 365, 389, 414, 417, 433, 433, 436, 439, 442, 447, 462, 466, 468, 492, 493, 495, 504, 509, 515, 533, 556, 570, 573, 597, 608, 613, 614, 616, 622, 626, 633, 642, 647, 661, 685, 686, 701, 727, 732, 753, 774, 782, 810, 813, 832, 833, 847, 855, 858, 868, 877, 879, 897, 906, 912, 923, 924, 938, 938, 939, 970, 975, 1011, 1033, 1039, 1055, 1062, 1062, 1075, 1092, 1094, 1098, 1111, 1124, 1126, 1151, 1179, 1179, 1185, 1186, 1192, 1194, 1200, 1206, 1214, 1227, 1239, 1245, 1248, 1275, 1286, 1310, 1329, 1341, 1360, 1368, 1368, 1372, 1388, 1391, 1407, 1410, 1415, 1424, 1424, 1432, 1432, 1454, 1455, 1458, 1459, 1474, 1532, 1541, 1565, 1587, 1597, 1608, 1616, 1624, 1636, 1637, 1657, 1661, 1669, 1677, 1682, 1688, 1718, 1719, 1727, 1729, 1731, 1737, 1743, 1747, 1751, 1756, 1771, 1776, 1806, 1822, 1832, 1868, 1872, 1873, 1878, 1883, 1886, 1910, 1924, 1929, 1932, 1933, 1938, 1941, 1956, 1975, 1976, 1978, 1983, 1984, 1985, 1991, 2014, 2015, 2017, 2017, 2021, 2030]
Décroissant:[762, 760, 758, 750, 750, 745, 694, 684, 676, 640, 639, 607, 599, 596, 573, 571, 571, 568, 554, 548, 514, 507, 501, 485, 480, 476, 473, 473, 469, 467, 457, 453, 449, 422, 422, 420, 412, 411, 411, 394, 381, 345, 334, 334, 333, 333, 315, 298, 285, 283, 261, 252, 245, 245, 243, 230, 214, 206, 191, 190, 171, 161, 149, 147, 139, 133, 113, 110, 79, 70, 65, 56, 47, 42, 19, 6, 3]
Fusion:[3, 6, 9, 10, 10, 19, 26, 29, 36, 42, 47, 52, 56, 65, 70, 75, 79, 81, 99, 110, 110, 113, 128, 131, 133, 139, 141, 147, 147, 149, 161, 162, 169, 171, 184, 190, 191, 206, 214, 215, 218, 227, 230, 240, 243, 245, 245, 252, 254, 261, 264, 266, 271, 275, 283, 283, 285, 289, 298, 301, 312, 315, 323, 329, 333, 333, 334, 334, 341, 345, 365, 381, 389, 394, 411, 411, 412, 414, 417, 420, 422, 422, 433, 433, 436, 439, 442, 447, 449, 453, 457, 462, 466, 467, 468, 469, 473, 473, 476, 480, 485, 492, 493, 495, 501, 504, 507, 509, 514, 515, 533, 548, 554, 556, 568, 570, 571, 571, 573, 573, 596, 597, 599, 607, 608, 613, 614, 616, 622, 626, 633, 639, 640, 642, 647, 661, 676, 684, 685, 686, 694, 701, 727, 732, 745, 750, 750, 753, 758, 760, 762, 774, 782, 810, 813, 832, 833, 847, 855, 858, 868, 877, 879, 897, 906, 912, 923, 924, 938, 938, 939, 970, 975, 1011, 1033, 1039, 1055, 1062, 1062, 1075, 1092, 1094, 1098, 1111, 1124, 1126, 1151, 1179, 1179, 1185, 1186, 1192, 1194, 1200, 1206, 1214, 1227, 1239, 1245, 1248, 1275, 1286, 1310, 1329, 1341, 1360, 1368, 1368, 1372, 1388, 1391, 1407, 1410, 1415, 1424, 1424, 1432, 1432, 1454, 1455, 1458, 1459, 1474, 1532, 1541, 1565, 1587, 1597, 1608, 1616, 1624, 1636, 1637, 1657, 1661, 1669, 1677, 1682, 1688, 1718, 1719, 1727, 1729, 1731, 1737, 1743, 1747, 1751, 1756, 1771, 1776, 1806, 1822, 1832, 1868, 1872, 1873, 1878, 1883, 1886, 1910, 1924, 1929, 1932, 1933, 1938, 1941, 1956, 1975, 1976, 1978, 1983, 1984, 1985, 1991, 2014, 2015, 2017, 2017, 2021, 2030]
===============================================================================
Croissant:[0, 8, 19, 40, 46, 46, 64, 81, 87, 105, 112, 125, 132, 142, 148, 148, 163, 165, 176, 179, 180, 190, 197, 199, 214, 252, 258, 290, 297, 300, 306, 326, 328, 366, 382, 382, 386, 389, 390, 393, 403, 405, 424, 439, 459, 470, 472, 477, 489, 504, 505, 523, 530, 530, 536, 536, 546, 552, 597, 598, 606, 625, 642, 656, 664, 676, 685, 705, 717, 720, 727, 749, 750, 755, 760, 762, 766, 780, 782, 787, 798, 812, 816, 846, 882, 894, 918, 925, 928, 933, 934, 934, 938, 961, 965, 968, 982, 987, 995, 1006, 1013, 1019, 1022, 1024, 1030, 1046, 1060]
Décroissant:[1121, 1113, 1106, 1106, 1097, 1059, 1045, 1044, 1033, 1014, 999, 988, 982, 972, 964, 962, 956, 955, 947, 930, 900, 879, 877, 876, 864, 861, 829, 822, 813, 809, 803, 801, 790, 789, 785, 775, 749, 720, 709, 708, 706, 700, 672, 670, 670, 666, 664, 657, 647, 631, 624, 616, 593, 570, 557, 549, 522, 514, 505, 490, 479, 476, 466, 466, 458, 452, 449, 435, 420, 405, 403, 400, 388, 386, 373, 366, 361, 347, 312, 305, 296, 294, 279, 274, 271, 269, 267, 266, 261, 257, 246, 209, 206, 199, 170, 142, 138, 121, 117, 114, 88, 84, 81, 69, 68, 62, 53, 28, 23, 15, 14, 13, 4]
Fusion:[0, 4, 8, 13, 14, 15, 19, 23, 28, 40, 46, 46, 53, 62, 64, 68, 69, 81, 81, 84, 87, 88, 105, 112, 114, 117, 121, 125, 132, 138, 142, 142, 148, 148, 163, 165, 170, 176, 179, 180, 190, 197, 199, 199, 206, 209, 214, 246, 252, 257, 258, 261, 266, 267, 269, 271, 274, 279, 290, 294, 296, 297, 300, 305, 306, 312, 326, 328, 347, 361, 366, 366, 373, 382, 382, 386, 386, 388, 389, 390, 393, 400, 403, 403, 405, 405, 420, 424, 435, 439, 449, 452, 458, 459, 466, 466, 470, 472, 476, 477, 479, 489, 490, 504, 505, 505, 514, 522, 523, 530, 530, 536, 536, 546, 549, 552, 557, 570, 593, 597, 598, 606, 616, 624, 625, 631, 642, 647, 656, 657, 664, 664, 666, 670, 670, 672, 676, 685, 700, 705, 706, 708, 709, 717, 720, 720, 727, 749, 749, 750, 755, 760, 762, 766, 775, 780, 782, 785, 787, 789, 790, 798, 801, 803, 809, 812, 813, 816, 822, 829, 846, 861, 864, 876, 877, 879, 882, 894, 900, 918, 925, 928, 930, 933, 934, 934, 938, 947, 955, 956, 961, 962, 964, 965, 968, 972, 982, 982, 987, 988, 995, 999, 1006, 1013, 1014, 1019, 1022, 1024, 1030, 1033, 1044, 1045, 1046, 1059, 1060, 1097, 1106, 1106, 1113, 1121]