Gymnastique algorithmique 16

Merge Sort Le tri par fusion est l'un des algorithmes de tri les plus connus qui utilisent la division et la conquête. Il s'agit d'un algorithme de tri qui tente de réaliser le tri en divisant et en fusionnant de manière récursive. Cette fois, je voudrais utiliser ce tri de fusion pour trier la liste liée au lieu du tableau.

Exemple

Solution

Runtime Complexity O(n(log(n)) Il faut proportionnel à n pour fusionner avec n listes. (fusionner) De plus, il faut un temps de log (n) pour diviser n éléments de données en deux éléments. (diviser) Par conséquent, le temps d'exécution est O (n log (n)). Memory Complexity O（log n) L'utilisation de la récurrence consomme de la mémoire sur la pile, ce qui entraîne O (log n).

L'étape de fractionnement divise la liste saisie en deux et se poursuit avec une liste de taille 1 ou 0. L'étape de jointure fusionne les listes triées et se poursuit jusqu'à ce que les listes soient complètement triées. La relation récursive de cet algorithme de tri par fusion est la suivante:

T（n）= 2T（n / 2）+ n

Cette formule est utilisée lors de l'analyse de la complexité d'exécution de l'algorithme récursif, comme dans les cours universitaires. Puisqu'il s'agit d'un contenu à traiter, je n'entrerai pas dans cela, mais si vous êtes intéressé, cliquez ici Référence.

Façon de penser

Puisque le tri par fusion est effectué sur la liste au lieu du tableau, les liens des nœuds adjacents lors du fractionnement Je vais le couper. Ensuite, vous avez l'impression de comparer un nœud les uns aux autres et de les réorganiser tout en les fusionnant. L'implémentation peut être un peu déroutante car elle utilise la récurrence. L'idée est qu'il existe trois méthodes. Utilisez la première méthode mergeSort pour créer une division et une fusion de trame logique approximative. Ensuite, la deuxième méthode splitHalf est un rôle de division, qui a pour rôle de fractionner le lien. Placez les têtes des deux listes fractionnées dans l'objet paire. Et la troisième méthode mergeSortedList est le rôle de fusion, qui est responsable de la fusion et de la réorganisation des nœuds séparés.

la mise en oeuvre

MergeSort.java

class MergeSort{

    public LinkedListNode mergeSort(LinkedListNode head) {

      // base case
      if (head == null || head.next == null) {
        return head;
      }

      Pair<LinkedListNode, LinkedListNode> pair = new Pair<LinkedListNode, LinkedListNode>(null, null);
      
      // Let's split the list in half, sort the sublists
      // and then merge the sorted lists.

      splitHalf(head, pair);

      pair.first = mergeSort(pair.first);
      pair.second = mergeSort(pair.second);

      return mergeSortedList(pair.first, pair.second);
  }
    // this method splits linked list in two halves by iterating over whole list
    // It returns head pointers of first and 2nd halves of linked lists in pair
    // Head of 1st half is just the head node of linked list
   public void splitHalf(LinkedListNode head, Pair<LinkedListNode, LinkedListNode> pair) {
      
      if (head == null) {
        return;
      }

      if (head.next == null) {
        pair.first = head;
        pair.second = null;
      } else {
        
        LinkedListNode slow = head;
        LinkedListNode fast = head.next;

      // Two pointers, 'fast' and 'slow'. 'fast' will move two steps in each 
      // iteration whereas 'slow' will be pointing to the middle element
      // at the end of the loop
        while (fast != null) {

          fast = fast.next;

          if(fast != null) {
            fast = fast.next;
            slow = slow.next;
          }
        }

        pair.first = head;
        pair.second = slow.next;

        // disconnecting the first linked list with the second one
        slow.next = null;
      }
    }
    public LinkedListNode mergeSortedList(LinkedListNode first, LinkedListNode second) {
      
      if (first == null) {
        return second;
      }

      if (second == null){
        return first;
      }

      LinkedListNode newHead;

      if (first.data <= second.data) {
        newHead = first;
        first = first.next;
      } else {
        newHead = second;
        second = second.next;
      }

      LinkedListNode current = newHead;

      while (first != null && second != null) {
        LinkedListNode temp = null;
        if (first.data <= second.data) {
          temp = first;
          first = first.next;
        } else {
          temp = second;
          second = second.next;
        }

        current.next = temp;
        current = current.next;
      }

      if (first != null) {
        current.next = first;
      } else if (second != null) {
        current.next = second;
      }

      return newHead;
    }
}

Output Trié comme ça!