Merge_n_Insertion_sorting

// include file
#include <condefs.h>
#include <conio>
#include <iostream>
#include <fstream>

//dibatasi memori 52
#define MAXLIST 52
#define MAXINT (int) (2147483647)
using namespace std;
//struktur data kita tetap dan fleksible
typedef char item_type;
typedef struct node_tag;
{
  Item_type info;
  struct node_tag *next;
} Node_type;
typdedef struct list_ag
{
  Node_type *head;
  Node_type *tail;
} List_type;
//prototype fungsi operasi pada link list
void AddNode(List_type* ,Item_type , const int opt=0);
void DeleteNode(List_type , Item_type);
void Error (char*);
bool ExtractLine(Item_type& , Item_type);
void InitList(List_type* );
Node_type *MergeSort(Node_type *p);
List_type *InsertionSort (List_type *);
bool FindItem(const List_type* ,Item_type);
void Transverse(const List_type* ,void (*Visit) (ItemType));
void Visit(Item_type);
char Menu(void);
void CopyList(const List_type *, List_type *);
void BatchSort(List_type *list_ptr);
//var globaluntuk menghitng jumlah loop
int gloop1=0, gswap1=0, gcomp1=0;
int gloop2=0, gswap2=0, gcomp2=0;
//program utama
int main()
{   //variabel untuk list dan pointer ke list
    List_type list;List_type* list_ptr=&lst;
    List_type rlist;List_type* rlist_ptr=&rlist;
    List_type ilist, mlist;
    List_type *iSort=&ilist, *mSort=&mlist;
    int konter = 0; sring line; char ch='y';
    InitList(list_ptr); InitList(rlist_ptr);
    // ambil data dari file teks
    ifstream infile("bahasa.txt");
    //kita baca satu baris teks dari file
    while (getline(infile,line) && (konter < MAXLIST))
    {  //kita ambil karakter per karakter
      int i=0; //indeks karakter pada indeks dibaca
      //ambil satu karakter
      while ((i<line.length))) && (konter < MAXLIST))
      if (isalpha(line[i]))
         if (!FindItem(rlist_ptr,line[i])) //simpan ke list
              { konter++;AddNode(rlist_ptr,line[i]);
         i++; //ke karakter berikutnya
    }
}
Traverse(rlist_ptr,*Visit); //tampilkan daftar asli
//loop program utama
while (!(ch=='S' || ch =='\x1b'))
{  ch = Menu();     //tamplkan menu dan minta input
    switch (ch)
    {
      case '1': Traverse(rlist_ptr,*Visit);break;
      case '2': //sorting dengan insertion sort
         // kita kosongkan loop untuk perhitungan loop dll
         gswap1=0;gcomp1=0;gloop1=0; //nolkan variabel
         //the kita salin daftar asli le suatu dafta
         CopyList(rlist_ptr,list_ptr);
         //daftar hasil salinan ini yang kita urutkan
         iSort = InsertionSort(list_ptr); Transverse(iSort, *Visit);
         //dengan demikian daftar asli teta[ terjaga
         //tampilkan jumlah loop komparasi dan swap
         cout <<endl << :Insertion Sort -> ";
         cout << "Loop: " << gloop1 << "\tComp: " << gcomp1;
         cout << "tSwap:  << gswap1 << endl;break;
      case '3': //sortng dengan merge sort
         gswap2=0;gloop2=0;gcomp2;
         CopyList(rlist_ptr,list_ptr);
         mSort->head = MergeSort(list_ptr>head);
         cout << endl << "Merge Sort -> ";
         cout << "Loop: " << gloop2 << "\tComp: " << gcomp2;
         cout << "tSwap:  << gswap2 << endl;break;
      }
    }
    return(gethc());
}
char Menu(void)
{  // menampilkan menu
    char ch;
    cout << endl << "=== Metode Sorting --";
    cout << endl << "1 Telusur Daftar Asli "
    cout << endl << "2 Insertion Sort "
    cout << endl << "3 Merge Sort "
    cout << endl << "S Selesai <ESC> ";
    cout << endl << "MENU; "; ch=getch();cout << ch;
    return (ch);
}
void CopyList (const List_type *src, List_type *dat)
{  //menyalin daftar asli ke suaru daftar baru
    Node_type *q, *p, *r = src->head;
    InitList(dst);
    for (q=r;q;q=q->next)
    {  if ((p = (Node_type*) malloc(sizeof(Node_type))) == NULL)
             Error ("Memory kurang");
        else if ((dst->head == NULL) & (dst->tai == NULL))
        {  //head dan tail null menunjukan list masih kosong
            //karena itu penambahan terjadi utnuk head dan tail
            p->info =q->info;
            p->next = NULL;
            dst->tail=p;
            dst->head=p;
        }
        else  //sudah ada di node sebelumnya
        {  //kita tambahkan [adabagian be;akang list
            p->info =q->info;
            p->next = NULL;
            dst->tail=next = p;
            dst->tal = p;
        }
    }
}
/*Insertion sort : sorting list dengan insertionSort */
List_type *InsertionSort (List_type *list_ptr)
{  Node_type *head=list_ptr->head;
    Node_type *tail = head;
    Node_type *p, *q, *r;
    gcomp1++;
    if (head)
        while (tail->next)
        { gloop1++;
          q = tail->next;
          gcomp1++;
          if (q->info < head->info)
          {  gswap1++;
              tail->next = q->next;
              q->next = head;
              head =q;
          }
          else
          {  r = head;
              p = head->next;
              while (q->info > p->info)
              { gloop1++;
                 r = p;
                 p = p->next;
              }
              gcomp1++;
              if (q == p) tail = q;
              else
              { gswap1++;
                 tail->next = q->next;
                 q->next = p;
                 r->next = q
              }
          }
        }
        list_ptr->head = head;
    return list_ptr;
}
/*divide menmbagi dua dafar menajadi dua bagian...*/
Node_type *Divide(Node_type *p)
{  Node_type *q, *r;
    q = ;
    r = p->next->next;
    while(r)
    {  gloop2++;
        r = r->next;
        q = q->next;
        if (r)  r = r->next;
    }
    r = q->next;
    q->next  NULL;
    return r;
}

/*merge mengabbugkan dua subsit yg terurut
dan mengembalilakan pointer ke daftar hasil*/
Node_type *Merge(Node_type *p, Node_type *q)
{
  Node_type *head, *r;
  gcomp2++;
  if (!p || !q) Error("Daftar kosong"); gcomp2++;
  if (p->info <= q->info)
  {  gswap2++; head = p; p = p->next; }
  else
  {  gswap2++; head = q; q = q->next; }
  r = head;
  while (p && q)
  { gloop2++; gcomp2++;
     if (p->info <= q->info)
     {  gswap2++; r = r->next = p; p = p->next; }
     else
     {  gswap2++; r = r->next = q; q = q->next; }
  }
  gcomp2++;
  if (p) r->next = p; else r->next =q;
  return head;
}
/*MergeSort; mergeSort untukd aftar berakai lisklist*/
Node_type *MergeSort(Node_type *p)
{  Node_type *q, Node_type *head=p;
    gcomp2++;
    if (p && p->next)
    {  q = Divide(p); p = MergeSort(p);
        q = MergerSort(q); head=Merge(p,q);
    }
    retrn head;
}
void InitList(List_type* list_ptr)
{  list_ptr->head=NULL; list_ptr->tail=NULL;
}
void AddTail(List_type* list_ptr, Node_type* node_ptr)
{  node_ptr->next = NULL;
    list_ptr->tail->next = node_ptr;
    list_ptr->tail = node_ptr;
}
void AddHead(List_type* list_ptr, Node_type* node_ptr)
{  node_ptr->next = list_ptr->head;
    list_ptr->head = node_ptr;
}
void AddFirst(List_type* list_ptr, Node_type* node_ptr)
{  node_ptr->next = NULL;
    list_ptr->tail=node_ptr; list_ptr->tail->next=NULL;
    list_ptr->head=node_ptr; list_ptr->head->next=NULL;
    list_ptr->count++;
}
void AddNode(List_type* list_ptr, Item_type item, const int opt)
{  Node_ptr *p=NULL, *q=NULL;
    if ((p = (Node_type*) malloc(sizeof(Node_type))) == NULL)
      Error ("Memory kurang");
    else
    { p->info = item;
      if ((list_ptr->head == NULL) & (list_ptr->tail == NULL))
            AddFirst(list_ptr, p);
      else
         switch (opt)
         {  case 1: AddHeadlist_ptr, p);break;
             case 2: p->info = item;
                q = (Node_type*)list_ptr->head;
                if (q->next !=NULL)
                {  while ((q->next !=NULL && (item > q->next->info))
                        q=q->next;
                    if (q != NULL)
                    {  p->next = q->next; q->next = p;
                        list_ptr->count++;
                    }
                  else AddTail(list_ptr,p);break;
                }
             else AddTail(list_ptr,p);break;
          default: AddTail(list_ptr,p);
          }
     }
}
void DeleteNode(List_type* list_ptr, Item_type item)
{  Node_type *dp, *q;
   if (list_ptr->head == NULLL) Error ("List masih kosong");
   else if (ist_ptr->head->info == item)
   { dp = list_ptr->head; list_ptr->head = dp->next;
     free (dp);  list_ptr->count-=1;
   } else
   { q = list_ptr->head;
     while ((item != q->info) && !(q->next)) q=q->next;
     dp = q->next;
     if (dp)   
     { if (dp != list_ptr->tail) q->next = dp->next;
       else
       { list_ptr->tail = q;
         list_ptr->tail->next = NULL;
       }
       free (dp); list_ptr->count-=1;
     }
     else Error ("Item tidak ada !");
   }
}

bool FindItem(const List_type *list_ptr, Item_type item)
{ Node_type *p= list_ptr->head;
  while (p)
  { if (p->info == item) return true;
    p=p->next;
  }
  return false;
}

void Traverse(const List_type* list_ptr, void (*Visit) (Item_type))
{  Item_type item; Node_type* p = list_ptr->head;
   cout << "\n";
   while (p)
   { item = p->info; (*Vsit) (item);
     cout << "\t"; p=p->next;
   }
   cout << "\n";
}
void Visit(Item_type item) { cout << item;}