3 Replies - 203 Views - Last Post: 02 June 2019 - 12:53 PM Rate Topic: -----

#1 jstanley6   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 53
  • Joined: 22-January 17

MergeSort method acting strange

Posted 01 June 2019 - 09:00 PM

hello, I am working on a merge sort algorithm and it has been acting weird and I am not sure why. I made it for a Circular LinkedList and it also uses a Queue as well. I will provide the methods for the mergeSort below. If you might be able to help let me know and I can provide all of it with the main so you can just make your own classes for it and test it. What happens is it works great for anything below 2000 random generated integers and sorts everything correctly but as soon as I try to generate 2000+ random integers it starts to act strange and sometimes works great and sometimes doesn't. Anything I generate from 3000+ it never works and I need to have it generate 20,000 integers and yes my processor can handle it but it doesn't seem like it wants too.

public CDoublyLinkedList mergeSort(CDoublyLinkedList l1, CDoublyLinkedList l2) throws Exception {
        CDoublyLinkedList tempList = new CDoublyLinkedList();
        while (!(l1.isEmpty()) && (!(l2.isEmpty()))) {
            if (((Comparable) l1.head.next.data).compareTo(l2.head.next.data) < 0) {
                tempList.addLast(l1.head.next.data);
                l1.removeFirst();
            } else if (((Comparable) l2.head.next.data).compareTo(l1.head.next.data) < 0) {
                tempList.addLast(l2.head.next.data);
                l2.removeFirst();
            }
        }
        while (!(l1.isEmpty())) {
            tempList.addLast(l1.head.next.data);
            l1.removeFirst();
        }
        while (!(l2.isEmpty())) {
            tempList.addLast(l2.head.next.data);
            l2.removeFirst();
        }
        this.head = tempList.head;
        this.size++;
        return tempList;
    }
 public void mergeSort() throws Exception {
        LinkedQueue queue = new LinkedQueue();
        for (Node cur = this.head.next; cur != head; cur = cur.next) {
            CDoublyLinkedList newList = new CDoublyLinkedList();
            newList.addFirst(head.next.data);
            queue.enqueue(newList);
            this.removeFirst();
        }
        CDoublyLinkedList tempList = new CDoublyLinkedList();
        while (queue.getSize() > 1) {
            CDoublyLinkedList subList1 = (CDoublyLinkedList) queue.dequeue();
            CDoublyLinkedList subList2 = (CDoublyLinkedList) queue.dequeue();
            tempList = mergeSort(subList1, subList2);
            queue.enqueue(tempList);
        }
        this.head = tempList.head;
        this.size++;
    }


Let me know if you need any other methods for it, or I can attach the files instead. it might be too many characters to put in here.

Is This A Good Question/Topic? 0
  • +

Replies To: MergeSort method acting strange

#2 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12618
  • View blog
  • Posts: 45,779
  • Joined: 27-December 08

Re: MergeSort method acting strange

Posted 01 June 2019 - 09:32 PM

Your mergeSort(CDoublyLinkedList l1, CDoublyLinkedList l2) method does not appear to recursively sort. Effectively, this method only merges the two lists. I think this is your issue.


Also, in looking at your code, I have some other suggestions to improve things. Here, you are ignoring the case in which two elements are equal. In such a case, the compareTo() method will return 0. So you can change your code here:
while (!(l1.isEmpty()) && (!(l2.isEmpty()))) {
            if (((Comparable) l1.head.next.data).compareTo(l2.head.next.data) < 0) {
                tempList.addLast(l1.head.next.data);
                l1.removeFirst();
            } else if (((Comparable) l2.head.next.data).compareTo(l1.head.next.data) < 0) {
                tempList.addLast(l2.head.next.data);
                l2.removeFirst();
            }
        }




To something like:
while (!(l1.isEmpty()) && (!(l2.isEmpty()))) {
            if (((Comparable) l1.head.next.data).compareTo(l2.head.next.data) <= 0) {
                tempList.addLast(l1.head.next.data);
                l1.removeFirst();
            } else {
                tempList.addLast(l2.head.next.data);
                l2.removeFirst();
            }
        }



Also, as a stylistic and efficiency point, it would be better to handle the comparison once before your if statements:
int comparison = ((Comparable) l1.head.next.data).compareTo(l2.head.next.data);



Then compare comparison to 0.
Was This Post Helpful? 1
  • +
  • -

#3 jstanley6   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 53
  • Joined: 22-January 17

Re: MergeSort method acting strange

Posted 02 June 2019 - 12:42 PM

oh wow, that fixed it all, I think it was because it got stuck in an infinite loop because I wasn't checking the case if they were equal and it couldn't pop out of the loop, thanks a lot!

This post has been edited by jstanley6: 02 June 2019 - 12:52 PM

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12618
  • View blog
  • Posts: 45,779
  • Joined: 27-December 08

Re: MergeSort method acting strange

Posted 02 June 2019 - 12:53 PM

Recall from the Comparable interface that the compareTo(T a, T b) method returns a negative value if a is "smaller than" b, a value of 0 if a.equals(b), and a positive value if a is "greater than" b.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1