Results 1 to 1 of 1
  1. #1
    wfsteadman is offline Member
    Join Date
    Jan 2013
    Location
    Texas
    Posts
    45
    Rep Power
    0

    Default Adding Counts to a mergesort

    Greetings all,
    So i have created a merge sort application that will take x number of list elements containing random integer values and will sort them in proper order. What I am trying to figure out now is where is the best place in the code to count the steps to do such a sort so that I could in essence get the number of comparison needed to fully sort the list. I am trying to do comparisons of both the merge sort and quick sort to numerically validate but have added the list for my mergesort code here to get assistance. I know it is good to count on while loops and for loops but is there a definitive location to count steps in the process? I have always struggled with where to count comparisons and with the more complex algorithm's I get even further confused because there are many different steps that I can count. I have attached a copy of my program here and I put some static variables and counts where I think they may go, but would really like some advice from the experts out here.

    class MSNode
    Java Code:
    package MergeSortComparison;
    
    public class MSNode 
    {
        private int number;
        public MSNode next;
        public MSNode prev;
    
        public int getNumber() {
            return number;
        }
    
        public void setNumber(int number) {
            this.number = number;
        }
        
        public String display()
        {
        return number+"";
        }
        
    }
    class MergeSortApp
    Java Code:
    package MergeSortComparison;
    import java.util.Random;
    
    public class MergeSortApp {
    
    
        public static void main(String[] args) {
            Random rnd = new Random();
            MSNode myList = new MSNode();
            myList.setNumber(rnd.nextInt(500));
            int maxSize = 5000;
            
            MergeSortClass mSort = new MergeSortClass(myList);
            
            for(int i = 0; i < maxSize; i++)
            {
                int temp = rnd.nextInt(10000);
                MSNode node = new MSNode();
                node.setNumber(temp);
                mSort.insertBack(myList, node);
            }
    
            System.out.println("Print before sort");
            MSNode tempList = myList;
            while(tempList != null)
            {
                System.out.println(tempList.display());
                tempList = tempList.next;
            }
            
            myList = mSort.startSort();
            
            System.out.println("After Sort");
            tempList = myList;
            while(tempList != null)
            {
                System.out.println(tempList.display());
                tempList = tempList.next;
            }
            
            System.out.println("Total Count " + mSort.getTotalCount());
       }
    }
    class MergeSortClass
    Java Code:
    package MergeSortComparison;
    
    public class MergeSortClass {
    
        private MSNode masterList;
        private MSNode[] darray = new MSNode[2];
        private static int oddListCt = 0;
        private static int evenListCt = 0;
        private static int removeFrontCt =0;
        private static int insertFrontCt =0;
        private static int insertBackCt = 0;
        private static int totalCount;
        
        public MergeSortClass(MSNode start) {
            masterList = start;
        }
    
        public MSNode[] removeFront(MSNode list) {
            MSNode temp;
            MSNode[] dar = new MSNode[2];
            temp = list;
            list = list.next;
    
            temp.next = null;
            temp.prev = null;
    
            if (list != null) {
                list.prev = null;
            }
    
            dar[0] = temp;
            dar[1] = list;
            return dar;
        }
    
        public MSNode insertFront(MSNode list, MSNode item) {
            if (list != null) {
                list.prev = item;
                item.next = list;
            }
            return item;
        }
    
        public MSNode insertBack(MSNode list, MSNode item) {
            MSNode temp;
    
            if (list != null) {
                temp = list;
                while (temp.next != null) {
                    temp = temp.next;
                }
    
                temp.next = item;
                item.prev = temp;
            } else {
                list = item;
            }
            return list;
        }
    
        private MSNode sort(MSNode myNode) {
            MSNode oddList = null;
            MSNode evenList = null;
            MSNode temp;
    
            while (myNode != null) {
                darray = removeFront(myNode);
                temp = darray[0];
                myNode = darray[1];
                oddList = insertFront(oddList, temp);
                if (myNode != null) {
                    darray = removeFront(myNode);
                    temp = darray[0];
                    myNode = darray[1];
                    evenList = insertFront(evenList, temp);
                }
    
            }
    
            if (oddList != null && oddList.next != null) {
                oddList = sort(oddList);
                
            }
            if (evenList != null && evenList.next != null) {
                evenList = sort(evenList);
                
            }
            while (oddList != null && evenList != null) {
                if (oddList.getNumber() < evenList.getNumber()) {
                    darray = removeFront(oddList);
                    temp = darray[0];
                    oddList = darray[1];
                    myNode = insertBack(myNode, temp);
                } else {
                    darray = removeFront(evenList);
                    temp = darray[0];
                    evenList = darray[1];
                    myNode = insertBack(myNode, temp);
                }
                totalCount++;
                
            }
            if (oddList == null) {
                myNode = insertBack(myNode, evenList);
                oddListCt++;
            }
            if (evenList == null) {
                myNode = insertBack(myNode, oddList);
                evenListCt++;
            }
            return myNode;
        }
        public MSNode startSort()
        {
            masterList = sort(masterList);
           return masterList;
        }
    
      public static int getOddListCt()
      {
        return oddListCt;
      }
    
      public static void setOddListCt(int oddListCt)
      {
        MergeSortClass.oddListCt = oddListCt;
      }
    
      public static int getEvenListCt()
      {
        return evenListCt;
      }
    
      public static void setEvenListCt(int evenListCt)
      {
        MergeSortClass.evenListCt = evenListCt;
      }
    
      public static int getRemoveFrontCt()
      {
        return removeFrontCt;
      }
    
      public static void setRemoveFrontCt(int removeFrontCt)
      {
        MergeSortClass.removeFrontCt = removeFrontCt;
      }
    
      public static int getInsertFrontCt()
      {
        return insertFrontCt;
      }
    
      public static void setInsertFrontCt(int insertFrontCt)
      {
        MergeSortClass.insertFrontCt = insertFrontCt;
      }
    
      public static int getInsertBackCt()
      {
        return insertBackCt;
      }
    
      public static void setInsertBackCt(int insertBackCt)
      {
        MergeSortClass.insertBackCt = insertBackCt;
      }
    
      public static int getTotalCount()
      {
        return totalCount;
      }
    
      public static void setTotalCount(int totalCount)
      {
        MergeSortClass.totalCount = totalCount;
      }
    }
    Attached Files Attached Files

Similar Threads

  1. Creating a program that counts Votes??
    By besart in forum New To Java
    Replies: 4
    Last Post: 12-06-2012, 05:57 PM
  2. Mergesort
    By pauser in forum New To Java
    Replies: 1
    Last Post: 05-09-2011, 07:33 PM
  3. mergesort recursion
    By Yakg in forum New To Java
    Replies: 13
    Last Post: 02-20-2011, 06:58 PM
  4. help with mergesort
    By desconocido in forum New To Java
    Replies: 5
    Last Post: 09-15-2010, 03:56 AM
  5. mergeSort
    By Blue_beaver in forum New To Java
    Replies: 2
    Last Post: 10-11-2009, 10:55 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •