9 Replies Latest reply: Nov 6, 2007 10:18 PM by 807603 RSS

    Selection Sort Algorithm

    807603
      I'm trying to implement a selection sort method with linked lists, but I just can't seem to get it to work correctly.
       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() != null) {
                      current = pointer;
                      exchangeMade = false;
                      iterationsOUTER++;
                      while (current.getNext() != null && !exchangeMade) {
                          if(current.getNext().getData() < current.getData()) {
                              int temp = current.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);
              }
          }
      If I test it with this 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();
      I get this as my output...
      8
      13
      1
      2
      29
      5
      30
      30
        • 1. Re: Selection Sort Algorithm
          807603
          That would be a bubble sort not a selection sort.
          • 2. Re: Selection Sort Algorithm
            807603
            Please clarify one thing for me:

            Is the Node class, something you made, or is it in the Java class library (there's quite a few named Node in there)? let me know....


            also, the LinkedList class has a generic type attached to it. Meaning you can store any data type in the LinkedList, but you have to specify what you want.

            example:
            LinkedList<String> strings = new LinkedList<String>();
            since the list is a parameter you don't have to initialize it, however you still need to specify what data type you're dealing with. I'd use "LinkedList<Object>" if you're not sure what type a user of this method may select, but it looks like you're gonna want to use "LinkedList<Node>".
            • 3. Re: Selection Sort Algorithm
              807603
              after I re-read your question, and saw you got some output; i guess you don't have to specify a parameterized type, but it's probably a good practice to do so.

              Edited by: art on Nov 7, 2007 3:00 AM
              • 4. Re: Selection Sort Algorithm
                807603
                Sorry...the LinkedList and Node classes were custom classes. Node takes an int as a parameter.

                Ah...I knew that didn't look correct. I've already written a BubbleSort method, and I thought I had read the algorithm for the SelectionSort right...but apparently not.
                • 5. Re: Selection Sort Algorithm
                  807603
                  selection sort is an n^2 algorithm so that's how many iterations you should have.

                  (i think)

                  and btw:
                  that looks like a selection sort algorithm to me, but you don't need the boolean variable in there.

                  Edited by: art on Nov 7, 2007 3:48 AM

                  Edited by: art on Nov 7, 2007 3:52 AM
                  • 6. Re: Selection Sort Algorithm
                    807603
                    that looks like a selection sort algorithm to me
                    OP is comparing next node with current node and if next node is less than current node, swap them. Sounds like a bubble sort to me!
                    • 7. Re: Selection Sort Algorithm
                      807603
                      Maybe I'm not positive on how a selection sort is supposed to work. Does it pick the smallest element in the list, puts it in the first slot, finds the seconds smallest element in the list and puts it in the second slot...and so on? I thought I was doing this by finding placing it into "position" and looping through the list with "current" to find the smallest element in the linked list.
                      • 8. Re: Selection Sort Algorithm
                        807603
                        Yes that is how selection sort should work but you are only comparing 2 nodes at a time and swapping them. That is a bubble sort. Read this:

                        http://en.wikipedia.org/wiki/Selection_sort
                        • 9. Re: Selection Sort Algorithm
                          807603
                          yes, you're both correct. (i didn't read it correctly, flounder...it's been a long day)

                          hehe...yeah, i checked out the wiki to see if i was thinking of the right thing.

                          so, is this for a school project or just personal stuff?

                          cause you may want to look into the merge sort for sorting LinkedLists. (or just use Collections.sort(list)...check out the API).

                          -----
                          for the implementation you have above, you'll need to have a temp list that keeps getting shorter with each "outer" iteration...

                          Edited by: art on Nov 7, 2007 4:07 AM

                          Edited by: art on Nov 7, 2007 4:16 AM