0

I have an ArrayList<Node>, where a Node class is 

public Node{

String key; 
int x;} .

I want to sort this ArrayList in descending order of x, as in high to low, without importing any other statement besides 

import java.util.*;

I've looked online and everyone is saying to use the Collections.sort method. However, I cannot use that and want to learn how to sort an ArrayList without using it.

AbhishekSaha
  • 705
  • 3
  • 9
  • 24
  • 3
    Implement a sort method like [Bubble Sort](http://en.wikipedia.org/wiki/Bubble_sort), [Merge Sort](http://en.wikipedia.org/wiki/Merge_sort) or [Quick Sort](http://en.wikipedia.org/wiki/Quicksort). – Luiggi Mendoza Nov 19 '13 at 21:21
  • Collections.sort won't work! –  Nov 19 '13 at 21:21
  • possible duplicate of [How to sort a List alphabetically using Object name field](http://stackoverflow.com/questions/8432581/how-to-sort-a-listobject-alphabetically-using-object-name-field) – JB Nizet Nov 19 '13 at 21:21
  • 1
    Why couldn't you use that? Collections and Comparator are under java.util. So you may use them. – JB Nizet Nov 19 '13 at 21:22
  • 1
    @RouteMapper be careful when reading the question: *I've looked online and everyone is saying to use the Collections.sort method. **However, I cannot use that***. – Luiggi Mendoza Nov 19 '13 at 21:22
  • Make your own sort. Insertion is the easiest to make but painfully slow. – Neil Locketz Nov 19 '13 at 21:23
  • @JBNizet this question looks like homework exercise for an algorithm course... – Luiggi Mendoza Nov 19 '13 at 21:23
  • @LuiggiMendoza: or not. To me, it looks like the teacher helps them by making them look for a solution in java.util, and not in any of the other gazillions of Java packages. – JB Nizet Nov 19 '13 at 21:24
  • @JBNizet well then, assuming OP cannot use `Collections#sort`, he/she may still use a `TreeSet` and let this structure do the sorting for him/her. Of course, this is not the path I would follow when `Collections#sort` is already optimized for this use case. – Luiggi Mendoza Nov 19 '13 at 21:26
  • 1
    @LuiggiMendoza certainly, if Corrections#sort is forbidden, then using anything else built in is, likely implied to be off-limits. – Cruncher Nov 19 '13 at 21:27
  • 1
    You are being asked to implement your own sort. Presumably this was covered in the course material and lectures. If you still do not know what to do then you should talk to your professor and/or teaching assistant. – Jim Garrison Nov 19 '13 at 21:33
  • Here's an old question regarding an implementation of Merge Sort using `List` (regardless the class implementation): http://stackoverflow.com/q/15579425/1065197. – Luiggi Mendoza Nov 19 '13 at 22:24

2 Answers2

1

You should use own implemented sorting method. For this you also need to learn ArryList class methods for swaping values. You'll have to use get(int) and set(int, E) extensively to swap elements.

I am showing you one solution that I like to do when Collections.Sort is not feasible. In this I am using "Bubble Sort" sorting method. I hope you are aware from "Bubble Sort".. package online.solution;

import java.util.ArrayList;

public class Node {
    private String key;
    private int x;

    public Node(String key, int x) {
        this.key = key;
        this.x = x;
    }

    public int getX() {
        return x;
    }

    public static void main(String[] args) {
        Node n1 = new Node("B", 14);
        Node n2 = new Node("H", 7);
        Node n3 = new Node("U", 13);
        Node n4 = new Node("S", 1);
        Node n5 = new Node("H", 88);
        Node n6 = new Node("A", 99);
        Node n7 = new Node("N", 12);

        ArrayList<Node> nodes = new ArrayList<>();
        nodes.add(n1);
        nodes.add(n2);
        nodes.add(n3);
        nodes.add(n4);
        nodes.add(n5);
        nodes.add(n6);
        nodes.add(n7);

        System.out.println("Before sorting...");
        for (Node node : nodes) {
            System.out.println(node.getX());
        }

        int n, i, j;

        Node swap;
        n = nodes.size();

        for (i = 0; i < (n - 1); i++) {
            for (j = 0; j < n - i - 1; j++) {
                if (nodes.get(j).getX() > nodes.get(j + 1).getX()) {
                    swap = nodes.get(j);
                    nodes.set(j, nodes.get(j + 1));
                    nodes.set(j + 1, swap);
                }
            }
        }

        System.out.println("After sorting in Ascending Order...");
        for (Node node : nodes) {
            System.out.println(node.getX());
        }

        for (i = 0; i < (n - 1); i++) {
            for (j = 0; j < (n - i - 1); j++) {
                if (nodes.get(j).getX() < nodes.get(j + 1).getX()) {
                    swap = nodes.get(j);
                    nodes.set(j, nodes.get(j + 1));
                    nodes.set(j + 1, swap);
                }
            }
        }

        System.out.println("After sorting in Descending Order ...");
        for (Node node : nodes) {
            System.out.println(node.getX());
        }
    }
}

I hope this solution help you in your work...

enter image description here

Bhushankumar Lilapara
  • 780
  • 1
  • 13
  • 26
-1

If you are unable to use Collections.sort then you're going to have to write your own sorting algorithm. Insertion sort, and selection sort are probably the easiest to implement

When you have an ArrayList of Nodes, you compare 2 indices i and j as follows: nodes.get(i).x > nodes.get(j).x. The rest of the details on sorting will depend on which algorithm you pick.

Cruncher
  • 7,641
  • 1
  • 31
  • 65