リンクリストにマージソートアルゴリズムを実装するC++プログラム

マージソート手法は、分割統治手法に基づいています。 whileデータセットを小さな部分に分割し、並べ替えられた順序で大きな部分にマージします。このアルゴリズムは最悪の場合にも時間計算量が少ないため、最悪の場合にも非常に効果的です。

リンクリストは、merge-sortを使用して非常に効率的に並べ替えることができます。リンクリストの場合、マージタスクは非常に簡単です。リンクを更新してマージするだけです。このセクションでは、このアプローチを使用してリンクリストを並べ替える方法を説明します。

マージソート手法の複雑さ

• 時間計算量 −すべての場合のo（n log n）

• スペースの複雑さ − o（n）

Input − The unsorted list: 14 20 78 98 20 45
Output − Array after Sorting: 14 20 20 45 78 98

アルゴリズム

mergeList（ll1、ll2）

入力 −2つのリンクリストll1とll2が必要です

出力 −マージされたリスト

Begin
   if ll1 is empty, then
      return ll2
   if ll2 is empty, then
      return ll1
   if data(ll1) <= data(ll2), then
      new_head = ll1;
      next(new_head) = mergeList(next(ll1), ll2)
   else
      new_head = ll2;
      next(new_head) = mergeList(ll1, next(ll2))
   return new_head
End

split_list（start、ll1、ll2）

入力 −リンクリストの開始ポインタ、2つの出力引数ll1およびll2

出力 −リンクリストから生成された2つのリンクリスト

Begin
   slow := start
   fast := next(start)
   while fast is not null, do
      fast := next(fast)
      if fast is not null, then
         slow := next(slow)
         fast := next(fast)
   end while
   ll1 := start
   ll2 := next(slow)
   next(slow) := null
End

mergeSort（start）

入力 −リンクリスト

出力 −ソートされたリンクリスト

Begin
   head = start
   if head is null or next(head) is null, then
      return
   split_list(head, ll1, ll2)
   mergeSort(ll1)
   mergeSort(ll2)
   start := mergeList(ll1, ll2)
End

ソースコード（C ++）

#include<bits/stdc++.h>
using namespace std;
class node { //define node to store data and next address
   public:
   int data;
   node *next;
};
void display(class node* start) {
   node* p = start; // current node set to head
   while(p != NULL) { //traverse until current node isn't NULL
      cout << p -> data << " ";
      p = p -> next; // go to next node
   }
}
node* getNode(int d) {
   node* temp = new node;
   temp -> data = d;
   temp -> next = NULL;
   return temp;
}
node* mergeList(node* ll1, node* ll2) { //function for merging two sorted list
   node* newhead = NULL;
   if(ll1 == NULL)
      return ll2;
   if(ll2 == NULL)
      return ll1;
   //recursively merge the lists
   if(ll1 -> data <= ll2 -> data) {
      newhead = ll1;
      newhead -> next = mergeList(ll1->next,ll2);
   } else {
      newhead = ll2;
      newhead -> next = mergeList(ll1,ll2->next);
   }
   return newhead;
}
void splitList(node* start, node** ll1,node** ll2) {
   //similar to flyod's tortoise algorithm
   node* slow = start;
   node* fast = start -> next;
   while(fast!= NULL) {
      fast = fast -> next;
      if(fast!= NULL) {
         slow = slow -> next;
         fast = fast -> next;
      }
   }
   *ll1 = start;
   *ll2 = slow -> next;
   //spliting
   slow -> next = NULL;
}
void mergeSort(node** start) {
   node* head = *start;
   node* ll1,*ll2;
   //base case
   if(head == NULL || head->next == NULL) {
      return;
   }
   splitList(head,&ll1,&ll2); //split the list in two halves
   //sort left and right sublists
   mergeSort(&ll1);
   mergeSort(&ll2);
   //merge two sorted list
   *start = mergeList(ll1,ll2);
   return;
}
int main() {
   cout << "Creating the linked list: " << endl;
   cout << "Enter 0 to stop building the list, else enter any integer" << endl;
   int k,count = 1,x;
   node* curr,*temp;
   cin >> k;
   node* head = getNode(k);   //buliding list, first node
   cin >> k;
   temp = head;
   while(k) {
      curr = getNode(k);
      temp -> next = curr;//appending each node
      temp = temp -> next;
      cin >> k;
   }
   cout<<"Before sorting: " << endl;
   display(head); // displaying the list
   cout<<"\nAfter sorting: " << endl;
   mergeSort(&head);
   display(head);
   return 0;
}

出力

Creating the linked list:
Enter 0 to stop building the list, else enter any integer
89
54
15
64
74
98
10
24
26
0
Before sorting:
89 54 15 64 74 98 10 24 26
After sorting:
10 15 24 26 54 64 74 89 98