Define Array:
An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number.
Types of Array:
There are three different kinds of arrays: indexed arrays, multidimensional arrays, and associative arrays.
1. Indexed Arrays
Indexed arrays store a series of one or more values. You can look up items by their position in the array, which you might have done in earlier sections. The first index is always the number 0, and the index increments by one for each subsequent element that you add to the array.
2. Multidimensional Arrays
Multidimensional arrays are an extension of 2-D matrices and use additional subscripts for indexing.
A 3-D array, for example, uses three subscripts. The first two are just like a matrix, but the third dimension represents pages or sheets of elements.
3. Associative Arrays
Associative arrays use keys instead of a numeric index to organize stored values. Each key is a unique string, and it’s associated with and used to access one value. That value can be a data type such as Number, Array, Object, and so on. When you create code to find a value that’s associated with a key, you’re indexing or performing a lookup, which is the most typical reason for using an associative array
Define the concept of Sorting in Array:
Sorting an array means to arrange the elements in the array in a certain order. Various algorithms have been designed that sort the array using different methods.
The simplest array-sorting algorithm is called a bubble sort, and it also is the slowest.
A selection sort uses an algorithm that performs array sorting in a slightly more efficient manner than a bubble sort but still requires multiple iterations through the array.
A method of array sorting that can be efficient but sometimes complex to implement is known as a quicksort.
One factor that can affect an array-sorting algorithm is the means by which the data is tested for equivalency.
Sorted Array:
A sorted array is an array that is organized in a specific order (alphabetic, chronological, ordinal, cardinal order).
Unsorted Array:
An unsorted array is one that is not organized in any specific order.
Why is processing a sorted array faster than processing an unsorted array?
Example:
import java.util.Arrays;
import java.util.Random;
public class Main
{
public static void main(String[] args)
{
// Generate data
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
data[c] = rnd.nextInt() % 256;
// !!! With this, the next loop runs faster
Arrays.sort(data);
// Test
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
for (int c = 0; c < arraySize; ++c)
{ // Primary loop
if (data[c] >= 128)
sum += data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}
Branch Prediction
With a sorted array, the condition data >= 128 is first false for a streak of values, then becomes true for all later values. That’s easy to predict. With an unsorted array, you pay for the branching cost.
The reason why performance improves drastically when the data is sorted is that the branch prediction penalty is removed.
Now, if we look at the code,
if (data[c] >= 128)
sum += data[c];
we can find that the meaning of this particular if... else... branch is to add something when a condition is satisfied. This type of branch can be easily transformed into a conditional move statement, which would be compiled into a conditional move instruction: cmovl, in an x86 system. The branch and thus the potential branch prediction penalty is removed.
In C, thus C++, the statement, which would compile directly (without any optimization) into the conditional move instruction in x86, is the ternary operator ... ? ... : .... So we rewrite the above statement into an equivalent one:
sum += data[c] >=128 ? data[c] : 0;
Drop your query!