My code sorts lists in ascending order when the length of a list is 3, the code works perfectly, however, when the length of a list increases and the number of inserted variables increase, the output is either System out of bound or it doesn't sort it correctly.

    public class Lists {
        
    int [] lists;
    int itemcount;
    
    public Lists(int l) {
        lists =new int[l];
        itemcount=0;
    }
    public void insert(int x) {
        if(itemcount==0) {
            lists[itemcount]=x;
            itemcount  ;
        }
        else {
            for(int i=itemcount-1;i>=0;i--) {
                if(lists[i]>x) {
                    lists[i 1]=lists[i];
                    lists[i]=x;
                    itemcount  ;
                }
                else {
                    lists[i 1]=x;
                    itemcount  ;
                    
                }
            }
        }
    }
    public static void main(String[]args) {
        Lists s=new Lists(5);
        s.insert(9);
        s.insert(4);
        s.insert(6);
        s.insert(5);
        s.insert(8);
    
        
        for (int i=0;i<s.lists.length;i  ) {
            System.out.print(s.lists[i]);
        }
        
        
    }
    
    }

CodePudding user response：

The "sorting" part does not seem to be correct, itemcount is incremented in loop several times instead of 1 when only 1 element is inserted.

Thus, the index should be detected where the new item has to be inserted, then the elements shoulds be shifted to the end of lists array.

Also, a case needs to be addressed when there is an attempt to insert more elements than lists.length: print a message and ignore the attempt, throw an exception, or increase the size of lists (e.g. using Arrays.copyOf)

Linear search of the id is as follows as the size of lists is relatively small (if the lists size is large enough, a binary search should be used)

public void insert(int x) {
    if (itemcount == lists.length) {
        lists = Arrays.copyOf(lists, lists.length * 2);
    }
    int id = 0;
    for (; id < itemcount; id  ) {
        if (x <= lists[id]) {
            break; // insert in id
        }
    }
    for (int i = itemcount; i > id; i--) {
        lists[i] = lists[i - 1];
    }
    lists[id] = x;
    itemcount  ;
}

Also, when printing the contents of lists it may better to use itemcount as a limit, unless it's needed to show 0's as empty elements.

So, the output for the following test setup:

Lists s = new Lists(5);
s.insert(9); s.insert(4); s.insert(6);
s.insert(5); s.insert(8); s.insert(5);
s.insert(2);

for (int i=0;i<s.itemcount;i  ) {
    System.out.print(s.lists[i]   " ");
}

Output:

2 4 5 5 6 8 9 

CodePudding user response：

This is insertion sort, each time we insert an item to the already sorted list. All the elements greater than the item is moved ahead. So we need to stop at the right position so it require additional condition in the iteration loop. see how it works , https://en.wikipedia.org/wiki/File:Insertion-sort-example-300px.gif

public void insert(int x) {
  int i;/*Insertion position */
  for(i=itemcount-1;i>=0 && lists[i]>x;i--) {
    lists[i 1]=lists[i];
  }
  lists[i 1]=x;
  itemcount  ;    
 }