0

I'm needing to be able to sort an Array Class that I've created that holds over 300,000 or even sometimes 1,000,000 results on an Android Phone.

However I want it to be quicker so I have been looking into possible options such as a Merge Sort or a parallel sort, but these are mostly dealing with arrays with just integers in a single line (from left to right) in order to sort.

Here is an example of my currently Array Class...

public class ClassSearchResults {

        private int rowID;
        private String TitleHREF;
        private String ImageSRC;
        private String Title;
        private int Price;



        public int getRowID() {
            return rowID;
        }
        public void setRowID(int rowID) {
            this.rowID = rowID;
        }

        public String getTitleHREF() {
            return TitleHREF;
        }
        public void setTitleHREF(String TitleHREF) {
            this.TitleHREF = TitleHREF;
        }

        public String getImageSRC() {
            return ImageSRC;
        }
        public void setImageSRC(String ImageSRC) {
            this.ImageSRC = ImageSRC;
        }

        public String getTitle() {
            return Title;
        }
        public void setTitle(String Title) {
            this.Title = Title;
        }
        public int getPrice() {
        return Price;
        }
        public void setPrice(int Price) {
        this.Price = Price;
        }

Now I am wanting to be able to sort this by the getPrice field of course. The methods I have tried are doing a regular Comparitor / Collections.sort but after sooo many records this seems to be very very slow overall and I run into out of memory issues.

Is there any better ways of doing this? Should I even be using an array class or should I be using something else?

Should I just create a local SQL Database and throw the results in there first then sort and output?

I'm looking for the BEST, FASTEST, and most Stable way of doing this. Keep in mind that we are looking for OVERALL speed for Inserting/Cataloging the Result, then Sorting the Result, then Outputing it in a system.out.println or some type of simple output.

If I should be using a whole different data structure, what should I be using?

eqiz
  • 1,521
  • 5
  • 29
  • 51
  • "...Merge Sort or a parallel sort, but these are mostly dealing with arrays with just integers in a single line (from left to right) in order to sort..." How is your case different than that? – gkrls Dec 10 '14 at 01:34
  • From what I know, or i could be completely wrong. My Array Class is considered top-down since you have a row of results equal to a specific integer (or index) and they are seen as a "table" results. While a left-right array comparison is just comparing the value that is left and right of a specific row of arrays (for example Array[0][1] Compared to Array[0][2]) – eqiz Dec 10 '14 at 01:48
  • 1
    I don't think i completely understand your previous commend but anyway ArrayLists are implimented using Arrays. i.e the sorting does happen on Arrays eventually. Furthermore u said you tried merge sort. Merge sort gives a complexity of O(n log n). Collections.sort() in fact does use MergeSort but with a twist. So i think that's your best bet. Apart from that maybe you should consider using a different data structure. – gkrls Dec 10 '14 at 02:03
  • I second the suggestion for a different datastructure. You most def want something like a tree. Maybe even a balanced one. – Fildor Dec 10 '14 at 06:24
  • What type of data structure would you suggest? I neglected to mention this is all done on an Android Phone using Java, so the data structures I am able to use are somewhat limited, but I'm open to ideas. The Collections.sort() takes too long and uses too much memory.. I run out of memory when trying to deal with over a million records. – eqiz Dec 10 '14 at 22:53
  • 1
    You cannot possibly show a user over a million records, so why sort them all at once? The best solution may not be changing the data structure but to rethink the strategy of limiting the data for sort. Just my 2 cents. – display name Dec 10 '14 at 23:01
  • I can't do that really either.. Let me put it into perspective. I'm pulling data from over 3,000 - 9,000 different sources and each source has between 20 - 100 items per each one. These have to be sorted and then displayed. Now I don't need to display 1 million results, but they do have to be sorted so I can show the sorted first 5,000 or so records. Make sense? – eqiz Dec 10 '14 at 23:03
  • 1
    https://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/list/TreeList.html for example provides a sorted list that sorts on adding elements. Another approach would be using Collections.Sorts() after each add (and parallel to your look up of the next few hundred elements). If both cases are to memory costly, use sqlite or try a custom implemented data structure – Christian R. Dec 11 '14 at 02:42
  • 1
    Sorry, wrong link,http://stackoverflow.com/questions/416266/sorted-collection-in-java should help – Christian R. Dec 11 '14 at 02:49

1 Answers1

0

https://github.com/KenPowers/Multi-Threaded-In-Place-QuickSort/blob/master/src/main/java/net/kenpowers/projects/quicksort/Sorter.java

I found this and its way faster than a Collections.Sort or a Array.Sort so just wanted to share that information.

eqiz
  • 1,521
  • 5
  • 29
  • 51