10 Replies Latest reply: Dec 3, 2007 11:11 PM by 807603 RSS

    Selection Sort using Linked Lists

    807603
      As the subject says, I'm trying to implement a selection sort method on a linked list structure. I've already created a bubble sort, but I can't seem to get this method to work correctly. The Node and LinkedList classes were written by me, and I know they work correctly (because of the other methods work right).
      public void selectionSort(LinkedList list) {
              int iterationsINNER = 1, iterationsOUTER = 1, swaps = 0, comparisons = 1;
              if(list.isEmpty())
                  System.out.println("List is currently empty.");
              else if (list.size() == 1)
                  System.out.println("List is already sorted.");
              else {
                  Node pointer = list.getFirst();
                  Node current;
                  boolean exchangeMade;
                  while (pointer.getNext().getNext() != null) {
                      current = pointer;
                      exchangeMade = false;
                      iterationsOUTER++;
                      while (current.getNext() != null && !exchangeMade) {
                          if(current.getNext().getData() < pointer.getData()) {
                              int temp = pointer.getData();
                              pointer.setData(current.getNext().getData());
                              current.getNext().setData(temp);
                              exchangeMade = true;
                              iterationsINNER++;
                              swaps++;
                              comparisons++;
                          }
                          current = current.getNext();
                      }
                      pointer = pointer.getNext();
                  }
                //  System.out.println("Comparisons: " + comparisons + " \nSwaps: " + swaps + " \nIterations: " + iterationsINNER+iterationsOUTER);
              }
          }
      For instance, if I run this bit of code...
      LinkedList list = new LinkedList();
              list.insert(5);
              list.insert(29);
              list.insert(2);
              list.insert(1);
              list.insert(13);
              list.insert(8);
              list.insert(30);
              list.insert(3);
              sort.selectionSort(list);
              list.print();
      The output is...
      1
      8
      13
      3
      2
      29
      30
      5

      Anyone have any idea what is going wrong, or is anymore information needed?

      PS: I also need to create a insertion sort method with this, and I've been told I need to reverse the list for the insertion sort to work correctly. Any tips on how to implement this method too? :)
        • 1. Re: Selection Sort using Linked Lists
          807603
          procedure bubbleSort( A : list of sortable items ) defined as:
            do
              swapped := false
              for each i in 0 to length( A ) - 2 do:
                if A[ i ] > A[ i + 1 ] then
                  swap( A[ i ], A[ i + 1 ] )
                  swapped := true
                end if
              end for
            while swapped
          end procedure
          That is bubble sort.
          Your code doesn't seem to loop while there are still operations...
          • 2. Re: Selection Sort using Linked Lists
            807603
            Wait...the code above is a bubble sort? Hmm...well I thought that I was doing it right when I was comparing the pointer node to each other node until I found one with smaller data (or not find one). Is that not what's it's doing?
            • 3. Re: Selection Sort using Linked Lists
              807603
              Would someone please explain? I've looked at the selection sort algorithm, and I thought I was working it right. What exactly is wrong?

              PS: And for the insertion sort, do I need to create an extra list to store the sorted data in, or do you sort it in the same list?
              • 4. Re: Selection Sort using Linked Lists
                807603
                You are supposed to find the smallest value of all unsorted entries and swap that with the element you are currently looking at.
                But you are actually getting the first entry wich is smaller than the current and swap those.

                And from that line
                while (pointer.getNext().getNext() != null)
                I'd guess you get a NullPointerException for a list of size two.
                • 5. Re: Selection Sort using Linked Lists
                  807603
                  I've changed it up a bit, and it works, but is this still a bubble sort? I've tried uncommenting that section that keeps track of the iterations and such, but I know they can't be right. Does this look correct? I basically just removed that boolean check...
                  public void selectionSort(LinkedList list) {
                          int iterationsINNER = 1, iterationsOUTER = 1, swaps = 0, comparisons = 1;
                          if(list.isEmpty())
                              System.out.println("List is currently empty.");
                          else if (list.size() == 1)
                              System.out.println("List is already sorted.");
                          else {
                              Node pointer = list.getFirst();
                              Node current;
                              while (pointer.getNext() != null) {
                                  current = pointer;
                                  iterationsOUTER++;
                                  while (current.getNext() != null) {
                                      comparisons++;
                                      if(current.getNext().getData() < pointer.getData()) {
                                          int temp = pointer.getData();
                                          pointer.setData(current.getNext().getData());
                                          current.getNext().setData(temp);
                                          iterationsINNER++;
                                          swaps++;
                                      }
                                      current = current.getNext();
                                  }
                                  pointer = pointer.getNext();
                              }
                              System.out.println("Comparisons: " + comparisons + " \nSwaps: " + swaps + " \nIterations: " + iterationsINNER+iterationsOUTER);
                          }
                      }
                  And no, I tried and I don't get a NullPointerException if I have a list of 2.

                  Edited by: birdboy30 on Dec 3, 2007 7:23 PM
                  • 6. Re: Selection Sort using Linked Lists
                    807603
                    And no, I tried and I don't get a NullPointerException if I have a list of 2.
                    Sorry, my fault.

                    But you should find the smallest entry once.
                    Instead of swapping everytime you find a smaller entry, remember the node that contained the smallest entry and swap after you are finished with your inner while loop.

                    *(edit)*
                    You can look for an example at
                    http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/selectionSort.htm

                    That should make clear what I mean to say.

                    And
                    http://en.wikipedia.org/wiki/Insertion_sort
                    shows that you don't need an extra list.

                    Edited by: Theophrast on Dec 4, 2007 3:31 AM
                    • 7. Re: Selection Sort using Linked Lists
                      807603
                      Well...I tried to not swap each time and came up with this.
                      public void selectionSort(LinkedList list) {
                              int iterationsINNER = 1, iterationsOUTER = 1, swaps = 0, comparisons = 1;
                              if(list.isEmpty())
                                  System.out.println("List is currently empty.");
                              else if (list.size() == 1)
                                  System.out.println("List is already sorted.");
                              else {
                                  Node pointer = list.getFirst();
                                  Node current;
                                  boolean swapMade = false;
                                  int temp = 0;
                                  while (pointer.getNext() != null) {
                                      current = pointer;
                                      iterationsOUTER++;
                                      while (current.getNext() != null) {
                                          comparisons++;
                                          if(current.getNext().getData() < pointer.getData()) {
                                              temp = pointer.getData();
                                              swapMade = true;
                                          }
                                          current = current.getNext();
                                      }
                                      if(swapMade) {
                                          pointer.setData(current.getData());
                                          current.setData(temp);
                                      }
                                      pointer = pointer.getNext();
                                  }
                                  System.out.println("Comparisons: " + comparisons + " \nSwaps: " + swaps + " \nIterations: " + iterationsINNER+iterationsOUTER);
                              }
                          }
                      It doesn't work right, but is that the idea? Sort of...?
                      • 8. Re: Selection Sort using Linked Lists
                        807603
                        You are going the right direction.
                        But you are only storing the value of the smallest entry, not the node.

                        You could do it by initializing the smallest node before the inner loop
                        Node smallest = current;
                        and keep updating it, so you can swap current node and the smallest node (if they are not the same)

                        *(edit)*
                        I don't know your assignment, but currently you always swap the data of the nodes.
                        Since you have to do this with a linked list, you might have to update the pointers to do the swapping

                        node1 -> node2 -> node3
                        swap node2 and node3:
                        node2 is then pointing to null (where node3 was pointing to) and
                        node3 is pointing to node2
                        node1 is pointing to node3

                        So you would have
                        node1 -> node3 -> node2
                        after a swap.

                        Also, Wikipedia mentions a slightly modified version for a linked list.
                        http://en.wikipedia.org/wiki/Selection_sort

                        Have you had a look at this?

                        Edited by: Theophrast on Dec 4, 2007 4:00 AM
                        • 9. Re: Selection Sort using Linked Lists
                          807603
                          I have looked at it. And it is for an assignment. Here's a link for it if you would like to look, http://cs.uscupstate.edu/public/SCSC321/Assignments/Assignment2F07.doc
                          I thought it would be much easier to swap the data instead the entire node. Wouldn't that be much more work?
                          • 10. Re: Selection Sort using Linked Lists
                            807603
                            I'd say it tells you to implement a method swap for the linked list. Although it says "data swaps" my guess still would be that you have to manipulate the pointers.
                            On the other hand, it doesn't tell you to implement a linked list with forward and backward pointers, and without pointers to the previous element swapping by manipulating pointers would impair performance.
                            Wouldn't that be much more work?
                            "much" is relative, for you it's now probably about whether you have a doubly linked list or a singly linked list.

                            Do as you please, I can only guess and don't know what you were told in class and the assignment is too vague to say for sure.

                            If you implement a swap method in your LinkedList, taking two Nodes as parameters, you could now go by swapping the data and always decide later to implement it by manipulating pointers.