1
\$\begingroup\$

I was trying another approach of sorting a linked list. Aside from the available methods, I've decided to take each node from the linked list and place it into an array. With that, I would be able to compare the data variables easily. I applied quickSort() on the array, and this is what I have. I would appreciate any feedback/comments on my code.

    public static void main(String[] args) {


        MyLinkedList list = new MyLinkedList();

        Student s = new Student(1, "John", 20, "Italy", "2011");
        list.addStudent(s);
        Student s2 = new Student(2, "Mark", 19, "UAE", "2010");
        list.addStudent(s2);
        Student s3 = new Student(3, "Sally", 35, "UAE", "2000");
        list.addStudent(s3);

        System.out.println("Students in the list: ");
        list.print();

        Node[] n = list.convertA(list);
        quickSort(n, 0, (n.length-1));
        System.out.println("Sorted list is:");

        for(int q =0;q<n.length;q++){
            System.out.println(n[q] + " ");
        }
    }

    public static int partition(Node arr[], int left, int right) {

        int i = left, j = right;

        Node tmp;

        Node pivot = arr[(left + right) / 2];

        while (i <= j) {

            while (arr[i].getStudent().getAge() < pivot.getStudent().getAge()) {
                i++;
            }

            while (arr[j].getStudent().getAge() > pivot.getStudent().getAge()) {
                j--;
            }

            if (i <= j) {

                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;

            }

        }
        return i;

    }

    public static void quickSort(Node arr[], int left, int right) {

        int index = partition(arr, left, right-1);

        if (left < index - 1) {
            quickSort(arr, left, index - 1);
        }

        if (index < right) {
            quickSort(arr, index, right);
        }
    }
\$\endgroup\$
1
\$\begingroup\$

First of all I don't know why are you trying to reinvent the wheel? Java has a strong and beautiful API with many methods and there is also a method for sorting an custom array. Which is more faster than quicksort. However I think this is for your own practice.

  • Your convertA method is not good, cause you are passing the reference as argument as well. So either make the method static or use the existing method toArray().
  • You are converting a student list to an Node array, why? change Node array to Student array. So this

    arr[i].getStudent().getAge()
    

    will change to

    arr[i].getAge() 
    
  • there is a possible bug you are calculating (left + right) / 2 which may cause an overflow, though Java int range is very big you will face the overflow very rarely, but if you want to fix this; change to (right - left) / 2 + left.

Check How Other Have Done The Quicksort :

From CodeReview 1

From CodeReview 2

Why you should use the API method?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.