Results 1 to 3 of 3
  1. #1
    bh-chobo is offline Member
    Join Date
    Oct 2009
    Posts
    6
    Rep Power
    0

    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,size, value);
    		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;
    			}
        }
    Last edited by bh-chobo; 10-07-2009 at 11:41 AM.

  2. #2
    xcallmejudasx's Avatar
    xcallmejudasx is offline Senior Member
    Join Date
    Oct 2008
    Location
    Houston, TX & Flint, MI
    Posts
    609
    Rep Power
    7

    Default

    Try to explain your question clearer. From my understanding you have an unsorted array that you're trying to sort using binary search. Binary search only works on sorted arrays so you would need to sort it first. There is something like binary insertion which is basically insertion sort that could sort for you. Essentially each time you add a new number to your array you sort it. So using your example {10,9,11} it would be something like

    array = {}
    insert 10
    array = {10}
    check is 9 is < 10 or > 10 //this is your binary search
    insert 9 at location
    array = {9,10}
    check if 11 is < 9 or > 10 or inbetween //binary search
    insert 11 at location
    array = {9,10,11}

    The example becomes clearer when using more values. Essentially you just run a binary search for where the item you're inserting would be located and then inserting it in that spot.
    Liberty has never come from the government.
    Liberty has always come from the subjects of government.
    The history of liberty is the history of resistance.
    The history of liberty is a history of the limitation of governmental power, not the increase of it.

  3. #3
    bh-chobo is offline Member
    Join Date
    Oct 2009
    Posts
    6
    Rep Power
    0

    Default

    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.

    Much appreciated for your tips.

Similar Threads

  1. trouble with sorting! T^T
    By PureAwesomeness in forum New To Java
    Replies: 1
    Last Post: 03-09-2009, 01:44 PM
  2. [SOLVED] trouble in sorting...please help
    By jacline in forum New To Java
    Replies: 8
    Last Post: 03-08-2009, 05:44 PM
  3. java binary search and insert
    By pansylea in forum New To Java
    Replies: 6
    Last Post: 02-23-2009, 05:54 PM
  4. Binary Search searching news Article
    By peterdfl in forum New To Java
    Replies: 0
    Last Post: 09-26-2008, 12:57 AM
  5. Replies: 0
    Last Post: 04-14-2008, 09:39 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •