Tri par insertion de liste chaînée

Je ne suis pas encore très avancé dans le sorting de la programmation, je cherchais donc de l’aide pour mon algorithme.

void sortList() { Item_PTR tmpNxt = current->nextItem; Item_PTR tmpPTR = current; int a, tmp; while(tmpNxt != NULL) { a = tmpPTR->value; while(tmpNxt != tmpPTR && tmpNxt->value value = tmpNxt->value; tmpNxt->value = tmp; tmpPTR = tmpPTR->nextItem; } tmpPTR = current; tmpNxt = tmpNxt->nextItem; } } 

Etat de la liste avant le sorting: 9 8 7 6 5 4 3 2 1 après le sorting: 1 9 8 7 6 5 4 3 2

Je ne sais pas trop pourquoi … j’ai beaucoup joué à l’ordinateur sur papier et je sens que cela devrait fonctionner … mais peut-être que d’autres yeux remarqueront le problème.

Current est un pointeur global qui aura toujours l’emplacement du premier / premier élément de la liste.

En effet, la fonction sortList() ne change pas de current , la variable “globale” désignant l’en-tête de liste.

Veuillez ne pas utiliser de variable globale, et certainement pas pour une tête de liste liée. (Que ferez-vous quand vous aurez besoin de deux listes?)

Je sortList() fonction sortList() en l’un des éléments suivants:

 /* sort the list pointed to by phead and return the new head after sorting */ Item_PTR sortList( Item_PTR phead ); /* sort the list pointed to by *pphead */ void sortList( Item_PTR * pphead ); 

Aussi, familiarisez-vous (même si vous ne pouvez pas les utiliser dans le projet immédiat) à l’interface de la bibliothèque standard C ++ pour les listes, lien std::list

En plus des modifications suggérées par @Arun Saha, il semble y avoir une erreur logique (ne pas mettre à jour une valeur après la permutation), c’est pourquoi la liste n’est même pas imprimée dans l’ordre de sorting même à l’intérieur de la fonction de sorting. Le code suivant devrait résoudre ce problème.

 void sortList() { Item_PTR tmpNxt = current->nextItem; Item_PTR tmpPTR = current; while(tmpNxt != NULL) { while(tmpNxt != tmpPTR && tmpNxt->value < tmpPTR->value) { int tmp = tmpPTR->value; tmpPTR->value = tmpNxt->value; tmpNxt->value = tmp; tmpPTR = tmpPTR->nextItem; } tmpPTR = current; tmpNxt = tmpNxt->nextItem; } } 
  **Java code for insertion sort of linked list** package LinkedList; /** * Created by dheeraj on 5/1/15. */ public class InsertionSortLinkedList { private static final class Node { int value; Node next; public Node(int d) { value = d; next = null; } } private Node root; private Node sortedHead; private void addData(int data) { if (root == null) { root = new Node(data); } else { Node temp = new Node(data); temp.next = root; root = temp; } } private void printList() { Node temp = root; while (temp != null) { System.out.print(temp.value + " "); temp = temp.next; } System.out.println(); } private void printSortedList() { Node temp = sortedHead; while (temp != null) { System.out.print(temp.value + " "); temp = temp.next; } System.out.println(); } private void insertionSort() { Node outer = root; Node resultRoot = null; if (outer == null) { return; } while (outer != null) { if (resultRoot == null) { //System.out.println("null"); resultRoot = new Node(outer.value); } else { Node t = resultRoot; if (outer.value < t.value) { //current outer is smallest //System.out.println("smallest"); Node temp = new Node(outer.value); temp.next = t; resultRoot = temp; } else { boolean broken = false; while (t.next != null) { if (t.value < outer.value && outer.value <= t.next.value) { Node temp = new Node(outer.value); temp.next = t.next; t.next = temp; broken = true; //System.out.println("middle"); break; } // t = t.next; } if (!broken) { //current outer is greatest //System.out.println("largest"); t.next = new Node(outer.value); } } } outer = outer.next; } sortedHead = resultRoot; } public static void main(String[] args) { InsertionSortLinkedList insertionSortLinkedList = new InsertionSortLinkedList(); insertionSortLinkedList.addData(5); insertionSortLinkedList.addData(30); insertionSortLinkedList.addData(1); insertionSortLinkedList.addData(18); insertionSortLinkedList.addData(19); insertionSortLinkedList.printList(); insertionSortLinkedList.insertionSort(); insertionSortLinkedList.printSortedList(); } }