Tri rapide

Le tri rapide est un algorithme de tri efficace utilisé dans plusieurs langages de programmation (C et Java par exemple).

L'idée générale de l'algorithme est la suivante :

on choisit une valeur « pivot » dans le tableau et on la garde en mémoire (ici on la place à la fin du tableau),
on parcourt l'ensemble des valeurs et on effectue des échanges de façon à ce que, à l'issue du parcours, les valeurs inférieures ou égales au pivot soient situées au début du tableau, celles strictement supérieures à la fin,
la position définitive du pivot est alors la frontière des deux zones. On peut ainsi le placer de façon certaine et réitérer la démarche de façon récursive sur chacune des zones.

Observons le déroulement du parcours, étape aussi appelée partition.

Ce parcours étudie successivement tous les éléments du tableau (variable i).

Lors du parcours on fait en sorte de ramener dans la zone de gauche du tableau les éléments inférieurs ou égaux au pivot. La variable curseur permet de repérer la position d'insertion du prochain élément inférieur au pivot.

Ainsi, à chaque étape du parcours, l'algorithme garantit que tous les éléments d'indice strictement inférieur à curseur sont inférieurs ou égaux au pivot.

État initial

Le pivot est le 5, il est en dernière position.

i et curseur sont initialisés à 0.

1ère étape : i = 0 et curseur = 0

Le 6 lu est strictement supérieur au pivot. On ne fait pas d'échange.

i augmente de 1.

curseur n'est pas modifié.

2ème étape : i = 1 et curseur = 0

Le 7 lu est strictement supérieur au pivot. On ne fait pas d'échange.

i augmente de 1.

curseur n'est pas modifié.

3ème étape : i = 2 et curseur = 0

Le 3 lu est inférieur ou égal au pivot : on l'échange avec le 6 situé à la position du curseur.

i augmente de 1.

curseur augmente de 1.

4ème étape : i = 3 et curseur = 1

Le 4 lu est inférieur ou égal au pivot : on l'échange avec le 7 situé à la position du curseur.

i augmente de 1.

curseur augmente de 1.

5ème étape : i = 4 et curseur = 2

Le 8 lu est strictement supérieur au pivot. On ne fait pas d'échange.

i augmente de 1.

curseur n'est pas modifié.

6ème étape : i = 5 et curseur = 2

Le 1 lu est inférieur ou égal au pivot : on l'échange avec le 6 situé à la position du curseur.

i augmente de 1.

curseur augmente de 1.

Fin du parcours : curseur = 3

En fin de parcours, curseur vaut 3 et est égal à la position définitive du pivot.

On échange le pivot 5 et le 7 (à la position du curseur).

Partition terminée :

Le pivot est à sa position définitive.

À sa gauche on ne trouve que des valeurs qui lui sont inférieures ou égales. À sa droite que des valeurs strictement supérieures.

Algorithme

On considère un tableau dont on souhaite trier les éléments d'indices compris entre debut (inclus) et fin (exclu).

On choisit comme pivot le dernier élément de la zone à trier. On a donc pivot = tableau[fin - 1].

La phase de partition du tableau consiste alors à parcourir tous les éléments de la zone à trier (sauf le pivot) afin de ramener les valeurs inférieures ou égales au pivot au début de la zone, les valeurs supérieures à la fin.

Pour ce faire on utilise deux indices :

i est l'indice utilisé lors du parcours. Il stocke l'indice de l'élément lu actuellement et évolue entre debut (inclus) et fin - 1 (exclu),
curseur est l'indice de l'élément qui sera échangé avec l'élément lu si besoin. Au fil du parcours, on est certain que tous les éléments d'indice strictement inférieur à curseur sont inférieurs ou égaux au pivot.

Ces deux indices sont initialisés à la valeur debut.

Étudions en détail une étape du parcours. On a déjà lu un certain nombre de valeurs et le déroulé de l'algorithme jusqu'à cette étape garantit que i est supérieur ou égal à curseur.

On lit donc la valeur tableau[i] et on la compare à pivot :

si cette valeur est strictement supérieure au pivot, comme elle est déjà dans la zone des valeurs supérieures (i >= curseur), on ne la déplace pas ;
si à l'inverse la valeur est inférieure ou égale au pivot, il faut la ramener dans la zone du début du tableau : on échange les valeurs d'indices i et curseur. La zone des valeurs inférieures s'est agrandie : on incrémente curseur en conséquence.

À la fin du parcours, les éléments d'indices strictement inférieurs à curseur sont tous inférieurs ou égaux au pivot. Ceux d'indice supérieurs ou égaux sont strictement supérieurs au pivot. On peut donc placer le pivot à la position curseur en faisant un dernier échange.

Il est ensuite possible de recommencer le tri sur le début du tableau (indice allant de debut inclus à curseur exclus) et la fin (indices entre curseur + 1 inclus et fin exclu).

La fonction partition

Compléter la fonction partition prenant en paramètre un tableau non vide tableau ainsi que deux entiers debut et fin et réalisant une partition du tableau entre les indices debut (inclus) et fin (exclus) en fonction de la valeur pivot située à l'indice fin-1.
La fonction renverra la position finale de la valeur pivot.

Évaluations restantes : 10/10

.128013s3_8ufvIy n7aSû1me(P24:jtwi]D[hE)6Oo;bcdUg/0lqp!.rL-,=+k95Rxé050O0s0z0n0B0T0b0k0N0T0n0b0b0$010z0B0V010406050b0f0r0r0n0Y0j040o0K0T0f110K0l0k020n0r0V0L0k0+0s1b0Y0U0f0s0b050R181a1c1e160V041C1J051M0R1M1O1J160O0B0h0_0{0}0 0F0B0Q0F0T1$0F0z14050;0M0T0s1X0|0~011#1%1)1%0z1/1;1-0z0M0K0O1e1.0Y1K0z0F0_1h0b0V0n0l0 0v011?1Z010g0?0s0l1p0s1-2e2g2l1^2o1;2r0r2t040a0k0u0Y0K0V0K0b0B1k1m0/2c0Y0Y0s0N2O1C2v0l1K0R2a2!0z2827290O2x0 1)0l2q2L1-1U1W0`1@2.0B2:0l241V1-0V2T1K2Y2!35172f1m2_2m2~0Y1b0T140k0q2X3915382w3b1^3d3f3h0v3k2g3m2Y2-013r0n3g040k0c3v2Z163y3p0 3B3D0k0w3H3x393z3N3h0*3R3J3T3L3A0K3e3C3h0I3Y3n3a1Y3q3%3s3E0m3,3K3/3M3;3)3E0e3^3!3`3$3(3O0)403o423V040q0S473.2`433=0q3j1D3l3Z484g4a0q3u4l3w4n4f3c3|3D0q3G4t2Z1L331C2@2%0O2+3z0N242D0.1V1K320s343l3R054M0/4U4o2m0(140/0g4W3_4g0A3h4+414p0g142f0Y112W4C4!4w1^13040t4:4#3q141 0s0n0f534~0 500#3R0k3-3U4(0s0M1j5b3z5e5g5i3#0l142o0l5o3#500H0x3Y0k5E5h4,3c4@1V0K0z5r5H1^0K140$5N4;5I0457595y42500E5Z4p5v2|5%2m5Q040!5+1^0r0B144k375O5d140C5D5F5s49140N0f0Y0b0s645T540 5-5S4|5G5U55040/5m5M4|06065F6f6a010N0q14032G1c4`0B1l0k0O0f0k5X5a6m6p604g4%040g3%695c3A140B6Q3z0K4.045*6e6K3c0M140Y2g0Q0s5:5{516.6S6i5l5n4|6$4 145f6#5`6=5w6;5-5/6_6 5=5@6;5A5C6I6p5 6 6M0B4*6~6g3M560n1:586H5_7k015#6;5u6Z795|6V3#5-020T0z0L6d356q6R7w0V5K6l7r6r507b356o7d7V6`7l5W7n1;5Y757s7u7%6r7w6U7*6R500C6}7I7X6=6G7y045$7.5j046365670Y7`5}7j6r6c7A617Z7o7$7P7/147|8e7~8066687}5z5|7=3l7J7~7_8n5!8g7v6T845~7V6J6 7w8k82894g5-0%7H8r7@774b3Y7U5E7@6t6v2G2L2N6A0l2:2C0l0z6C0-5w8Z0g6C6E7M0h5L8B8s5t7m8c7q4V6 7)8i8_6N6!9042736;8P5^8}7(8p8I5V8u944g8 9a7+62648l838v9h7z866R889s8t7!7p7`8h9j7K9l818m9g2m7:8q3w8^8a9f9B5p8x9p5V719R5P14749G5;5?8Q9U6/857T8D7s6M2T0z645x9v918G9F4m1C4Y4T4E9{0R4H1C0z4Ja02)2#23252%9x2!4H1I4}3z2T0r0d0g0n0(0s0d0F0c141u1w1y1A0k7S4V1P3m1J0Z1=0N0F0K0B0,8/0k8;5L0k1A8)0f2:0k0-0;0V1=0B1q3%0;8(0s0X1Lay040i0TaL0b8)2K0}0B7oaI1caL0,1v0V1;6C1=0z0K0f0ya 650_aD0B2M0Y0ka{0/0Y0l0B0sb80-0T0-8%8)6D6F9x590X0k0G1m0r0K0j2qaP0NaBb5aGaM0k2|0z0-2T0}2g8)1bb6bEa*bD320K1:bj0n11as0k2Mb9a}bo6EbD2|8Z3C1v2q8)2(0B0-0k0ta aIbIbXb/0-0Hbq0D2g0^bz0_0|0#b!b4aEaGbmbbbdbfaQbibk2c1a1=aJ8)590Qbk1=a{2~0r0M2T6C002JbHbV8!0^0l0-bzbJ0BbIaLbl1l0Nc64M0pblcp003C0Q3%2N0F2Ca#ax1T1V3z0n0Obubd2O0k2~0z2D1Ic$c(1l8Z1l0!4`2004aq1casa$ac0J1maT1j0kc)2(cdbXa{aCc8aHcbbebgcfb-ch2CaI7Nc,00bQ0|aI0-2r1)0bbKbY0B0k6B4S0l2,0baE2P1=0rbh6+cda{6G0k0n0hdx2QdN0Ydgbqa)a+cl0T3%0^d4b^bS9xa|0k2T0l4M8(2Tb8aObn8{0k1y0|0Bc_dVb;0Wd04G4Qac0PaP59d8aI2L2M0M0?2Nb;bD2Qdcb6cG0kd@ckdPbibVaEcu0Oc0c66Gb~evc20Nc4b!0^6GaGb)11b+cgb{cBcR0fcnb-bf1la-dr660lec1;cgdb0KcOd,0TcR0TcTdV2acXe21Jb eWb90nbY0f2N1=ei0:c.a=6,dA3ab5b7e@babfccdhbjdj4Mcidm8=cl5wd,2M1q1)2odMe@0ObU0YaCa!e29~0:0=0@04.

La fonction tri_rapide

Écrire la fonction tri_rapide prenant en paramètre un tableau ainsi que deux entiers debut et fin et triant le tableau entre les indices debut (inclus) et fin (exclu) à l'aide du tri rapide.

La fonction partition

On pourra s'aider de la fonction partition qui est déjà chargée en mémoire.

Évaluations restantes : 10/10

.128013s3o_;bcdufvg/lyà n7AapSr1-me,(P2=4:C+jtwki5h)é6050i0C0N0v0Q0o0b0r0h0o0v0b0b0H010N0Q0w010406050b0j0B0B0v0y0p040x0d0o0j0:0d0s050n0`0|0~100^0w04191g051j0n1j1l1g0^0i0Q0l0(0*0,0.0S0Q0m0S0o1z0S0N0?050Z0g0o0C1u0+0-011y1A1C1A0N1I1K1G0N0g0d0i101H0y1h0N0S0(130b0w0v0s0.0G011M1w010k0#0C0s0v0B0C1G1.1:1^1O1{1K1~200?0a0r0F0y0d0w0d0b0Q160s0r0X1,0y0y0C0h2l19230s1h0n1*2y0N1(1%1)0i250.1C0s1}2i1G1r1t0)1N2I0Q2K0s1!1s1G0w2r1h2w2y2$0_1/2m2Q1_2V0y0}0o0?0z2v2*0@2)242,1O2.2:0?0G2@1:2_2w2H012~0v2;040c322x0^352|0.383a0I3d342*363j0?0R3m3f3o3h370d2/390?0V3t2`2+1v2}3y2 040t3m1i2!192O2B0i2F360h1!211h3Q1k3O2(1a2^053V0X2#3v3G0.0P0?0X0k3M3g3.010O0?0r3@3-2R370k0?2C0Q0e0y0v0w0Q0X3~2{3_0=040E4c3F400s430v1J0C0v0j4i364f0D3m3}3^4k3;0C0g154s3w4u4w3E3p0?1{183%334I4F0?0T0J3t0r4V4x3 1_0h0z0?030r0K0+2n1L0g0+1L4L0r0A4+4C0N0r020o0N0f0r0z0r0J0r0j2m1V4p0j0r0l4a1L0C0b4^0i0U0M0q0r440U4U4W4P3_3:040Q3?4N2x4X4d4z044L4H4y1_0d0?0A5B4Y2}4A4@5H5x5D0?020m4|0H5M4j1_0B0Q2=4E4e0?4T5u0@4W5*5w5V5J040h0j0y0b0C5;5U365E045T5(5,4J041/0y0:2u5(5o404f4h665C5.554q5!680?4v5~672-5K4D6b5I0.4G6k6c3i4K2T6g1_4f0T5m5+5 3w4!4$0r0u0w0w0C0$0r0y0U5:5=5s0b6C5+6l6d0y4547494b6p5N1O696y6d4n1K6f6(5-6r6i5_3w4l040X5L6;4t6@6t6q370?6R5?5^6~4Q046B5(066D4V6X6v044446485a6,6?4g7n737i6.567q6s2$6E3_6`755@0y6^3_5{0L7E405X5Z785#046j7x7g7r5A7M6h7a3D0n3*0C2y2Z7!3P1s3R2B2D2z1Z1#2B7t2y3Q0^0n0X0Z0#0b04.