Array algorithms for adding/inserting element values
Lesson content
- About algorithms for adding elements (values) to an array
- Setting all array elements to a specific value
- Adding a value to the first/last free position
- Adding/inserting a value while maintaining array order (e.g., ascending or descending)
- Inserting a value into a specific position in the array
- Most common errors
About algorithms for adding elements (values) to an array
Adding a value to an array actually means assigning a new value to one of the “free spots” in the array (an array element with no value assigned). This does not refer to the quick initialization of an array, where the array is declared and values are assigned to its elements in a single statement. A similar term to adding is inserting values into an array. However, inserting usually involves moving existing elements one place left or right beforehand - to free the spot where the new value is to be added (inserted).
Adding a value to an array may be necessary:
- Immediately after initializing the array (setting all elements to an initial value).
- During regular use of the array (entering individual values into the array — into the first or last free position, or in such a way that the array’s order is maintained).
In the first case, this applies when the default value of array elements is not suitable. For example, elements of an array of real numbers are initialized by default to 0.0, but you might want them all to start as -1.0.
In the second case, a single element gets a new value — but only if the array is not full. This new value can be added to the first or last available spot, or in such a way that, after insertion, the elements retain a certain order (e.g., sorted in ascending order).
It’s important to mention that some of these algorithms were already introduced in previous lessons because it was necessary to make the examples work, but this lesson covers them in detail.
From an algorithmic perspective, when adding values to an array, a FOR-EACH loop cannot be used because element values are being changed. Other important characteristics of these algorithms include:
- One or more new values are inserted into the array.
- It is essential to ensure the array’s capacity is not exceeded.
- Typically, they involve finding the appropriate array element (“free spot”) where the new value will be stored.
- The algorithm must stop immediately after inserting the value, to prevent the same value from being added to multiple positions.
Setting all array elements to a specific value
When an array is initialized, its elements receive default values for the given data type in Java. For example:
- An array of integers gets all elements set to 0,
- A double array gets all elements as 0.0,
- A boolean array gets false for all elements, and so on.
In cases where a specific initial value is required that’s different from the default, an algorithm is used to assign that starting value to every element of the array. This might be done, for example, when the initial value is something unrealistic (like a negative body weight), to indicate that the value has not yet been entered — that is, the position in the array is still “free” for input.
Typically, this algorithm is written as part of the constructor. After initializing the array, each element is assigned the initial value.
Specifically, a FOR loop is used, where the loop counter goes through all index values (from 0 to length - 1), and during each iteration, one element is assigned the chosen value.
Example 1
Create a class ProductPrices that contains:
- An attribute prices that represents an array of prices for multiple products (e.g., 123.44).
- A constructor that receives the total number of prices as a parameter and initializes the prices array to that capacity. Additionally, it sets the (initial) values of all elements in the array to -1.
- A method print that prints all elements of the array from the first to the last on the screen.
1 class ProductPrices {
2
3 double[] prices;
4
5 ProductPrices(int numberOfProducts){
6 prices = new double[numberOfProducts];
7
8 for (int i = 0; i < prices.length; i++)
9 prices[i] = -1;
10 }
11
12 void print(){
13 for (int i = 0; i < prices.length; i++)
14 System.out.println(prices[i]);
15 }
16
17 }
Create a class TestProductPrices which in its main method creates one object of the ProductPrices class that should contain five prices and calls the print method.
1 class TestProductPrices {
2
3 public static void main(String[] args) {
4 ProductPrices pp = new ProductPrices(5);
5
6 pp.print();
7 }
8 }
In the constructor, you can see that after initializing the array, a FOR loop is used to go through all the elements and assign the initial value of -1.
If you’re using a counter to track how many prices have actually been entered into the array, the algorithm would still look the same — you’d go through all array elements (indices 0 to length - 1), since all need to be assigned an initial value.
Adding a value to the first/last free position
The most common way to add a value to an array is at the first or last available (free) spot. However, depending on how the array is used, there are different versions of these algorithms:
- Adding to a specific position (the entire array capacity is used, and it’s known exactly which element represents what — e.g., seats on a bus, monthly profits).
- Adding to the first/last free spot, but spots are not filled/released in order (requires searching from the beginning of the array to find a free spot).
- Adding to the first free spot, but spots must be filled/released in order (a counter is used to track how many elements have been filled; it gives the exact index of the first free spot, so searching isn’t needed).
In the next example, you’ll see how adding to a specific position works.
Example 2
Create a class MonthlyTemperatures that contains:
- An attribute monthlyTemperatures that represents an array of average temperatures in a city (e.g., 23.1) for each of the 12 months of the year. The first element corresponds to January, the second to February, etc., and the last to December. The array should be initialized immediately upon declaration.
- A method addTemperature that inserts a temperature for a given month into the appropriate element of the array. The first parameter of the method is the month number, and the second is the average temperature for that month. Note that months are numbered from 1 to 12, while array indices go from 0 to 11.
- A method print that prints all monthly temperatures using a FOR loop.
1 class MonthlyTemperatures {
2
3 double[] monthlyTemperatures = new double[12];
4
5 void addTemperature(int month, double temperature){
6 monthlyTemperatures[month -1] = temperature;
7 }
8
9 void print(){
10 for (int i = 0; i < monthlyTemperatures.length; i++)
11 System.out.println(monthlyTemperatures[i]);
12 }
13
14 }
Create a class TestMonthlyTemperatures which in its main method creates one object of the MonthlyTemperatures class, then enters arbitrary temperatures for each month and prints all monthly temperatures on the screen.
1 class TestMonthlyTemperatures {
2
3 public static void main(String[] args) {
4 MonthlyTemperatures mt = new MonthlyTemperatures();
5
6 mt.addTemperature(1,-3.4);
7 mt.addTemperature(2,2.2);
8 mt.addTemperature(3,8.1);
9 mt.addTemperature(4,13.8);
10 mt.addTemperature(5,17.3);
11 mt.addTemperature(6,23.1);
12 mt.addTemperature(7,29.1);
13 mt.addTemperature(8,28.5);
14 mt.addTemperature(9,20.3);
15 mt.addTemperature(10,12.9);
16 mt.addTemperature(11,7.6);
17 mt.addTemperature(12,6.7);
18
19 mt.print();
20 }
21 }
The adding algorithm is located in the addTemperature method. Since the full array is being used (up to its full capacity), and it is known exactly which element corresponds to which month, there is no need to search for a free spot, and therefore no FOR loop is needed. The value is added at a specific position — in this case, the month number minus one gives the index where the value should be stored. That’s why the month number is passed as a method parameter — along with the temperature to insert.
If you’re adding values to an array but not filling spots in order, then before each addition, you’ll need to search the array to find a free spot. This can be tricky, because sometimes it’s not obvious how to recognize a free spot in the array.
For example, if an array stores people’s weights, you might set the initial value of all elements to -1. While adding peoples weights, a free spot would be one that still has -1 — since negative weight is not a real-world value. After a weight is added, that spot will contain a real weight (e.g., 62 kg) instead of -1. Similarly, for a temperature array, a value like -1000 could be considered an impossible value, and used as an indicator that a spot is free (if the element contains that value).
However, this doesn’t always work. For example, in an array that stores a company’s profits (which can be both positive and negative), there’s no “impossible” value to use as an indicator. Also, arrays of boolean values can only contain true or false, so setting an “impossible” value as an indicator isn’t feasible either.
In such cases, a counter is introduced to keep track of how many elements have been filled (containing actual values), and the array is filled sequentially from the beginning.
In the next example, the case is shown where adding to the first/last free spot is done by searching (because the elements are not filled/released in order). It is also possible to use an “impossible” value as an indicator that a spot is free.
Example 3
Create a class ProductPrices2 by modifying the class ProductPrices. This class should have:
- An attribute prices representing an array of prices for multiple products (e.g. 123.44).
- A constructor that receives the total number of prices as a parameter and initializes the prices array to that capacity. Additionally, it sets the initial value of all elements in the array to -1.
- A method addFirst which takes a new price as a parameter and adds it at the first available spot in the array. A spot is available if the value at that position is -1. If there are no available spots, the method prints “No space left” to the screen.
- A method addLast which takes a new price as a parameter and adds it at the last available spot in the array. A spot is available if the value at that position is -1. If there are no available spots, the method prints “No space left” to the screen.
- A method print which prints all the elements of the array from the first to the last.
1 class ProductPrices2 {
2
3 double[] prices;
4
5 ProductPrices2(int numberOfProducts){
6 prices = new double[numberOfProducts];
7
8 for (int i = 0; i < prices.length; i++)
9 prices[i] = -1;
10 }
11
12 void addFirst(double newPrice){
13 for (int i = 0; i < prices.length; i++)
14 if (prices[i] == -1) {
15 prices[i] = newPrice;
16 return;
17 }
18
19 System.out.println("No space left");
20 }
21
22 void addLast(double newPrice){
23 for (int i = prices.length-1; i>=0; i--)
24 if (prices[i] == -1) {
25 prices[i] = newPrice;
26 return;
27 }
28
29 System.out.println("No space left");
30 }
31
32 void print(){
33 for (int i = 0; i < prices.length; i++)
34 System.out.println(prices[i]);
35 }
36
37 }
Create a class TestProductPrices2 which in the main method creates one object of the ProductPrices2 class with a capacity of 5 prices, inserts the price 123.45 at the beginning and 545.02 at the end, and then calls the print method.
1 class TestProductPrices2 {
2
3 public static void main(String[] args) {
4 ProductPrices2 pp = new ProductPrices2(5);
5
6 pp.addFirst(123.45);
7
8 pp.addLast(545.02);
9
10 pp.print();
11 }
12 }
The class ProductPrices2 contains an array of product prices and a constructor that initializes this array to the entered number of products (its capacity). This constructor also sets all elements in the array to -1, just like in the ProductPrices class. This is because -1 is considered an “impossible” price value, and serves as an indicator that the spot is free (i.e. that the array element at that position still has not been assigned a value).
The method addFirst adds a new price to the array, specifically to the first available spot. A FOR loop goes through all array indices (from 0 to length - 1), and an inner IF condition checks whether the current array element is “free,” i.e., whether its value is -1. If it is, the new price is assigned to that position, and the method ends using a return statement.
It’s very important for the method to stop immediately after the assignment — otherwise, the same price would be assigned into every available spot in the array. If the loop goes through the entire array without finding a free spot, it completes and reaches the line that prints “No space.” If a free spot is found, the return command stops the method, so the message is not printed.
The method addLast implements almost the same algorithm, except it inserts the new price at the last available spot in the array. The only difference is that the FOR loop iterates in reverse (from length - 1 to 0), so the first available spot starting from the end actually represents the last available spot if starting from the beginning.
The method print is the same as in the ProductPrices class.
In the next example, an algorithm for inserting at the first/last free spot is presented, without searching — instead, it uses a counter variable because elements are inserted and removed in order. This solution is the only possible option in cases where an “impossible” value cannot be used to indicate that a spot is free. But it can also be applied in other cases as well.
Additionally, it can be said that this approach is better in terms of program performance, because the free position is known exactly.
This example has already been partially covered in the lesson about arrays, so here it will just be explained further.
Example 4
Create a class ExamGrades2 that includes:
- An attribute examName representing the name of the exam.
- An attribute grades representing the students’ grades (for that exam). A grade is an integer in the range from 5 to 10.
- An attribute counter representing the current number of grades entered into the array. Its initial value is 0.
- A constructor that takes the number of students who registered for the exam as a parameter, and initializes the capacity of the grades array to that number.
- A method enterGrade that takes a grade as a parameter and inserts it into the first available spot in the array.
- A method print that prints all information about the exam: its name and all grades.
1 class ExamGrades2 {
2
3 String examName;
4
5 int[] grades;
6
7 int counter = 0;
8
9 ExamGrades2(int numberOfStudents){
10 grades = new int[numberOfStudents];
11 }
12
13 void enterGrade(int newGrade){
14 if (counter < grades.length) {
15 // The variable counter represents
16 // current number of grades in the array
17 // but also represents the index of the first
18 // free spot in the array.
19 grades[counter] = newGrade;
20
21 // The new grade is added to the array
22 // so it is necessary to increase the counter
23 // by one.
24 counter++;
25 }
26 else
27 System.out.println("No more free space");
28 }
29
30 void print(){
31 for(int i = 0; i< counter; i++)
32 System.out.println(grades[i]);
33 }
34
35 }
Create a class TestExamGrades2 which in the main method creates an object of class ExamGrades2 with 12 students registered, and:
- Inputs the exam name “Java programming”.
- Inputs the grades: 5, 10, 10, 7, and 8.
- Prints all the information about the exam to the screen.
1 class TestExamGrades2 {
2
3 public static void main(String[] args) {
4 ExamGrades2 eg = new ExamGrades2(12);
5
6 eg.examName = "Java programming";
7
8 eg.enterGrade(5);
9 eg.enterGrade(10);
10 eg.enterGrade(10);
11 eg.enterGrade(7);
12 eg.enterGrade(8);
13
14 eg.print();
15 }
16 }
The enterGrade method does not need to contain a FOR loop with a nested IF statement to find the “free spot,” i.e., an element with a value of zero. Assuming the counter is kept up-to-date, grades are added from the beginning of the array toward the end, meaning the counter value also represents the index of the first available spot. If no grades have been entered, the counter value is zero, and the grade should be added to the first array element (index zero). The counter should then be incremented by one. If one grade has already been entered, the counter value is one, which is also the index of the second array element (the next free spot).
Therefore, there’s no need for a FOR loop or a nested IF statement to find the first available spot. The entire method consists of a single IF statement. How do we know if there is any space left in the array? It’s enough to check whether the counter (number of entered grades) is less than the array capacity (length). If that’s the case, the input is done using two statements. The first adds the new grade at the first free spot (index equal to the counter), and the second increments the counter because a new grade has been added. If not, the ELSE block is executed and a message is printed saying there’s no more space.
How would the enterGrade and print methods look if grades were to be entered at the last available spot in the array, meaning the array is filled from the end toward the beginning? Modified code is given in the classes ExamGrades2A and TestExamGrades2A.
1 class ExamGrades2A {
2
3 String examName;
4
5 int[] grades;
6
7 int counter = 0;
8
9 ExamGrades2A(int numberOfStudents){
10 grades = new int[numberOfStudents];
11 }
12
13 void enterGrade(int newGrade){
14 if (counter < grades.length) {
15 // index of the last free spot
16 // is obtained when the largest
17 // index value is decremented by
18 // the current value of the counter
19 grades[grades.length-1- counter] = newGrade;
20
21 // The new grade is added to the array
22 // so it is necessary to increase the counter
23 // by one.
24 counter++;
25 }
26 else
27 System.out.println("No more free space");
28 }
29
30 void print(){
31 // The FOR loop counter goes from capacity -1
32 // down to the capacity -1 - counter because the
33 // array values are filled from the end of the
34 // array towards the beginning.
35 for(int i = grades.length-1; i> grades.length-1- counter; i--)
36 System.out.println(grades[i]);
37 }
38
39 }
1 class TestExamGrades2A {
2
3 public static void main(String[] args) {
4 ExamGrades2A eg = new ExamGrades2A(12);
5
6 eg.examName = "Java programming";
7
8 eg.enterGrade(5);
9 eg.enterGrade(10);
10 eg.enterGrade(10);
11 eg.enterGrade(7);
12 eg.enterGrade(8);
13
14 eg.print();
15 }
16 }
The only difference in the enterGrade method is that the index of the last free spot in the array is obtained by subtracting the counter value from the index of the last array element, i.e., “grades.length - 1 - counter”. After adding, the counter still needs to be incremented by one.
Another difference is seen in the print method, where the loop counter does not go from 0 to counter - 1, but from the last index (length - 1) backward to the last filled spot in the array (length - 1 - counter).
Adding/inserting a value while maintaining array order (e.g., ascending or descending)
In previous examples, array elements were usually added in arbitrary order, that is, in the order they were entered: first entered value at the first array position, second at the second, etc.
However, sometimes there is a need to keep the array values ordered, meaning some kind of sequence. If it’s an array of numbers or characters, the order could be:
-
Ascending: the first element has the smallest value, and each subsequent element has a larger value than the previous one, e.g.:
{-3, 1, 5, 6, 9, 11, 45}
-
Descending: the first element has the highest value, and each subsequent element has a smaller value than the previous one, e.g.:
{45, 11, 9, 6, 5, 1, -3}
When dealing with characters, letters are compared alphabetically. For example, a character array in ascending order would be:
1 {A, B, D, T, Y}
and in descending order:
1 {Y, T, D, B, A}
In case there are duplicate values in the array, then the ordering can be:
-
Non-descending (similar to ascending but with duplicates): the first element has the smallest value, and each subsequent element has a value greater than or equal to the previous one, e.g.:
{-1, 0, 1, 1, 3, 3, 3, 23, 32}
-
Non-ascending (similar to descending but with duplicates): the first element has the largest value, and each subsequent element has a value less than or equal to the previous one, e.g.:
{32, 23, 3, 3, 3, 1, 1, 0, -1}
How do we add/insert values to the array so that the existing order is preserved? If we’re dealing with ascending (or non-descending) order, the algorithm goes through the array using a FOR loop and finds the first element in the array with a value greater than the new value. That is exactly the place where the new value should be inserted to maintain ascending order.
Why do we say inserted instead of added? Because by simply adding the new value at that index would overwrite (replace) the existing value (it is not a “free spot”), so it is necessary to first “shift” all elements starting from that index to the right by one spot to create a “free spot”. Only then the new value can be placed in the array. Since the whole process involves both shifting array elements and adding a new value, it is more often referred to as inserting.
Example 5
For instance, if an array is sorted in ascending order and contains the following values (values of -1 represent “free” spots in the array):
1 {1, 3, 7, 34, 45, -1, -1, -1}
Then, inserting a new number 23 while maintaining ascending order means that this number should be placed “between” the numbers 7 and 34. Since there are no free spots between 7 and 34, a free spot must be created.
1 First, a free spot must be created "between" 7 and 34
2 {1, 3, 7, 34, 45, -1, -1, -1}
3 ^
4 |
A free spot is created by shifting the numbers 34 and 45 one position to the right — first copying 45 to the 6th position, then 34 to the 5th position (do not confuse element positions with their indexes). This order is important to avoid overwriting the value 45 if 34 is copied first.
- Copy number 45 one position to the right (from 5th to 6th position):
1 {1, 3, 7, 34, 45, -> -1, -1, -1}
2
3 Now 45 appears twice:
4
5 {1, 3, 7, 34, 45, 45, -1, -1}
- Copy number 34 to position 5:
1 {1, 3, 7, 34, -> 45, 45, -1, -1}
2
3 Now 34 appears twice:
4
5 {1, 3, 7, 34, 34, 45, -1, -1}
Now, since 34 appears twice, we overwrite the first instance with the new number 23 to maintain the ascending order.
Final step:
1 Insert 23 at position 3
2 {1, 3, 7, 34, 34, 45, -1, -1}
3 ^
4 |
5 23
6
7 Resulting in:
8
9 {1, 3, 7, 23, 34, 45, -1, -1}
There are two borderline cases here:
- If the array is empty, the new value is inserted at the first free spot. Since it will be the only value, the order is not disturbed — regardless of the type of ordering.
- If the array is full, no new value is inserted.
If the order is descending, the algorithm is exactly the same — only now, we look for the first element smaller than the new value. The shifting of elements to the right is still done the same way to free up a spot.
For non-descending or non-ascending orders, the logic is almost the same. The only difference is that we now look for the first element that is:
- Greater than or equal to the new value (for non-descending), or
- Less than or equal to the new value (for non-ascending).
That’s the position at which the new value should be inserted — even if it is a duplicate.
Example 6
For example, if an array is sorted in non-descending order (like ascending but allows duplicate values), and it contains the following values (spaces ’ ’ represent free positions):
1 {'A', 'D', 'L', 'M', 'R', ' ', ' '}
Then, inserting a new character ‘M’ (a duplicate) while preserving the order means it should be inserted “between” the characters ‘L’ and ‘M’ (or after the existing ‘M’, since the order would still be the same). Since there are no free spots between ‘L’ and ‘M’, a free spot needs to be created.
1 First, make a free spot between 'L' and 'M'
2 {'A', 'D', 'L', 'M', 'R', ' ', ' '}
3 ^
4 |
A free spot is created by shifting the characters ‘M’ and ‘R’ one position to the right. First copy ‘R’ to position 6, then ‘M’ to position 5. This order is critical to prevent overwriting ‘R’.
- Copy ‘R’ to the right:
1 {'A', 'D', 'L', 'M', 'R', -> ' ', ' '}
2
3 Now 'R' appears twice:
4
5 {'A', 'D', 'L', 'M', 'R', 'R', ' '}
- Copy ‘M’ to position 5:
1 {'A', 'D', 'L', 'M', -> 'R', 'R', ' '}
2
3 Now 'M' appears twice:
4
5 {'A', 'D', 'L', 'M', 'M', 'R', ' '}
Now that ‘M’ appears twice, we insert the new ‘M’ at position 4 (though this final step is optional in this specific case, since the shift already produced the desired result with two ‘M’ letters side by side).
Final step:
1 Insert 'M' at position 4 (optional, since 'M' is a duplicate)
2 {'A', 'D', 'L', 'M', 'M', 'R', ' '}
3 ^
4 |
5 'M'
6
7 The array remains sorted:
8
9 {'A', 'D', 'L', 'M', 'M', 'R', ' '}
All algorithms for insertion while maintaining order have two variations depending on whether a counter (that tracks the number of actual elements in the array) is used or not. For simplicity and universality, the version with a counter is used here.
Example 7
Create a class ProductPrices3 that has the following:
- A foodPrices attribute that represents an array with the prices of multiple food products (e.g., 123.44). The elements of this array should be arranged in non-decreasing order (with the cheapest food listed first).
- A counterFood attribute that represents the current number of entered prices in the foodPrices array. Its initial value is 0.
- A drinkPrices attribute that represents an array with the prices of multiple beverage products (e.g., 2499.44). The elements of this array should be arranged in non-increasing order (with the most expensive drinks listed first).
- A drinkCounter attribute that represents the current number of entered prices in the drinkPrices array. Its initial value is 0.
- A constructor that takes the total number of food and drink prices as parameters and initializes both arrays with the provided capacities.
- A method enterFoodPrice that takes a new price for a food item as a parameter and inserts it into the array while keeping the prices in non-decreasing order. If there is no available space in the array, the method will print the message “No space” on the screen.
- A method enterDrinkPrice that takes a new price for a beverage item as a parameter and inserts it into the array while keeping the prices in non-increasing order. If there is no available space in the array, the method will print the message “No space” on the screen.
- A method print that prints all the elements of both arrays on the screen, from the first to the last, with all the food prices in the first row and all the beverage prices in the second row. It should only print the prices that were actually entered.
1 class ProductPrices3 {
2
3 double[] foodPrices;
4 int foodCounter = 0;
5
6 double[] drinkPrices;
7 int drinkCounter = 0;
8
9 ProductPrices3(int totalFoodPrices, int totalDrinkPrices){
10 foodPrices = new double[totalFoodPrices];
11 drinkPrices = new double[totalDrinkPrices];
12 }
13
14 void enterFoodPrice(double newPrice){
15 //If there is no space left in the array
16 if (foodCounter == foodPrices.length){
17 System.out.println("No space");
18 return;
19 }
20
21 // Helper variable which stores the position index
22 // of the element where the new price should be inserted
23 // Initially, it is set on first free spot in
24 // the array - where the new price will be entered if
25 // the array is empty (counter is zero) or if all
26 // array elements have values less than the new price.
27 int index = foodCounter;
28
29 // First, find the place where the new price is
30 // to be entered. If the current element value is
31 // larger than or equal to the new price, that is
32 // the place to enter the new price.
33 for (int i = 0; i < foodCounter; i++)
34 if (foodPrices[i] >= newPrice) {
35 index = i;
36 break;
37 }
38
39 // Then, "shifting one place to the right" of all
40 // elements from that position is performed by
41 // copying the value of the previous element
42 // to the current element. This frees one space
43 // in the array in the index position.
44 for (int i = foodCounter -1; i >= index; i--)
45 foodPrices[i+1] = foodPrices[i];
46
47 // Add the new price to the right spot
48 // which is now free.
49 foodPrices[index] = newPrice;
50
51 //Increase the counter by one
52 foodCounter++;
53 }
54
55 void enterDrinkPrice(double newPrice){
56 //If there is no space left in the array
57 if (drinkCounter == drinkPrices.length){
58 System.out.println("No space");
59 return;
60 }
61
62 // Helper variable which stores the position index
63 // of the element where the new price should be inserted
64 // Initially, it is set on first free spot in
65 // the array - where the new price will be entered if
66 // the array is empty (counter is zero) or if all
67 // array elements have values less than the new price.
68 int index = drinkCounter;
69
70 // First, find the place where the new price is
71 // to be entered. If the current element value is
72 // lesser than or equal to the new price, that is
73 // the place to enter the new price.
74 for (int i = 0; i < drinkCounter; i++)
75 if (drinkPrices[i] <= newPrice) {
76 index = i;
77 break;
78 }
79
80 // Then, "shifting one place to the right" of all
81 // elements from that position is performed by
82 // copying the value of the previous element
83 // to the current element. This frees one space
84 // in the array in the index position.
85 for (int i = drinkCounter -1; i >= index; i--)
86 drinkPrices[i+1] = drinkPrices[i];
87
88 // Add the new price to the right spot
89 // which is now free.
90 drinkPrices[index] = newPrice;
91
92 //Increase the counter by one
93 drinkCounter++;
94 }
95
96 void print(){
97 for (int i = 0; i< foodCounter; i++)
98 System.out.print(foodPrices[i]+" ");
99
100 System.out.println();
101
102 for (int i = 0; i < drinkCounter; i++)
103 System.out.print(drinkPrices[i]+" ");
104 }
105
106 }
Create a class TestProductPrices3 that in the main method creates an object of the ProductPrices3 class containing five food prices and five beverage prices. Then, food prices 59.00, 134.50, 89.00, 129.00, and 39.00 and beverage prices 2500.00, 1209.00, and 803.00 are entered, and the method to print the arrays is called.
1 class TestProductPrices3 {
2
3 public static void main(String[] args) {
4 ProductPrices3 pp = new ProductPrices3(5,5);
5
6 pp.enterFoodPrice(59.00);
7 pp.enterFoodPrice(134.50);
8 pp.enterFoodPrice(89.00);
9 pp.enterFoodPrice(129.00);
10 pp.enterFoodPrice(39.00);
11
12
13 pp.enterDrinkPrice(2500.00);
14 pp.enterDrinkPrice(1209.00);
15 pp.enterDrinkPrice(803.00);
16
17 pp.print();
18 }
19 }
When the program is run, you should be able to see from the output on the screen that the arrays are sorted, regardless of the order in which the prices were entered.
In the enterFoodPrices method, it is first checked whether there is space in the array. If there is not (i.e., foodCounter equals the array capacity), a message “No space” is displayed, and the method stops. If there is space, the program moves to finding the correct position to insert the new price.
To find the correct position, an auxiliary variable index is introduced, which will contain the index of that position in the array. Initially, this variable is set to the value of foodCounter for several reasons:
- This value will change during the search for the appropriate position when a larger or equal element to the new price is found in the array.
- If the array is empty, the search will not change the value of index, but that is fine because foodCounter will be 0 (indicating that the array is empty), so the new price will be inserted at the first position in the array.
- If the array is not empty but all the prices in the array are smaller than the new price, the search will not change the value of index. This means that the new price should be added after all the entered food prices. This is fine because foodCounter will represent the index of the first free space in the array, and the new price will be inserted into that position.
After that, the program searches for the correct position to insert the new price, i.e., the first array element whose price is greater than or equal to the new price (“if (foodPrices[i] >= newPrice)”). If such a position is found, the variable index will get that position (i.e., the index of the element or the value of the loop counter i), and the search will stop. If no such position is found, this might mean that the array is empty (i.e., foodCounter is 0) or that no prices are greater than the new price. In both cases, the variable index will remain set to its initial value (i.e., foodCounter), so the new price will be inserted either at the start of the array (if it’s empty) or after all the already entered prices (if the array is not empty but all existing prices are smaller than the new one).
Then, the program shifts all the elements of the array that are at the found position (the value of index) “to the right” to make room for the new price. This shifting is done from right to left, with each subsequent element taking the value of the previous one (“foodPrices[i+1] = foodPrices[i];”), starting from the last entered price and going backward to the found position (“for (int i = foodCounter-1; i >= index; i—)”).
Finally, when the space is cleared by shifting the elements to the right, the new price is inserted at the found position in the array (“foodPrices[index] = newPrice;”), and the food counter is increased by one (“foodCounter++;”).
It can be seen that in the enterDrinkPrice method, there is almost an identical algorithm, except that instead of finding the first element greater than or equal to the new price, the program looks for the first element that is smaller than or equal to the new price (“if (drinkPrices[i] <= newPrice)”).
Inserting a value into a specific position in the array
Inserting a value at a specific position in an array is very similar to adding/inserting a value into an array while maintaining some order. The procedure is as follows:
- Free the desired position by shifting the next elements of the array one place to the right.
- Insert the new value into the desired (now free) position.
If the position is not freed before inserting the value, the new value will overwrite (replace) the existing value.
The difference compared to adding/inserting a value into an array while maintaining an order is that the array is not searched for the appropriate position; instead, the index of the desired position is provided as a parameter. In this sense, the algorithm is simpler.
Example 8
For instance, if an array is given with the following values (the values of -1 represent “free” spaces in the array):
1 {222, 31, 7, 34, 45, -1, -1, -1}
Then, inserting the new number 23 at position 4 (position, not index) means that this number should be inserted “between” the numbers 7 and 34. Since there are no free spaces between 7 and 34, a free space needs to be created.
1 First, a free space should be made "between" 7 and 34.
2 {222, 31, 7, 34, 45, -1, -1, -1}
3 ^
4 |
The free space is created by shifting the numbers 34 and 45 one position to the right. First, number 45 is copied to position 6, and then number 34 is copied to position 5. This sequence is followed to avoid overwriting the value 45 if 34 were copied to position 5 first. Here’s how the steps unfold:
1 First, number 45 is copied to position 6 in the array.
2 {222, 31, 7, 34, 45, -> -1, -1, -1}
3
4 Now we have 45 in two places:
5 {222, 31, 7, 34, 45, 45, -1, -1}
6
7 Then, number 34 is copied to position 5 in the array.
8 {222, 31, 7, 34, -> 45, 45, -1, -1}
9
10 This "overwrites" the 45 that was there earlier, but now we have the number 34 in two places.
11 {222, 31, 7, 34, 34, 45, -1, -1}
It is important to note that now the value 34 appears twice, so instead of the first appearance of 34, we insert the new number 23, which prevents overwriting any existing value in the array:
1 Finally, the number 23 is added at position 4 in the array.
2 {222, 31, 7, 34, 34, 45, -1, -1}
3 ^
4 |
5 23
6
7 This "overwrites" the duplicate 34.
8 {222, 31, 7, 23, 34, 45, -1, -1}
There are also two edge cases to consider: an empty array and a full array. If the array is empty, everything is exactly the same — values are shifted to the right (for simplicity of the algorithm, even though these are “empty places”) and the new value is then inserted into the desired position. If the array is full, no new value can be inserted.
Example 9
Add the following method to the ExamGrades2 class:
- The method insertGrade takes the new grade and the index of the position in the array where the new grade should be inserted. The inserted index must be less than or equal to the grade counter, and the method inserts the new grade at the desired position in the array without overwriting existing grades. If there is no space in the array, print a message “No more free space”. If the entered index is greater than the value of the counter, just print the message “Invalid index.”
The solution could look like this:
1 void insertGrade(int newGrade, int index){
2 if (counter >= grades.length) {
3 System.out.println("No more free space");
4 return;
5 }
6
7 if (index > counter){
8 System.out.println("Invalid index");
9 return;
10 }
11
12 //Shift all elements to the right
13 for (int i = grades.length-1; i >index ; i--)
14 grades[i] = grades[i-1];
15
16 //Insert new grade at desired position (index)
17 grades[index] = newGrade;
18
19 //Increase counter by one
20 counter++;
21 }
Most common errors
Some of the most common errors related to algorithms for adding/inserting values to arrays that are not syntax errors but affect the program’s functionality are:
- Using a FOR-EACH loop to insert new values into an array, for example:
1 class IntegerArray {
2 int[] intArray = new int[10];
3
4 IntegerArray(){
5 for (int number: intArray)
6 number = -1;
7 }
8
9 void enterNumber(int newNumber){
10 for (int number: inArray)
11 if (number == -1){
12 number = newNumber;
13 break;
14 }
15 }
16 }
Instead, the correct approach is to use a regular FOR loop:
1 class IntegerArray {
2 int[] intArray = new int[10];
3
4 IntegerArray(){
5 for (int i = 0; i < intArray.length; i++)
6 intArray[i] = -1;
7 }
8
9 void enterNumber(int newNumber){
10 for (int i = 0; i < intArray.length; i++)
11 if (inArray[i] == -1){
12 intArray[i] = newNumber;
13 break;
14 }
15 }
16 }
- Forgetting to increment the element counter after adding or inserting a new value (all new values will be inserted into the first element of the array), for example:
1 int[] grades = new int[30];
2 int counter = 0;
3
4 void enterGrade(int newGrade){
5 if (counter < grades.length) {
6 grades[counter] = grade;
7 }
8 else
9 System.out.println("No more space in the array for new grades");
10 }
Instead, the correct way is:
1 int[] grades = new int[30];
2 int counter = 0;
3
4 void enterGrade(int newGrade){
5 if (counter < grades.length) {
6 grades[counter] = grade;
7 counter++;
8 }
9 else
10 System.out.println("No more space in the array for new grades");
11 }
- Forgetting to break the loop after inserting the value at the desired position in the array, or forgetting to use a break or return statement, for example:
1 void enterGrade(int newGrade){
2 for (int i = 0; i < grades.length; i++)
3 if (grades[i] == -1){
4 grades[i] = newGrades;
5 }
6 }
Instead, the correct way is:
1 void enterGrade(int newGrade){
2 for (int i = 0; i < grades.length; i++)
3 if (grades[i] == -1){
4 grades[i] = newGrades;
5 break;
6 }
7 }
- When initializing all the elements of the array, iterating up to the element counter rather than the entire array length:
1 class IntegerArray {
2 int[] intArray = new int[10];
3 int counter = 0;
4
5 IntegerArray(){
6 for (int i = 0; i < counter; i++)
7 intArray[i] = -1;
8 }
9 }
Instead, the correct approach is:
1 class IntegerArray {
2 int[] intArray = new int[10];
3 int counter = 0;
4
5 IntegerArray(){
6 for (int i = 0; i < intArray.length; i++)
7 intArray[i] = -1;
8 }
9 }
- When adding a new value at a specific position in the array (using a full array capacity), forgetting to adjust the index by subtracting one so that it corresponds to the element index in the array (e.g., 0 for January instead of 1):
1 class MonthlyTemperatures {
2
3 double[] monthlyTemperatures = new double[12];
4
5 void addTemperature(int month, double temperature){
6 monthlyTemperatures[month] = temperature;
7 }
8 }
Instead, the correct approach is:
1 class MonthlyTemperatures {
2
3 double[] monthlyTemperatures = new double[12];
4
5 void addTemperature(int month, double temperature){
6 monthlyTemperatures[month - 1] = temperature;
7 }
8 }
- Using the wrong comparison operator (“less than” < or “less than or equal to” <= instead of “greater than” > or “greater than or equal to” >=), thus arranging the input so the order becomes descending instead of ascending (non-descending instead of non-ascending when duplicates exist), for example:
1 void enterFoodPriceNonDescending(double newPrice){
2 if (foodCounter == foodPrices.length){
3 System.out.println("No space");
4 return;
5 }
6
7 int index = foodCounter;
8
9 for (int i = 0; i < foodCounter; i++)
10 if (foodPrices[i] <= newPrice) {
11 index = i;
12 break;
13 }
14
15 for (int i = foodCounter -1; i >= index; i--)
16 foodPrices[i+1] = foodPrices[i];
17
18 foodPrices[index] = newPrice;
19
20 foodCounter++;
21 }
Instead, the correct approach is:
1 void enterFoodPriceNonDescending(double newPrice){
2 if (foodCounter == foodPrices.length){
3 System.out.println("No space");
4 return;
5 }
6
7 int index = foodCounter;
8
9 for (int i = 0; i < foodCounter; i++)
10 if (foodPrices[i] >= newPrice) {
11 index = i;
12 break;
13 }
14
15 for (int i = foodCounter -1; i >= index; i--)
16 foodPrices[i+1] = foodPrices[i];
17
18 foodPrices[index] = newPrice;
19
20 foodCounter++;
21 }