Implementing Selection Sort in Java

Question

I did this sort function in C++ for Linked List

void sort()
{
    node* ctr;
    node* innerctr;
    info temp;
    node* max;
    ctr = start;
    while(ctr!=NULL)
    {
        innerctr=ctr->next;
        max=ctr;
            while(innerctr!=NULL)
            {

                if((innerctr->student.name) > (max->student.name))
                {
                    max=innerctr;

                }


                innerctr=innerctr->next;


            }

            //swapping...


        ctr=ctr->next;
    }
}

I need to do something similar in Java and I want to use the LinkedList ready class but I am a bit confused because there are no pointers.

"There are no pointers" is a sketchy statement, especially fun are NullPointerExceptions. — cohensh
– cohensh, Commented Apr 12, 2011 at 22:43

Frans · Accepted Answer · 2011-04-12 22:55:34Z

1

Check java.util.Collections.sort. There's no need to implement sorting and such in Java, it's all in the JDK.

answered Apr 12, 2011 at 22:55

Frans

4,0521 gold badge33 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Peter Lawrey Over a year ago

@Ahmed, sometimes the best lesson is when not to re-invent the wheel. ;)

Ahmed Over a year ago

You need to know the wheel first.

user unknown · Accepted Answer · 2011-04-12 23:30:32Z

With as few modifications as possible, nearly the same thing in Java:

class Student {String name = "Joe Doe";}
class Node {
    Node next;
    Student student;
}
class Info {}
public class NodeSorter {

    Node start; 

    void sort()
    {
        Node ctr;
        Node innerctr;
        Info temp;
        Node max;
        ctr = start;

        while (ctr != null)
        {
            innerctr = ctr.next;
            max=ctr;

            while (innerctr != null)
            {
                if ((innerctr.student.name).compareTo (max.student.name) > 0)
                {
                    max = innerctr;
                }
                innerctr=innerctr.next;
            }
            //swapping...
            ctr = ctr.next;
        }
    }
}

some dummy classes (Student, Info)
Node would normally be generic, not fixed to Student.
classnames with Capitals.
methods and attributes are just delimited with dot
comparision with compareTo (for non-numbers)

And here is the improved version, with Type "Student" as parameter for the Node:

class Student implements Comparable <Student> {
    String name = "Joe Doe";
    public int compareTo (Student other) {
        if (other == null) return 1;
        return name.compareTo (other.name);
    }   
}
class Node <T> {
    Node <T> next;
    T value;
}
class Info {}
public class NodeSorter {

    Node <Comparable> start;    

    void sort ()
    {
        Node <Comparable> ctr;
        Node <Comparable> innerctr;
        Info temp;
        Node <Comparable> max;
        ctr = start;

        while (ctr != null)
        {
            innerctr = ctr.next;
            max=ctr;

            while (innerctr != null)
            {
                if ((innerctr.value).compareTo (max.value) > 0)
                {
                    max = innerctr;
                }
                innerctr=innerctr.next;
            }
            //swapping...
            ctr = ctr.next;
        }
    }
}

The problem with the unspecified 'start' is inherited from you.

lukastymo · Accepted Answer · 2011-04-12 22:51:38Z

I don't know what means > for name in your example
Below code uses selecting min index not max index like in your case - so you should change a bit this solution. But idea is still the same

source from this site

public static void selectionSort2(int[] x) {
    for (int i=0; i<x.length-1; i++) {
        int minIndex = i;      // Index of smallest remaining value.
        for (int j=i+1; j<x.length; j++) {
            if (x[minIndex] > x[j]) {
                minIndex = j;  // Remember index of new minimum
            }
        }
        if (minIndex != i) { 
            //...  Exchange current element with smallest remaining.
            int temp = x[i];
            x[i] = x[minIndex];
            x[minIndex] = temp;
        }
    }
}

Collectives™ on Stack Overflow

Implementing Selection Sort in Java

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related