Fusion de deux tableaux triés

**krolis** · 11/03/2011, 14h08

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,

**tchize_** · 11/03/2011, 14h12

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

**hlbnet** · 11/03/2011, 14h56

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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--];
	}

**krolis** · 12/03/2011, 15h56

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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]);
		}
	}

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

**tchize_** · 12/03/2011, 17h56

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

**krolis** · 13/03/2011, 13h54

oui j'ai essayé votre solution. Mais ça me donne encore la fameuse erreur ArrayIndexOutOfBoundsException ici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

à savoir que j'utilise ces deux lignes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**tchize_** · 13/03/2011, 16h56

vous ne pourrez pas utiliser arraycopy sur la fin du tableau, puisque l'ordre n'est pas celui que vous voulez au final

**krolis** · 13/03/2011, 18h34

alors c'est quoi la solution :s

**adiGuba** · 13/03/2011, 19h08

Salut,

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

a++

**krolis** · 13/03/2011, 19h19

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

**adiGuba** · 13/03/2011, 19h54

Envoyé par krolis

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

Pourquoi ???

a++

**tchize_** · 13/03/2011, 21h02

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

**krolis** · 13/03/2011, 21h36

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

avez-vous une façon de le faire?

**tchize_** · 13/03/2011, 22h03

ben comme dans votre boucle :/ C'est pas compliqué de transférer des élements d'un tableau vers un autre quand même

**adiGuba** · 14/03/2011, 10h32

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++

**tchize_** · 14/03/2011, 13h13

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

**hlbnet** · 15/03/2011, 10h38

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**hlbnet** · 15/03/2011, 11h37

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]

Fusion de deux tableaux triés

Langage Java

Discussions similaires

Partager

Partager