Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Having trouble insert/sorting array values w/ binary searching.

  1. #1
    Junior Member
    Join Date
    Oct 2009
    Posts
    6
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Having trouble insert/sorting array values w/ binary searching.

    The client will be making an array and adding numbers to it. Its my job/objective to make sure that when the client passes it into the array - it is sorted in non-decreasing order.

    Note - i just finally learned about binary search and still trying to toy around with it. Have to utilize it - can't use sequential search as its resource consuming.

    So i'm basically just starting off with the client program VAGUELY - (you get the jist) - doing basic things like,
    PHP Code:
    list.add(10);
    list.
    add(9);
    list.
    add(11); 
    basically just shoving value 10,9,11 into my program.

    So, ideally - i want it the array to sort itself out. (without using array.sort)

    array - [9.10.11]

    Though i'm running into issues - i think my logic/thoughts/code in the ADD method (below) is messed. But i've hit a stump.. and honestly can't get around it... I called indexOf to use binary search to locate the index for the value, and so found that.

    Simply insert into that index? But it doesn't seem to comply.

    Might have been misunderstanding something. I got the idea.. just can't think of the right code to put it into performance.


    Took 2 quarter break from java, and decided to jump back into it for the next level class as it was a minor requirement -so my coding IS indeed flakey most definetly, so any assistance small or large would be greatly appreciated.



    PHP Code:

    import java
    .util.*;

    public class 
    SortArrayList {
        private 
    int[] elementData
        private 
    int size;          

        public static final 
    int MAX_CAP 100;

        public 
    SortArrayList() {
            
    this(MAX_CAP);
        }

        public 
    SortArrayList(int capacity) {
            
    elementData = new int[capacity];
            
    size 0;
        }

    // Use binary search to look for a requested value.
        
    public int indexOf(int value) {
         
            
    int index Arrays.binarySearch(elementData,0,sizevalue);
            return 
    index;         
         
        }



        public 
    void add(int value) {  
            
    int indexLocation indexOf(value);     // look for index of value wanted to be inserted.
                
                
                
    if(indexLocation 0) {
                    
    size++;
                    
    elementData[indexLocation] = value;
                }else{
                    
    size++;
                    
    elementData[-(indexLocation-1)] = value;
                }
        } 


  2. #2
    Super Moderator Json's Avatar
    Join Date
    Jul 2009
    Location
    Warrington, United Kingdom
    Posts
    1,274
    My Mood
    Happy
    Thanks
    70
    Thanked 156 Times in 152 Posts

    Default Re: Having trouble insert/sorting array values w/ binary searching.

    First of all you need to have a look at the binarySearch definition.

    binarySearch

    public static int binarySearch(int[] a, int key)

    Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found.
    As you can see above a binarySearch requires the array to be sorted before you can search it as using the Arrays.sort method.

    Here is a simple example using Collections.

        public static void main(String[] args) {
            final List<Integer> integers = new ArrayList<Integer>();
     
            integers.add(10);
            integers.add(9);
            integers.add(11);
     
            Collections.sort(integers, Collections.reverseOrder());
     
            System.out.println(integers);
     
            System.out.println(Collections.binarySearch(integers, 10, Collections.reverseOrder()));
        }

    // Json

  3. #3
    Junior Member
    Join Date
    Oct 2009
    Posts
    6
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Having trouble insert/sorting array values w/ binary searching.

    Ah yes - sorry my writeup in original post was bad.

    I need to do Binary Insert Sorting.

    Which - I fully realized I've done wrong and going to rewrite my add method.


    Basically the array starts out empty (thus sorted?)

    i've been misunderstanding the concept - so going to redo it and see if i can get it off the ground.

    But basically - my issue was with binary Insert Sorting.

    Not able to use any other means of sorting i believe.

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Having trouble insert/sorting array values w/ binary searching.

    Does your tree have to be self-balancing? If so, what self balancing method are you required to use (if any)?

    Second question, must you use an array to store your binary search tree? It's much easier to implement a nodal approach for binary search trees. If you can, maybe even implement a heap sort. Building a heap is O(n), where as building a binary search tree is O(nlogn). Critically, though, both items can return a sorted array in O(nlogn) time, but I think in practice heaps are faster (especially if you have an un-balanced tree).

  5. #5
    Super Moderator Json's Avatar
    Join Date
    Jul 2009
    Location
    Warrington, United Kingdom
    Posts
    1,274
    My Mood
    Happy
    Thanks
    70
    Thanked 156 Times in 152 Posts

    Default Re: Having trouble insert/sorting array values w/ binary searching.

    So I take it you have to implement the whole sorting your self then, so you cant just use a simple Treeset to do it for you?

        public static void main(String[] args) {
            final TreeSet<Integer> integers = new TreeSet<Integer>(Collections.reverseOrder());
     
            integers.add(10);
            integers.add(9);
            integers.add(11);
            integers.add(5);
            integers.add(87);
            integers.add(46);
            integers.add(1);
            integers.add(90);
     
            System.out.println(integers);
        }

    // Json

Similar Threads

  1. Replies: 1
    Last Post: December 22nd, 2011, 09:55 AM
  2. Searching Data
    By kalees in forum JavaServer Pages: JSP & JSTL
    Replies: 3
    Last Post: October 2nd, 2009, 04:23 AM
  3. [SOLVED] help with sorting...(comparator)
    By mdstrauss in forum Collections and Generics
    Replies: 2
    Last Post: July 26th, 2009, 07:25 AM
  4. [SOLVED] Java program to sort arrays containing dates
    By scottyadam in forum Collections and Generics
    Replies: 1
    Last Post: March 9th, 2009, 07:08 PM
  5. Trouble in downloading java
    By captjade in forum Java Theory & Questions
    Replies: 6
    Last Post: March 3rd, 2009, 04:16 PM