DSA Arrays
Arrays
A data structure called an array is used to hold numerous elements.
Numerous algorithms make use of arrays.
For instance, as the animation below illustrates, an algorithm can be used to search through an array and discover the lowest value:
------ IMAGE MUKAVI -----
An array in Python can be made in this way:
my_array = [7, 12, 9, 4, 11]
Note: This Python code creates a Python ‘list’ data type, but for the purposes of this lesson, it can be used in the same manner as an array. Find out more about lists in Python here.
Because arrays are indexed, every element in an array has an index, which is a number that indicates the element’s location within the array. The initial element in an array can be accessed at index 0 in the three programming languages covered in this tutorial: Python, Java, and C.
The first array element (value 7) is written to the console using index 0 in the following Python code:
Example
Python:
my_array = [7, 12, 9, 4, 11]
print( my_array[0] )
Algorithm: Find The Lowest Value in an Array
Let’s use the array data structure to develop our first algorithm.
The method for locating the lowest integer in an array is shown below.
How it works:
1.Go through the values in the array one by one.
2.Check if the current value is the lowest so far, and if it is, store it.
3.After looking at all the values, the stored value will be the lowest of all values in the array.
To demonstrate how the algorithm for determining the lowest value operates, try the simulation below (the animation is the same as the one on the top of this page):
----- IMAGE MUKAVI -----
Similar to the last simulation, this one likewise determines the lowest value in an array. However, this time, we can observe the process by which the values within the array are compared in order to determine the lowest value:
----- IMAGE MUKAVI -----
Implementation
Writing the method as a step-by-step procedure is usually a good idea before implementing it using a real programming language.
The method will be simpler to implement later if it can be expressed in a language that is halfway between human and programming language. This is because we won’t become bogged down in the intricate nuances of programming language syntax.
1.Create a variable ‘minVal’ and set it equal to the first value of the array.
2.Go through every element in the array.
3.If the current element has a lower value than ‘minVal’, update ‘minVal’ to this value.
4.After looking at all the elements in the array, the ‘minVal’ variable now contains the lowest value.
If you’d want, you may alternatively express the algorithm like this, which is more akin to a programming language:
Variable ‘minVal’ = array[0]
For each element in the array
If current element < minVal
minVal = current element
Note: ‘Pseudocode’ refers to the two detailed explanations of the algorithm that we have published above. Pseudocode is a description of a program written in a language halfway between English and computer languages.
It is considerably simpler to put the algorithm into practice in a particular programming language once it has been documented:
Example
Python:
my_array = [7, 12, 9, 4, 11]
minVal = my_array[0] # Step 1
for i in my_array: # Step 2
if i < minVal: # Step 3
minVal = i
print('Lowest value: ',minVal) # Step 4
Algorithm Time Complexity
When investigating algorithms, we frequently consider the algorithm’s running time in relation to the size of the data set.
The algorithm’s execution time in the aforementioned example is proportionate, or linear, to the size of the data collection. This is so that in order to determine the lowest value, the algorithm only needs to visit each array element once. Since the array contains five values, the loop needs to execute five times. Additionally, the loop would need to execute 1000 times if the array had 1000 values.
To illustrate the relationship between the size of the array and the number of comparison operations required to locate the lowest value, try the simulation below.
For a more detailed description of time complexity, refer to this page.
The temporal complexity of each algorithm in this lesson will be discussed.
