Array algorithms for sorting

• What is array sorting, element order (ascending, descending, non-ascending, non-descending)
• The “Bubble sort” algorithm for sorting
• The “Selection sort” algorithm for sorting
• Most common errors

In previous examples, array elements were added to the array in the order they were entered: the first entered value was placed at the first position, the second at the second, and so on. In the lesson on algorithms for adding elements to an array, we covered an algorithm that performs insertion while maintaining a certain order of the elements.

As a reminder, the order of array elements refers to their arrangement according to a specific criterion. If we are dealing with a sequence of numbers or characters, the order can be:

• Ascending: the first element has the smallest value, and each subsequent element has a greater value than the previous one, e.g.:

  {-3, 1, 5, 6, 9, 11, 45}

• Descending: the first element has the greatest value, and each subsequent element has a smaller value than the previous one, e.g.:

  {45, 11, 9, 6, 5, 1, -3}

When it comes to characters, letters are compared based on their alphabetical order. For example, a character array sorted in ascending order would be:

And in descending order:

In the case where element values are repeated in the array (i.e., there are duplicates), the order can instead be:

• Non-descending (similar to ascending, but allows 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.:

• Non-ascending (similar to descending, but allows 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.:

Achieving a desired order or arrangement of array elements can be done in two ways:

• By maintaining the order while inserting new elements
• By sorting the array afterward, when needed

Maintaining order while inserting each new element, i.e., the corresponding algorithms for this were covered in the lesson on adding elements to an array and will be briefly reviewed here. The idea is that adding a new value to the array is done in such a way that the existing order is preserved. This means that a new value shouldn’t be inserted just anywhere in the array, but in a precisely determined location, so that the order of the elements remains intact (e.g., the elements stay sorted in ascending order).

In practice, this means the array will always be sorted, but it also means that each new insertion becomes more complex (and sometimes slower) than usual, because the correct place for the new value must first be found, and then the existing values must be shifted to make space for insertion.

For example, suppose we need to insert the number 23 into the following array (the values -1 represent “free” or unused positions in the array), in such a way that the order of the elements, which is currently ascending, remains ascending:

This means that the number 23 needs to be inserted between 7 and 34. This is achieved first by shifting the elements to the right (from 34 onward) to make a free space, and then inserting the number 23 in the correct position:

However, it is often unnecessary or even undesirable (due to performance reasons) to maintain a sorted array at all times. In such cases, we turn to sorting the array when needed. This process of arranging all elements of the array according to a particular order is called array sorting. Sorting involves swapping elements in the array (moving them from one position to another) until the desired order is achieved. This is a complex operation and may take a relatively long time — the longer the array (the more elements it has), the longer the sorting takes.

There are many algorithms for sorting arrays (and other data structures): some use additional auxiliary arrays to speed up the sorting process, some do not, some algorithms divide the original array into smaller parts and sort those first before merging them back together, and so on. In this collection, two simple sorting algorithms will be covered that do not use auxiliary arrays:

• The Bubble Sort algorithm
• The Selection Sort algorithm

These are simple sorting algorithms mainly used in teaching, and less often for solving real-world sorting problems. Materials about what other sorting algorithms exist and how they work can be found in courses, tutorials, and books on data structures and algorithms.

These two sorting algorithms cannot be implemented using a FOR-EACH loop because they require swapping of array element values. Other characteristics of these sorting algorithms include:

• They sort the entire array, which already contains one or more values.
• They perform swapping of array elements (moving them from one position to another) until all elements are ordered.
• Sorting is done according to a sorting criterion, to achieve the desired order or arrangement of elements (ascending, non-ascending, descending, non-descending).
• They usually consist of two nested loops — because the array needs to be traversed multiple times.
• In some cases, it is possible to optimize the algorithm by stopping it early if/when it is determined that the array is already sorted.

“Bubble sort” is one of the simplest algorithms for this purpose. The name of the algorithm comes from its core idea: during the first pass through the array, the largest element “floats to the top” (like a bubble); in the second pass, the second-largest element floats to the top; in the third pass, the third-largest, and so on. After as many passes as there are elements in the array, the elements will have “floated” one by one in order from largest to smallest.

The only additional step required is that, as the elements “float”, they are stored back into the array in that order (e.g., from the end of the array toward the beginning), and this results in the array being sorted. If the goal is the reverse order, then in each pass the smallest element is made to “float” instead of the largest.

How does this “floating to the top” happen, and how is the found element placed back in the array in order? It works by traversing the array sequentially, comparing every pair of neighbouring (adjacent) elements, and if the first element is greater than the second, their positions are swapped.

This results in the largest element “bubbling up” to the last position in the array after the first pass. For example, if we have an array to be sorted in ascending order, the steps are as follows:

Initial array:

{3, 1, 8, 5}

Compare the first and second elements (3 and 1). Swap them because 3 is greater than 1: {3,<-> 1, 8, 5} → {1, 3, 8, 5} ^——-

Compare the second and third elements (3 and 8). Do not swap because 3 is less than 8: {1, 3, 8, 5} ^—

Compare the third and fourth elements (8 and 5). Swap them because 8 is greater than 5: {1, 3, 8,<-> 5} → {1, 3, 5, 8} ^——-

The largest element (8) has “floated” to the last position in the array. The array is now sorted, so the sorting process can stop: {1, 3, 5, 8}

It’s important to note that the array is sorted gradually. With each pass through the array:

• The sorted part of the array (at the end) grows by one element.
• The unsorted part of the array (at the beginning) shrinks by one element.

In the above example, the array was relatively simple, so one pass was enough. Not only did the largest element (8) bubble up to the end, but the whole array became sorted in ascending order, so further passes were unnecessary.

However, this is not always the case. In general, multiple passes through the array are needed. During each pass, elements that are already sorted (at the end of the array) must not be touched.

For example, take a similar array with a different order:

{5, 3, 8, 1}

1. 1st Pass Through the Array

   Compare the first and second elements (5 and 3). Swap them because 5 > 3: {5,<-> 3, 8, 1} → {3, 5, 8, 1} ^——-

   Compare the second and third elements (5 and 8). No swap needed (5 < 8): {3, 5, 8, 1} ^—

   Compare the third and fourth elements (8 and 1). Swap them because 8 > 1: {3, 5, 8,<-> 1} → {3, 5, 1, 8} ^——-

   The largest element (8) has “floated” to the last position, but the array is not yet sorted. The sorted part of the array includes only the last element (8), while the unsorted part includes 3, 5, and 1:

   {3, 5, 1, 8}

2. 2nd Pass Through the Array

   Compare the first and second elements (3 and 5). No swap needed (3 < 5): {3, 5, 1, 8} ^—

   Compare the second and third elements (5 and 1). Swap them because 5 > 1: {3, 5,<-> 1, 8} → {3, 1, 5, 8} ^——-

   Now, the second-largest element (5) has “floated” to the second-to-last position. The sorted part now includes 5 and 8. The unsorted part includes 3 and 1: {3, 1, 5, 8}

3. 3rd Pass Through the Array

   Compare the first and second elements (3 and 1). Swap them because 3 > 1: {3,<-> 1, 5, 8} → {1, 3, 5, 8} ^——-

   The third-largest element (3) has “floated” to the correct place. The entire array is now sorted: {1, 3, 5, 8}

How many passes are needed? When can we be sure the array is fully sorted?

In general:

• If an array has 4 elements, a maximum of 3 passes is needed.
• If it has 10 elements, then sorting is guaranteed after 9 passes.

In other words, the maximum number of passes is the number of elements minus one.

Also, in each pass, only the unsorted portion of the array is processed:

• First pass: all elements
• Second pass: all except the last
• Third pass: all except the last two
• And so on.

However, if during a pass no swaps occurred, it means the elements are already sorted, and the algorithm can terminate early. This is one of the possible improvements (optimizations) of the Bubble sort algorithm.

Example 1

Create a class ProductPrices that contains:

• An attribute prices representing an array of prices of multiple products (e.g., 123).
• An attribute counter representing the counter of elements, i.e., the number of prices actually entered into the array.
• A constructor that receives the total number of prices as a parameter and initializes the prices array with that capacity.
• A method enterPrice, which receives a new price as a parameter and inserts it into the array at the first free position. If the entered price is less than zero, or if there is no space in the array, the method should simply display the message “ERROR” on the screen.
• A method sortNonDescending that uses the Bubble sort algorithm to sort all entered prices in non-descending order.
• A method sortNonAscending that uses the Bubble sort algorithm to sort all entered prices in non-ascending order.
• A method sortNonDescending2 that also uses the Bubble sort algorithm to sort all entered prices in non-descending order, but uses a slightly improved version of the algorithm which stops execution as soon as the array is sorted — if this happens before all expected passes are completed.
• A method sortNonAscending2 that also uses the Bubble sort algorithm to sort all entered prices in non-ascending order, and also uses the improved version of the algorithm that stops early if the array is already sorted.
• A method print that prints all elements of the array in a single line.

Create a class TestProductPrices which in the main method creates an object of the class ProductPrices that can contain a maximum of eight prices. Enter five prices of your choice. Sort the array of prices in non-descending order, print the array, then sort it in non-ascending order and print the array again.

In the sortNonDescending method, the standard implementation of the Bubble Sort algorithm in Java is shown. The outer FOR loop repeats passes through the array. The maximum number of passes is equal to the number of entered values minus one (counter - 1 passes). This loop uses a counter i, which is also later used in the inner FOR loop.

The inner FOR loop performs one full pass through the array. The loop counter j takes values from 0 to counter - i - 2. Why this range?

• First, because in each step, two adjacent elements of the array are compared (indexes j and j+1), so the loop counter must take one value less than the maximum index to avoid going out of bounds. (Instead of counter - 1, we use counter - 2.)
• Second, and more importantly, this ensures that only the unsorted part of the array is processed in each pass: from the beginning of the array (index 0) to the last element that has not yet “floated up” in previous passes.

The idea is that elements which “float” to the end of the array as the largest are not touched in subsequent passes, since they are already sorted. In this way, they are skipped in each new pass through the array.

Specifically, in the first pass, the outer FOR loop counter i will have the value 0, so the inner FOR loop counter j will go from 0 to counter - i - 2, i.e., from 0 to counter - 2 (since i = 0), meaning the entire entered array is processed. In the last iteration of the inner FOR loop, j will be counter - 2 and j+1 will be counter - 1, so the second-to-last and last elements will be compared.

At the end of the first pass, the largest element in the array will have “floated” to the last position (index counter - 1).

In the second pass, the outer FOR loop counter i will be 1, so the inner FOR loop counter j will go from 0 to counter - 3 (since i = 1) — which means that the largest value at the end of the array (index counter - 1) will be ignored.

It’s also important to note that in the comparison of each pair of adjacent elements in the inner FOR loop, a swap is only performed if the previous element is greater than the next. In this way, the larger value is pushed toward the end of the array — i.e., it “floats.”

What happens if the values are equal? No swap is performed because there is no need — the order doesn’t change.

Also, the actual swap is always performed using a temporary variable.

In the method sortNonAscending, a nearly identical algorithm is shown. The only difference is the comparison criterion, as the goal is a different sort order.

Here, a swap is performed only if the previous element is less than the next one, so the smaller values float to the end, and we get non-ascending order.

The improvement to the Bubble sort algorithm consists of recognizing when the array is already sorted (either from the start or during sorting) and stopping early to avoid unnecessary passes and comparisons/swaps.

• First, it may happen that the array was accidentally entered already in the desired order, so no sorting is needed at all.
• Second, as shown in the earlier examples, in some cases the array may be sorted after just one pass, even though more passes are planned — these extra passes would be unnecessary.

The solution is to add a check to see if at least one swap of adjacent elements was made during the current pass through the unsorted portion of the array.

If no swaps occurred, that means the unsorted part of the array is already in the correct order. And since the sorted part is, by definition, already sorted — it follows that the entire array is sorted.

In the methods sortNonDescending2 and sortNonAscending2, this improvement is implemented.

A boolean variable swapPerformed is introduced, which is set to false before each pass through the array (before entering the inner FOR loop) — indicating that no swaps have yet been made.

If at least one swap is made during the execution of the inner FOR loop, it means the array is not yet sorted, and swapPerformed is set to true.

After each pass (when the inner FOR loop finishes), we check* if there were any swaps:*

If not (i.e., swapPerformed == false), then we can confidently conclude that the array is fully sorted, and the entire algorithm is terminated early using the break statement, which exits the outer FOR loop.

The “Selection sort” algorithm is also one of the simpler sorting algorithms, which is somewhat better than the “Bubble sort” algorithm. Here too, the name of the algorithm reflects its basic idea: that in the first pass through the array we search the array, find, let’s say, the largest element and place it at the last position; in the second pass we search and find the second-largest element and place it at the second-to-last position; in the third pass we find the third-largest element, and so on. In doing so, placing the largest element at the last position, the second largest at the second-to-last, and so on is done by swapping the value of the largest element with the last element of the array, the second largest with the second-to-last element, and so forth.

After as many searches (passes) as there are elements in the array minus one, the elements will be placed at the end of the array in order from largest to smallest (when viewed from the end of the array towards the beginning). This means that here as well, the sorted part of the array is located at the end of the array (and grows toward the beginning), while the unsorted part is at the beginning (and shrinks toward the beginning). If we want the reverse order, we search for the smallest element instead of the largest in each pass.

The difference from the Bubble sort algorithm is that we don’t compare every two adjacent elements (and swap them whenever needed), but instead search the array, find the current largest element, and move it to the end of the unsorted part. This means only one value swap is done in each pass through the array. The largest elements don’t “float” toward the end of the array (like bubbles) through repeated swapping with the next element. Instead, a search (selection) for the largest element is performed, and it is placed at the end by swapping it with the last element of the unsorted portion.

In a way, this algorithm can be interpreted as repeating the algorithm for finding the maximum (or minimum). That is, finding and placing the maximum (or minimum) at the end of the array, then repeating that procedure on the remaining array (unsorted part) until all elements are processed.

For example, if we have an array that needs to be sorted in ascending order, the sequence of steps is as follows:

In this example, two passes through the array were enough to sort it in ascending order. Further passes through the array are not needed, and the sorting process can be stopped.

As with the Bubble sort algorithm, this is not always the case – the number of passes through the array required to sort it varies and depends on the initial arrangement of elements. The number of elements minus one is the maximum number of passes needed for Selection sort to sort the array.

In this algorithm too, each pass goes only through the unsorted part of the array – meaning in each subsequent pass, one fewer element is processed than in the previous pass. In the first pass, all elements are processed, in the second, all except the last, in the third, all except the last and the second-to-last, and so on.

The Selection sort algorithm can also be improved by stopping as soon as it is determined that the array is already sorted. However, this optimization is not easy to implement, especially if the array contains duplicate values, so it will not be shown in this collection.

In the following examples, therefore, the version of this algorithm presented is the one that always performs the maximum number of passes through the array.

Example 2

Create a class ProductPrices2 that has:

• An attribute prices which represents an array of prices for multiple products (e.g., 123).
• An attribute counter which represents a counter of elements, i.e., the number of actually entered prices in the array.
• A constructor that takes the total number of prices as a parameter and initializes the prices array with that capacity.
• A method enterPrice which takes a new price as a parameter and inserts it into the array at the first available position.If the entered price is less than zero or if there is no space in the array, the method simply prints the message “ERROR” to the screen.
• A method sortNonDescending which, using the Selection sort algorithm, sorts all entered prices in non-descending order.
• A method sortNonAscending which, using the Selection sort algorithm, sorts all entered prices in non-ascending order.
• *A method print which prints all elements of
• the array in a single line on the screen.*

Create a class TestProductPrices2 which, in the main method, creates one object of class ProductPrices2 that ca contain a maximum of eight prices. Enter five prices of your choice. Sort the array of prices in non-descending order, print the array, then sort it in non-ascending order and again print the array.

In the method sortNonDescending, an implementation of the Selection sort algorithm in Java is shown. The outer FOR loop repeats passes through the array (at most counter - 1 passes), while the inner FOR loop actually searches for the maximum in the unsorted part of the array in a single pass.

Finding the maximum is an algorithm that has already been covered in previous lessons, so it can be said that here it is slightly modified because in the auxiliary variable maxIndex, we do not store the maximum value, but rather the position (index) of that value in the array. This is done because we will later swap that element with the last element of the unsorted part of the array. If we stored only the value, we would have to find its position again before the swap.

The counter of the inner FOR loop goes from 0 to counter - i - 1 so that in each subsequent pass, elements at the end of the array that have already been sorted are skipped – just like in the Bubble sort algorithm.

When the maximum is found using the inner FOR loop, its position is stored in the variable maxIndex, and then the value of that element is simply swapped with the value of the last element in the unsorted part of the array.

In the method sortNonAscending, a nearly identical algorithm is given, which sorts the array in non-ascending order, with the difference being that the minimum is searched for instead of the maximum in each pass through the unsorted part of the array.

Previous examples for Bubble sort and Selection sort involve using the element counter (counter). In cases where the array is always used at full capacity, it is sufficient to replace the counter variable with the array’s capacity, i.e., length, in the algorithms.

Some of the most common errors related to algorithms for adding values to arrays which are not syntax errors, but affect the program’s behavior are:

• Using the wrong comparison operator for comparing array elements (e.g., < instead of > – or vice versa), which results in the opposite order being produced (e.g., non-descending instead of non-ascending – or vice versa):

Instead of the correct version:

• Incorrect use of the auxiliary variable during the swap of array element values. A mistake here can be made by simply changing the order of the following three lines – which results in the same value being in all three variables:

Instead of the correct version (first element into tmp, second into first, tmp into second):

• Not using an auxiliary variable when swapping array element values. The same value ends up being written into both elements:

Instead of the correct version (first element into tmp, second into first, tmp into second):