Bonjour.

J'ai une erreur qui est mal indiqué. Je cherche a faire un tris rapide sur une liste chainee. Je n'arrive pas a comprendre pour quoi cette erreur. Qu'en pensez vous ?

	public ListeChainee Tri_rapide() {
		if (head == null || head.next == null) {
			return this;
		} else {
			ListeChainee l1 = less_or_equal(head.value);
			ListeChainee l2 = more(head.value);
			l1 = l1.Tri_rapide();
			l2 = l2.Tri_rapide();
			l2.shift(head.value);
			return concatener(l1, l2);
		}
	}

	public ListeChainee concatener(ListeChainee l1, ListeChainee l2) {
		ListeChainee buffChainee = new ListeChainee();
		if (l1.isEmpty()) {
			buffChainee = l2;
		}else if (l2.isEmpty()) {
			buffChainee = l1;
		}else {
			buffChainee = l1;
			Cellule bufferCellule = buffChainee.head;
			while (bufferCellule.next != null) {
				bufferCellule = bufferCellule.next;
			}
			bufferCellule.next = l2.head;	
		}
		return buffChainee;
	}

	public ListeChainee more(int pivot) {
		ListeChainee bufferChainee = new ListeChainee();
		Cellule myCellule = head;
		if (myCellule.value > pivot) {
			bufferChainee.push(myCellule.value);
		}
		while (myCellule.next != null) {
			if (myCellule.next.value > pivot) {
				bufferChainee.push(myCellule.next.value);
			}
			myCellule = myCellule.next;
		}
		return bufferChainee;
	}

	public ListeChainee less_or_equal(int pivot) {
		ListeChainee bufferChainee = new ListeChainee();
		Cellule myCellule = head;
		if (myCellule.value <= pivot) {
			bufferChainee.push(myCellule.value);
		}
		while (myCellule.next != null) {
			if (myCellule.next.value <= pivot) {
				bufferChainee.push(myCellule.next.value);
			}
			myCellule = myCellule.next;
		}
		return bufferChainee;
	}

	public void init() {
		if (isEmpty()) {
			for (int i = 0; i < 10; i++) {
				int toPush = (int) (Math.random() * 50);
				push(toPush);
			}
			Tri_rapide();
		}
	}

Exception in thread "main" java.lang.StackOverflowError
    at ListeChainee.less_or_equal(ListeChainee.java:334)
    at ListeChainee.Tri_rapide(ListeChainee.java:289)

-
Edité par -Crixus- 26 novembre 2020 à 1:22:03

Bonjour,

StackOverflow signifie récursivité trop profonde. Le problème vient de ton algorithme.

Si le pivot est le maximum de l1, tu vas trier la même liste à l'infini.

Pour corriger ce problème, il faut couper ta liste en 3. Les plus petits, les égaux et les plus grands. La liste des éléments égaux au pivot n'a évidemment pas besoin d'être triée. Et ça te fera trois listes à concaténer.

Un autre problème de ton algorithme est le choix du pivot. Sur une liste en ordre décroissant, ton algo va ramer comme un tri à bulles.

La meilleure stratégie pour choisir le pivot est de le prendre au hasard dans ta liste

brubru777 a écrit:

Si le pivot est le maximum de l1, tu vas trier la même liste à l'infini.