Reputation: 993
Inserting an element into an array in sorted order
I'm trying to add an element into an array in sorted order.
This is my code :
public class SortedInsertion {
public static void main(String[] args) {
int[] arr=new int[6];
arr[0]=5;
arr[1]=6;
arr[2]=9;
arr[3]=11;
System.out.println(Arrays.toString(arr));
insert(7,arr);
}
public static void insert(int val,int[] arr){
int i;
for(i=0;i<arr.length-1;i++){
if(arr[i]>val)
break;
}
for(int k=i;k<arr.length-1;k++){
arr[k+1]=arr[k];
arr[i]=val;
}
System.out.println(Arrays.toString(arr));
}
}
I'm getting the output as: [5, 6, 9, 11, 0, 0]
[5, 6, 7, 9, 9, 9]
But the right out put is
5,6,9,11,0,0
5,6,7,9,11,0
Upvotes: 4
Views: 37315
Answers (11)
Reputation: 139
this solution maybe help you or notice for in a specific your problem
in a sorted array , a search operation is performed for the possible position of the givin element by using Binary search , and then an insert operation is performed followed by shifting the elements to the right way .
public class InsertElmSort {
// Inserting a key elements in arr[] of gevin.
//capacity . n is current size of arr[] .
//this function return n + 1 if insertion is successful,
//else return n .
static int insertSorted(int arr[] , int n , int key , int capacity ) {
int i;
for(i = n - 1 ; (i >= 0 && arr[i] > key); i-- ) {
arr[i + 1] = arr[i];
//the way 1
//arr[i] = key;
}
//the way 2 instead of above way 1 by out the for loops block
arr[i + 1] = key;
// can not access more elements if n is already
//more than or equal capacity
if(n >= capacity) {
return n;
}
return (n + 1);
}
public static void main (String args[]) {
int arr[] = new int[20];
arr[0] = 1 ;
arr[1] = 3 ;
arr[2] = 5;
arr[3] = 6;
arr[4] = 9;
arr[5] = 11;
int n = 6;
int capacity = arr.length;
int key = 7;
System.out.print("Before the insertion: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
//call function to inserting key .
n = insetSorted(arr , n , key , capacity);
System.out.print("\n After the insertion: ")
for(int i = 0; i < n ; i++) {
System.out.print(arr[i] + " ");
}
}
}
Upvotes: 0
Reputation: 11
You could use the arrays.sort() functionality to insert a value into a new array then sort it. It solves the issue in a roundabout way. For example
int num = 10;
int array[] = {6, 7, 8};
int copy_array[] = new int[array.length + 1];
for (int i = 0; i < array.length; i++) {
copy_array[i] = array[i];
}
copy_array[copy_array.length - 1] = given_number;
Arrays.sort(copy_array);
Upvotes: 0
Reputation: 51
You can use the Arrays or Collections binarySearch function to get the position to insert the new value at, you will need to shift all elements from this position (if any) to the right
int position = Math.abs(Collections.binarySearch(sortedList, key)) - 1;
Upvotes: 5
Reputation: 1616
To be honest, the array in question is not really sorted like this: [0, 0, 5, 6, 9, 11].
It is a "zero tailed" array: [5, 6, 9, 11, 0, 0].
So to insert a value into that array it needs to know how many elements occupied are. In case when you provide this value into a method it would have O(log n) complexity. Otherwise, it needs to implement counting inside the inserting method.
/**
* @throws ArrayIndexOutOfBoundsException when the array is full and the value to be inserted is greater than the last element
*/
private static void insertToZeroTailedArray(int val, int[] arr) {
// an O(n) operation to count occupied elements
int elementsCount = 0;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
elementsCount = i + 1;
break;
}
}
// binarySearch returns a negative position to insert if the value was not found
int index = Arrays.binarySearch(arr, 0, elementsCount, val);
if (index != 0) {
int pos = index < 0
? -index - 1 // val not found, it is need to be inserted at (-index)-1 position
: index; // val found but we are going to insert it again
// shift the array to right and drop last element because of the array bounds
System.arraycopy(arr, pos, arr, pos + 1, arr.length - pos - 1);
arr[pos] = val;
} else {
// the case when value is found at 0 position
System.arraycopy(arr, 0, arr, 1, arr.length - 1);
arr[0] = val;
}
}
An alternative way to do what you need with O(log n) complexity for a really sorted array:
private static void insertToReallySortedArray(int val, int[] arr) {
int index = Arrays.binarySearch(arr, val);
if (index != 0) {
int pos = index < 0 ? -index - 1 : index;
System.arraycopy(arr, pos, arr, pos + 1, arr.length - pos - 1);
arr[pos] = val;
} else {
System.arraycopy(arr, 0, arr, 1, arr.length - 1);
arr[0] = val;
}
}
Based on this great answer.
Upvotes: 0
Reputation: 3758
completely unclear how an insert function should work without knowing the number of fields already occupied?
public static void insert( int n, int occupied, int[] array ) {
if( n >= array[occupied - 1] )
array[occupied] = n;
else
for( int i = 0; i < array.length; i++ ) {
int n1 = array[i];
int n2 = array[i + 1];
if( n1 > n || n1 < n && n2 >= n ) {
if( n1 > n ) i--;
System.arraycopy( array, i + 1, array, i + 2, occupied - i - 1 );
array[i + 1] = n;
break;
}
}
}
called from Your example above:
…
arr[3]=11;
int occupied = 4;
insert( 7, occupied, arr ); // [5, 6, 7, 9, 11, 0]
unchecked bust with ArrayIndexOutOfBoundsException if occupied >= array.length
Upvotes: 0
Reputation: 21
public class InsertInSortedArray {
public static void main(String[] args) {
int arr[] = {5, 6, 9, 11};
Arrays.sort(arr);
int k = 7;
int index = findIndexToBeInserted(arr, k, 0, arr.length - 1);
ArrayList<Integer> al = new ArrayList<>();
for (int i : arr)
al.add(i);
al.add(index, k);
for (int i : al)
System.out.println(i);
}
private static int findIndexToBeInserted(int[] arr, int k, int start, int end) {
if (k == 0)
return 0;
int mid = (start + end) / 2;
if (k > arr[mid] && k < arr[mid + 1])
return mid + 1;
if (arr[mid] < k)
return findIndexToBeInserted(arr, k, mid + 1, end);
return findIndexToBeInserted(arr, k, start, mid - 1);
}
}
Upvotes: 2
Reputation: 3510
Java Code,
public static void insertElementInSortedArr(int a[], int val) {
int n[] = new int[a.length + 1];
int j = 0;
boolean isAdded = false;
for (int i = 0; i < a.length; i++) {
if (a[i] < val) {
n[j] = a[i];
j++;
} else {
if (!isAdded) {
n[j] = val;
j = j + 1;
isAdded = true;
}
n[j] = a[i];
j = j + 1;
}
}
}
Upvotes: 0
Reputation: 57
Another way of solving is by using List and collections.sort method.
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < arr.length; i++) {
list.add(arr[i]);
}
list.add(val);
Collections.sort(list);
int[] result = list.stream().mapToInt(Integer::intValue).toArray();
System.out.println(Arrays.toString(result));
Hope this solutions helps.
Upvotes: 0
Reputation: 7926
Here
arr[k+1]=arr[k];
You're overriding every next array element with a previous value. You should probably reverse your loop and move from the end of the array, shifting all elements forward until you find the right spot, i.e.:
public static void insert(int val, int[] arr) {
for(int i = arr.length - 1; i > 0; i--) {
if (arr[i] == 0) continue; // skip last elements to avoid array index out of bound
arr[i + 1] = arr[i]; // shift elements forward
if (arr[i] <= val) { // if we found the right spot
arr[i] = val; // place the new element and
break; // break out the loop
}
}
System.out.println(Arrays.toString(arr));
}
Upvotes: 0
Reputation: 677
Change the insert method like this:
public static void insert(int val,int[] arr){
int i;
for(i=0;i<arr.length-1;i++){
if(arr[i]>val)
break;
}
for(int k=arr.length-2; k>=i; k--){
arr[k+1]=arr[k];
}
arr[i]=val;
System.out.println(Arrays.toString(arr));
}
Upvotes: 1
Reputation: 35577
There is an issues in your for loop
for(i=0;i<arr.length-1;i++){}
It should iterate up to i<arr.length
for(i=0;i<arr.length;i++){}
Upvotes: 1
Related Questions
- Inserting an integer into a sorted array
- Sorting elements using insertion sort
- Java Insertion Sort
- Inserting and Sorting in ascending order
- Insert an item into unordered array
- How to find correct position to insert an element in a sorted array?
- how to insert an integer element into sorted array
- How to insert number in a sorted array
- Java and Arrays - Insertion sort in ascending order
- Inserting into array in order