Difference between revisions of "W1301 Arrays"

From Coder Merlin
m (→‎Quiz: editorial review)
(24 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Background ==
== Background ==
{{KeyConcepts|
{{KeyConcepts|
* '''Abstract Data Types''', or '''ADTs''', represent ''models'' for '''data structures'''.  The model specifies the required behavior (semantics) of the type, such as supported operations and the impact of those operations on the type.
* {{GlossaryReference|Abstract Data Types|Abstract Data Types}}, or '''ADTs''', represent ''models'' for '''data structures'''.  The model specifies the required behavior (semantics) of the type, such as supported operations and the effect of those operations on the type.
* The model specifies the required semantics (behavior) of the type, such as supported operations and the impact of those operations on the type.
* The model specifies the required semantics (behavior) of the type, such as supported operations and the effect of those operations on the type.
* ADTs are theoretical and are used in designing and analyzing algorithms and data structures. Compilers, however, may implement specific data structures fulfilling most, if not all, of the requirements of an ADT.
* ADTs are theoretical and are used in designing and analyzing algorithms and data structures. Compilers, however, might implement specific data structures fulfilling most of, if not all, the requirements of an ADT.
}}
}}


== Arrays ==
== Arrays ==
The '''Array Data Structure''' is a ''collection of elements'' each of which can be identified by an index. An array is stored so that the position of the element in memory (or other storage) can be easily calculated based only on the index. For example, consider an array of integers:<br/>
The {{GlossaryReference|Array|array data structure}} is a ''collection of elements'' each of which can be identified by an index. An array is stored so that the position of the element in memory (or other storage) can be easily calculated using only the index. For example, consider an array of integers:<br/>
[[File:Array-Overview.png|frame|link=|Array Data Structure]]
[[File:Array-Overview.png|frame|link=|Array Data Structure]]
<br/>
<br/>


In this array, each integer requires thirty-two bits (or four bytes). Thus, there are four bytes from the beginning of each element to the beginning of the next element. This allows us to calculate the position of an integer in this array by adding the product of the element index (starting from zero) and the bytes required per element to the ''foundation address''. In this case, the formula would be:
In this array, each integer requires 32 bits (or 4 bytes). Thus, four bytes exist from the beginning of each element to the beginning of the next element. This allows us to calculate the position of an integer in this array by adding the product of the element index (starting from zero) and the bytes required per element to the ''foundation address''. In this case, the formula would be:
<pre>0x0800 + (4 * index)</pre>
<pre>0x0800 + (4 * index)</pre>
Arrays are very common data structures and used in almost every program. CPUs generally enable assembly language programs to easily work with arrays. As an example, a '''base plus index''' mode enables a program to access an element by storing the foundation address in the base register and specifying the index (scaled by the size of each element) in the index register.
Arrays are very common data structures and are used in almost every program. CPUs generally enable assembly language programs to easily work with arrays. As an example, a '''base plus index''' mode enables a program to access an element by storing the foundation address in the base register and specifying the index (scaled by the size of each element) in the index register.


== ADT Properties ==
== ADT Properties ==
As an abstract data type, arrays are:
As an abstract data type, arrays are:
* A '''collection''' type, meaning that a single variable conceptually “contains” many elements
* A '''collection''' type, meaning that one variable conceptually “contains” many elements
* Each item in the data structure is termed an '''element'''
* Each item in the data structure is called an '''element'''
* The collection is '''ordered''', that is, the order of the elements is maintained
* The collection is '''ordered''', that is, the order of the elements is maintained
* Elements can be accessed '''randomly''', that is, there is no need to access elements in any particular order
* Elements can be accessed '''randomly''', that is, there is no need to access elements in a certain order
* The array is '''homogeneous''', that is, all of the elements are of the same type

* The array is '''homogeneous''', that is, all the elements are of the same type



== One-Dimensional Array Declaration ==
== One-Dimensional Array Declaration ==
The first step in using a '''one-dimensional array''' is to declare the array following the outlined syntax below.
The first step in using a '''one-dimensional array''' is to declare the array by using the outlined syntax below.


The following is a syntax template you can use of a one-dimensional array declaration:
The following is a syntax template you can use for a one-dimensional array declaration:
<pre>Data_Type Array_Name [Const_Int_Expression];</pre>
<pre>Data_Type Array_Name [Const_Int_Expression];</pre>


Reference information regarding array declaration:
Reference information for the array declaration:


* '''Data_Type''' defines what type of data is stored in the array. Commonly used array types within a one-dimensional array are Int, String, Char, Bool, Var.
* '''Data_Type''' defines what type of data is stored in the array. Commonly used array types in a one-dimensional array are Int, String, Char, Bool, Var.


* '''Array_Name''' defines the name of the array in the array declaration.
* '''Array_Name''' defines the name of the array in the array declaration.
Line 37: Line 37:
* '''Const_Int_Expression''' defines the array size. This value must be greater than zero. When an array is defined as size 'n', the array indices will range from 0 to n-1.  
* '''Const_Int_Expression''' defines the array size. This value must be greater than zero. When an array is defined as size 'n', the array indices will range from 0 to n-1.  


Arrays can also be created of a determined size and initialized with an initial value with the following convention:
You can create an array with a determined size and initialize it with a value using the below convention:


<pre> var initailizedArray = [ArrayType](count: NumbeOfElements, repeatedValue: InitialValue) </pre>
<pre> var initailizedArray = [ArrayType](count: NumbeOfElements, repeatedValue: InitialValue) </pre>


For instance, the array can be set to hold four elements with each element of the array holding an initial value of zero with the following array definition.
For example, the array can be set to hold four elements, with each element of the array holding an initial value of zero with this array definition:


<syntaxhighlight lang="SWIFT">
<syntaxhighlight lang="SWIFT">
Line 48: Line 48:


=== Fun Use Case ===
=== Fun Use Case ===
Arrays in Swift can store elements of any type, known as heterogeneous collections. To define an array in swift to store elements of any type, simply specify the variable as [Any].
Arrays in Swift can store elements of any type; these are known as heterogeneous collections. To define an array in Swift to store elements of any type, simply specify the variable as [Any].


'''Example'''
'''Example'''
Line 55: Line 55:
</syntaxhighlight>
</syntaxhighlight>


Once you are ready to print the contents of the array simply use the following:
To print the contents of the array, use the following statement:


<syntaxhighlight lang="SWIFT">
<syntaxhighlight lang="SWIFT">
Line 61: Line 61:
</syntaxhighlight>
</syntaxhighlight>


Resulting in the following:
This results in the following:
<pre>The Array: [1, 2.4, "abc", "def", 4] </pre>
<pre>The Array: [1, 2.4, "abc", "def", 4] </pre>


Line 81: Line 81:
</syntaxhighlight>
</syntaxhighlight>


One can determine if an array is empty using the '''isEmpty''' property and determine the number of items in the array using the count property:
You can determine if an array is empty using the '''isEmpty''' property. And you can determine the number of items in the array using the count property:
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
     if !states.isEmpty {
     if !states.isEmpty {
Line 88: Line 88:
</syntaxhighlight>
</syntaxhighlight>


A shortcut to access the first and last elements makes use of the '''first''' and '''last''' property which return a type of Element? (optional Element).
A shortcut to access the first and last elements uses the '''first''' and '''last''' property that return a type of Element? (optional Element).
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
     print("The first state in the array is \(states.first!)")
     print("The first state in the array is \(states.first!)")
Line 94: Line 94:
</syntaxhighlight>
</syntaxhighlight>


Adding a single element to the end of an array can be accomplished with '''append''':  
Adding one element to the end of an array can be done with '''append''':  
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
     states.append("New York")
     states.append("New York")
</syntaxhighlight>
</syntaxhighlight>
   
   
We can also '''insert''' an element at a specific index in the array:
You can also '''insert''' an element at a specific index in the array:
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
     states.insert("New Jersey", at:1)
     states.insert("New Jersey", at:1)
</syntaxhighlight>
</syntaxhighlight>


This shifts the other elements in the array to "make room" for the new element.


This shifts the other elements in the array to “make room” for the new element.<br/>
Finally, elements can be removed with the '''remove''' method:
Finally, elements can be removed with the '''remove''' method:
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
Line 112: Line 112:


== Traversing One-Dimensional Arrays ==
== Traversing One-Dimensional Arrays ==
Traversing is another key operation used when working with one-dimensional arrays. Traversing - also known as looping - is a great way to print specific items within an array, or iterate through a one-dimensional array in a method.  
Traversing is another key operation used when working with one-dimensional arrays. Traversing—also known as looping—is a great way to print specific items in an array, or iterate through a one-dimensional array in a method.


Let's use the simple example of iterating through a small array of state capitals to show the benefits of traversing a one-dimensional array.
Let's use a simple example of iterating through a small array of state capitals to show the benefits of traversing a one-dimensional array.


We'll start by defining the array:
Start by defining the array:
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
let statecapitals = [
let statecapitals = [
     "Arizona": "Phoenix",
     "Arizona": "Phoenix",
     "California": "Sacremento",
     "California": "Sacramento",
     "Florida": "Tallahassee"
     "Florida": "Tallahassee"
     "Texas": "Austin"
     "Texas": "Austin"
Line 126: Line 126:
</syntaxhighlight>
</syntaxhighlight>


Now that the array is defined, let's use a '''for loop''' to iterate through the array and print each state and the associated state capital.
Now that the array is defined, let's use a '''for loop''' to iterate through it and print each state and its capital.


<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
Line 134: Line 134:
</syntaxhighlight>
</syntaxhighlight>


When traversing a one-dimensional array it may be important to access or print array items starting at the end of the list. To achieve this, use the swift method '''reversed()'''.
When traversing a one-dimensional array, it might be important to access or print array items starting at the end of the list. To achieve this, use the Swift method '''reversed()'''.


<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
Line 145: Line 145:
<quiz shuffleanswers=true display=simple>
<quiz shuffleanswers=true display=simple>
{
{
The best way to traverse over an array is by using an "if" statement?
True or False: The best way to traverse over an array is by using an "if" statement.
|type="()"}
|type="()"}


Line 152: Line 152:


{
{
How to define an array that supports multiple types:
How do you define an array that supports multiple types?
|type="()"}
|type="()"}


Line 161: Line 161:


{
{
The sort() method creates a newly sorted array
True or False: The sort() method creates a newly sorted array.
|type="()"}
|type="()"}


Line 176: Line 176:
- All three
- All three


{
Select the proper declaration for the for loop. The result should read "The number is ___" let count = 1...10
|type="()"}
- for count in number { print("Number is \(number)")}
+ for number in count { print("Number is \(number)")}
- for count in number { print("Number is (number)")}
- for number in count { print("Number is (number)")}
</quiz>
</quiz>


== Searching a One-Dimensional Array ==
== Searching a One-Dimensional Array ==
Oftentimes, you'll need to find a specific item in an array or determine if an object exists within an array. To find elements within an array the '''contains()''' method can be very useful. Let's take a look at how '''contains()''' can be applied.
Often, you will need to find a specific item in an array or determine if an object exists within an array. To find elements in an array, the '''contains()''' method can be very useful. Let's take a look at how '''contains()''' can be applied.


<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
Line 200: Line 192:
</syntaxhighlight>
</syntaxhighlight>


Once you've determined the object to be in the array, you can get the element with the following function.
Once you've determined the object is in the array, you can get the element with the following function:


<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
Line 230: Line 222:
- func return
- func return


{
How do you determine if a value in a var type array is even?
|type="()"}
- Use the even method
+ Iterate using a for loop and divide by the modulo operator %.
- Use the isEven method
- Return all values and sort


{
{
There's no way to find the last element in an array
True or False: There's no way to find the last element in an array
|type="()"}
|type="()"}


- true
- True
+ false
+ False
</quiz>
</quiz>


== Filtering One-Dimensional Arrays ==
== Filtering One-Dimensional Arrays ==


When you're working with a one-dimensional array, it may be useful to remove specific elements that aren't needed from the array. Fortunately, removing elements from an array is quite straightforward. Simply by using the '''filter()''' method, one can filter out specific elements within an array. Let's take a look at how it works.  
When working with a one-dimensional array, it can be useful to remove specific elements that aren't needed from the array. Fortunately, this is straightforward. To filter out specific elements in an array, use the '''filter()''' method. Let's take a look at how it works.


<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
Line 250: Line 250:
</syntaxhighlight>
</syntaxhighlight>


There are some key points to consider when filtering an array. First and foremost, the '''filter(isIncluded:)''' method in swift takes a closure for each element in the source Array that is enumerated over. Further, when you apply a filter on an array the original array is not modified. If this method returns an element, this element will be included in a new filtered array. In this case, '''filter(isIncluded:)''' creates a new array with only the elements you want. However, if the method returns false, the element is effectively filtered out and not included in this new array.  
You should consider some key points when filtering an array. First and foremost, the '''filter(isIncluded:)''' method in Swift takes a closure for each element in the source array. Further, when you apply a filter on an array, the original array is not modified. If this method returns an element, this element is included in a new filtered array. In this case, '''filter(isIncluded:)''' creates a new array with only the elements you want. However, if the method returns false, the element is effectively filtered out and not included in this new array.
 
== Quiz ==
<quiz shuffleanswers=true display=simple>
{
True or False: The filter array lets you find matching elements in an array.
|type="()"}
 
- True
+ False
 
{
What is the proper declaration for the filter method?
|type="()"}
 
- char filter(_ isIncluded: (Self.Element) throws -> Bool) rethrows -> [Self.Element]
- bool filter(_ isIncluded: (Self.Element) throws -> Bool) rethrows -> [Self.Element]
+ func filter(_ isIncluded: (Self.Element) throws -> Bool) rethrows -> [Self.Element]
- var filter(_ isIncluded: (Self.Element) throws -> Bool) rethrows -> [Self.Element]
 
{
True or False: When you apply the filter method, the original array is not modified.
Instead, filter(isIncluded) creates a new array with only the element you're searching for.
|type="()"}
 
+ True
- False
 
{
In an array called words, what is the proper way to find words that are 4 letters or longer?
|type="()"}
 
+ let filtered = words.filter { word in return word.count >= 3
- let filtered = words.filter { word in return word.count >= 4
- let filtered = filter.words { word in return word.count >= 3
- let filtered = filter.words { word in return word.count >= 4
 
</quiz>


== Sorting One-Dimensional Arrays ==
== Sorting One-Dimensional Arrays ==
When working with arrays in Swift, users can sort elements using both the '''sort()''' and the '''sorted()''' methods. Both these methods are effective for sorting arrays, however, they are slightly different in what they return. With '''sort()''', the array is sorted in place, meaning the original array is sorted, whereas, with '''sorted()''' the original array elements are copied to a new array in a sorted orientation.  
When working with arrays in Swift, you can sort elements using two methods: '''sort()''' and '''sorted()'''. Both are effective for sorting arrays; however, they are slightly different in what they return. With '''sort()''', the array is sorted in place, meaning the original array is sorted. With '''sorted()''', the original array elements are copied to a new array with the new sorting. Let's take a look at how you can use these methods.
Let's take a look at how these methods can be used.  


When working with a fairly simple array of a single type, the easiest way to sort this array is with the '''sort()'''. In this following example the array is sorted in palce.  
When working with a simple array of a single type, the easiest way to sort the array is with the '''sort()''' method. In this example, the array is sorted in place.  
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
var capitals = ["Phoenix", "Sacramento", "Austin", "Tallahassee", "Santa Fe"]
var capitals = ["Phoenix", "Sacramento", "Austin", "Tallahassee", "Santa Fe"]
Line 262: Line 298:
</syntaxhighlight>
</syntaxhighlight>


If you'd rather work with a copy of the original array that is sorted, using the '''sorted()''' method will be best. Let's take a look at the subtle difference in using this method.
To work with a copy of the original array that is sorted, use the '''sorted()''' method. Let's take a look at the subtle difference in using this method.
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
struct Capitals {
struct Capitals {
Line 281: Line 317:
}
}


//Once the custom struct is created, we can sort the struct copying the elements of capitalnames to sortedCapitals in a sorted manner.
//Once the custom struct is created, we can sort the struct, copying the elements of capitalnames to sortedCapitals and sorted.


let sortedCapitals = capitalnames.sorted {
let sortedCapitals = capitalnames.sorted {
Line 287: Line 323:
}
}
</syntaxhighlight>
</syntaxhighlight>
== Quiz ==
<quiz shuffleanswers=true display=simple>
{
True or False: The sort() method creates a newly sorted array.
|type="()"}
- True
+ False
{
Create a new array named sortedUsers that is coped and sorted from the original array named users.
|type="()"}
+ let sortedUsers = users.sorted {$0.firstName < $1.firstName}
- let users = sortedUsers.sorted {$0.firstName < $1.firstName}
- struct sortedUsers = users.sorted {$0.firstName < $1.firstName}
- struct users = sortedUsers.sorted {$0.firstName < $1.firstName}
{
True or False: The sorted() method creates a newly sorted array.
|type="()"}
+ True
- False
{
What does the following return? mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows
|type="()"}
+ Sorts the collection in place, using the given predicate as the comparison between elements
- Sorts the collection in a new array, using the given predicate as the comparison between elements
- Sorts the collection in place, using the given predicate as the comparison between array sizes
- Sorts the collection in a new array, using the given predicate as the comparison between array sizes
</quiz>


== Mutating Method for One-Dimensional Arrays ==
== Mutating Method for One-Dimensional Arrays ==
When creating structs that have a variable defined as a constant, there are some limitations in how you can use or alter the struct. Specifically, users are unable to change the properties of the struct once these properties have been defined as constant.  
When creating structs that have a variable defined as a constant, some limitations apply in how you can use or alter the struct. Specifically, you may not change the properties of the struct once these properties have been defined as constant.


This can quickly become a challenge when users want to apply a different variable within that structure. This limitation may seem overly cautious, however, the intention behind it is to protect users from unintentionally misapplying variable declarations to a struct. Fortunately, there is the '''mutating func()''' that allows users to override the constant declaration in an array and change the property inside the method.
This can quickly become a challenge when you want to apply a different variable in that structure. This limitation might seem overly cautious; however, it protects you from unintentionally misapplying variable declarations to a struct. Fortunately, the '''mutating func()''' allows you to override the constant declaration in an array and change the property inside the method.
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
struct StateCapitals {
struct StateCapitals {
Line 302: Line 374:
//This defines the structure, embedded with the property inside the method that can be altered.
//This defines the structure, embedded with the property inside the method that can be altered.


//Now we can apply this mutating function in the following manner:
//Now we can apply this mutating function as follows:


var capitals = StateCapitals(name: "Phoenix")
var capitals = StateCapitals(name: "Phoenix")
Line 309: Line 381:


== Using the Reduce Method with One-Dimensional Arrays ==
== Using the Reduce Method with One-Dimensional Arrays ==
The '''Reduce()''' method combines all of the elements within an array and returns a single new value. Often, '''Reduce()''' is used to sum all of the integers or characters within an array.
The '''Reduce()''' method combines all the elements in an array and returns one new value. Often, '''Reduce()''' is used to sum all the integers or characters in an array.


The Swift declaration is as follows:
The Swift declaration is as follows:
Line 317: Line 389:
</syntaxhighlight>
</syntaxhighlight>


As seen above, the '''Reduce()'' function takes two arguments, the initial value and the closure.  
As seen above, the '''Reduce()''' function takes two arguments: the initial value and the closure.  
*The '''initial value''' stores the initial value. This argument can also store the '''value''' or '''result''' of returned by the closure.
*The '''initial value''' stores the initial value. This argument can also store the '''value''' or '''result''' of returned by the closure.
*The '''closure''' accepts two arguments, one is an initial value which is used to store the initial value or the value or and the next item in the iteration.
*The '''closure''' accepts two arguments. One is an initial value that is used to store the initial value or the value or and the next item in the iteration.
 
{{MerlinNoteFromEditor|Reviewing and rewriting the second sentence in the above "closure" bullet. It seems redundant and is confusing.}}




Line 334: Line 406:
''Note: Python does not have arrays; lists are used instead''
''Note: Python does not have arrays; lists are used instead''


A list can be instantiated using a series of literals. For example:
You can instantiate a list using a series of literals. For example:
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
oddNumbers = [1, 3, 5, 7, 9, 11]
oddNumbers = [1, 3, 5, 7, 9, 11]
Line 340: Line 412:
</syntaxhighlight>
</syntaxhighlight>


An empty list can be instantiated:
To instantiate an empty list:
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
emptyArray = []
emptyArray = []
Line 350: Line 422:
</syntaxhighlight>
</syntaxhighlight>


One can determine if a list is empty by checking its length:
You can determine if a list is empty by checking its length:
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
if len( states ) > 0:
if len( states ) > 0:
Line 356: Line 428:
</syntaxhighlight>
</syntaxhighlight>


or by simply using <code>if</code>:
or by using <code>if</code>:
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
if states:
if states:
Line 362: Line 434:
</syntaxhighlight>
</syntaxhighlight>


The last element of a list can be accessed by using <code>-1</code> as the index. The first element can be accessed by calling the negative length(e.g. <code>states[-len(states)]</code>)
You can access the last element of a list by using <code>-1</code> as the index. Access the first element by calling the negative length (e.g., <code>states[-len(states)]</code>)
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
print("The first state in the array is " + states[-len(states)])
print("The first state in the array is " + states[-len(states)])
Line 368: Line 440:
</syntaxhighlight>
</syntaxhighlight>


We can use indices to iterate over each element at a specific location in a list with a for loop:
To iterate over each element at a specific location in a list, use a for loop:
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
for i in range(0, len(states)):
for i in range(0, len(states)):
Line 374: Line 446:
</syntaxhighlight>
</syntaxhighlight>


A very easy way to iterate over all ''elements'' in a list makes use of a '''for loop''':
A very easy way to iterate over all ''elements'' in a list, is to use a '''for loop''':
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
for state in states:
for state in states:
Line 380: Line 452:
</syntaxhighlight>
</syntaxhighlight>


Adding a single element to the end of a list can be accomplished with '''append''':  
To add one element to the end of a list, use '''append''':  
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
states.append("New York")
states.append("New York")
</syntaxhighlight>
</syntaxhighlight>
   
   
We can also '''insert''' an element at a specific index in the list:
You can also '''insert''' an element at a specific index in the list:
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
states.insert(1,"New Jersey")
states.insert(1,"New Jersey")
</syntaxhighlight>
</syntaxhighlight>


This shifts the other elements in the list to “make room” for the new element.<br/>
This shifts the other elements in the list to "make room" for the new element.  
Finally, elements can be removed with the '''del''' keyword:
 
Finally, you can remove elements with the '''del''' keyword:
<syntaxhighlight lang="swift">
<syntaxhighlight lang="swift">
del states[2]
del states[2]
Line 404: Line 477:


== Quiz ==
== Quiz ==
{{MerlinNoteFromEditor|Addressing question 3: what is the question?}}
<quiz shuffleanswers=true display=simple>
<quiz shuffleanswers=true display=simple>
{
{
For the array:
For the array:
int stats[4];
int stats[4];
What is the range of the index?  
what is the range of the index?  
|type="()"}
|type="()"}


Line 417: Line 492:


{
{
Arrays can be passed as parameters to a method either by value or by reference.
True or False: Arrays can be passed as parameters to a method either by value or by reference.
|type="()"}
|type="()"}


Line 433: Line 508:


{
{
How to create a one-dimensional string array called holder?
How do you create a one-dimensional string array called holder?
|type="()"}
|type="()"}


Line 442: Line 517:


{
{
The first value of the array called holder can set to 50 in the following way?
How do you set the first value of the array called holder to 50?
|type="()"}
|type="()"}


Line 451: Line 526:


{
{
int [] holder = {1, 2, 3, 4, 5};
For the array: int [] holder = {1, 2, 3, 4, 5};  
How would you access the third element in holder?
how do you access the third element in the holder array?
|type="()"}
|type="()"}


Line 461: Line 536:


{
{
A method can return a value of type array.
True or False: A method can return a value of type array.
|type="()"}
|type="()"}



Revision as of 08:08, 9 January 2022

Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder

Background[edit]

Key ConceptsKeyConceptsIcon.png
  • Abstract Data Types, or ADTs, represent models for data structures. The model specifies the required behavior (semantics) of the type, such as supported operations and the effect of those operations on the type.
  • The model specifies the required semantics (behavior) of the type, such as supported operations and the effect of those operations on the type.
  • ADTs are theoretical and are used in designing and analyzing algorithms and data structures. Compilers, however, might implement specific data structures fulfilling most of, if not all, the requirements of an ADT.

Arrays[edit]

The array data structure is a collection of elements each of which can be identified by an index. An array is stored so that the position of the element in memory (or other storage) can be easily calculated using only the index. For example, consider an array of integers:

Array Data Structure


In this array, each integer requires 32 bits (or 4 bytes). Thus, four bytes exist from the beginning of each element to the beginning of the next element. This allows us to calculate the position of an integer in this array by adding the product of the element index (starting from zero) and the bytes required per element to the foundation address. In this case, the formula would be:

0x0800 + (4 * index)

Arrays are very common data structures and are used in almost every program. CPUs generally enable assembly language programs to easily work with arrays. As an example, a base plus index mode enables a program to access an element by storing the foundation address in the base register and specifying the index (scaled by the size of each element) in the index register.

ADT Properties[edit]

As an abstract data type, arrays are:

  • A collection type, meaning that one variable conceptually “contains” many elements
  • Each item in the data structure is called an element
  • The collection is ordered, that is, the order of the elements is maintained
  • Elements can be accessed randomly, that is, there is no need to access elements in a certain order
  • The array is homogeneous, that is, all the elements are of the same type


One-Dimensional Array Declaration[edit]

The first step in using a one-dimensional array is to declare the array by using the outlined syntax below.

The following is a syntax template you can use for a one-dimensional array declaration:

Data_Type Array_Name [Const_Int_Expression];

Reference information for the array declaration:

  • Data_Type defines what type of data is stored in the array. Commonly used array types in a one-dimensional array are Int, String, Char, Bool, Var.
  • Array_Name defines the name of the array in the array declaration.
  • Const_Int_Expression defines the array size. This value must be greater than zero. When an array is defined as size 'n', the array indices will range from 0 to n-1.

You can create an array with a determined size and initialize it with a value using the below convention:

 var initailizedArray = [ArrayType](count: NumbeOfElements, repeatedValue: InitialValue) 

For example, the array can be set to hold four elements, with each element of the array holding an initial value of zero with this array definition:

var holderArray = [Int](count: 4, repeatedValue: 0)

Fun Use Case[edit]

Arrays in Swift can store elements of any type; these are known as heterogeneous collections. To define an array in Swift to store elements of any type, simply specify the variable as [Any].

Example

var test = [1, 2.4, "abc", "def", 4] as [Any]

To print the contents of the array, use the following statement:

print("The Array: \(test)")

This results in the following:

The Array: [1, 2.4, "abc", "def", 4] 

Performing Operations on a One-Dimensional Array[edit]

An array can be instantiated using a series of literals. For example:

   let oddNumbers = [1, 3, 5, 7, 9, 11]
   var states = ["California", "Florida", "Texas"]

An empty array can be instantiated by explicitly specifying its type:

    var emptyDoubleArray = [Double]()

The first element of a non-empty array is accessed using an index or subscript of 0. For example:

    let firstState = states[0]

You can determine if an array is empty using the isEmpty property. And you can determine the number of items in the array using the count property:

    if !states.isEmpty {
        print("The array contains \(states.count) states.")
    }

A shortcut to access the first and last elements uses the first and last property that return a type of Element? (optional Element).

    print("The first state in the array is \(states.first!)")
    print("The last state in the array is \(states.last!)")

Adding one element to the end of an array can be done with append:

    states.append("New York")

You can also insert an element at a specific index in the array:

    states.insert("New Jersey", at:1)

This shifts the other elements in the array to "make room" for the new element.

Finally, elements can be removed with the remove method:

    states.remove(at: 2)

Traversing One-Dimensional Arrays[edit]

Traversing is another key operation used when working with one-dimensional arrays. Traversing—also known as looping—is a great way to print specific items in an array, or iterate through a one-dimensional array in a method.

Let's use a simple example of iterating through a small array of state capitals to show the benefits of traversing a one-dimensional array.

Start by defining the array:

let statecapitals = [
    "Arizona": "Phoenix",
    "California": "Sacramento",
    "Florida": "Tallahassee"
    "Texas": "Austin"
]

Now that the array is defined, let's use a for loop to iterate through it and print each state and its capital.

for statecapital in statecapitals {
    print("\(statecapital.value) is the state capital of\(statecapital.key)")
}

When traversing a one-dimensional array, it might be important to access or print array items starting at the end of the list. To achieve this, use the Swift method reversed().

for statecapital in statecapitals.reversed() {
    print("\(statecapitals.value) is the state capital \(statecapitals.key)")
}

Quiz[edit]

1 True or False: The best way to traverse over an array is by using an "if" statement.

False
True

2 How do you define an array that supports multiple types?

var holder = ["a", true, "hello", 1]
var holder: Any[] = ["a", false, "hello", 1]
char holder: Any[] = ["a", false, "hello", 1]
char holder = ["a", false, "hello", 1]

3 True or False: The sort() method creates a newly sorted array.

False
True

4 What does the enumerated() function return?

Both the item in the array and its position
All three
The size of the array
The position of the item in the array


Searching a One-Dimensional Array[edit]

Often, you will need to find a specific item in an array or determine if an object exists within an array. To find elements in an array, the contains() method can be very useful. Let's take a look at how contains() can be applied.

if statecapitals.contains(where: {$0.name == "Phoenix"}) {
print("\(statecapitals.key) exists")
   // Here, we're looking to see if the element name exists within the array.

} else {
print("\(statecapitals.key) does not exist in the array")
// If there is no "Phoenix" element in the array.
}

Once you've determined the object is in the array, you can get the element with the following function:

if let capital = statecapitals.first(where: {$0.name == "Phoenix"}) {
   // Now you can use capital as you wish
} else {
   // the capital could not be found.
}

Quiz[edit]

1 Select the proper declaration for the contains() method.

bool contains(_ element: Element) -> Bool
char contains(_ element: Element) -> Bool
func contains(_ element: Element) -> Bool
var contains(_ element: Element) -> Bool

2 What instance method is used to return the first element that satisfies a given predictive?

func contains()
func contains(where)
func return
func first()

3 How do you determine if a value in a var type array is even?

Use the isEven method
Return all values and sort
Iterate using a for loop and divide by the modulo operator %.
Use the even method

4 True or False: There's no way to find the last element in an array

False
True


Filtering One-Dimensional Arrays[edit]

When working with a one-dimensional array, it can be useful to remove specific elements that aren't needed from the array. Fortunately, this is straightforward. To filter out specific elements in an array, use the filter() method. Let's take a look at how it works.

let capitals = ["Phoenix", "Sacramento", "Austin", "Tallahassee", "Santa Fe"]
let filteredcapitals = capital.filter { word in
  return word.count >= 9
} // filtered is ["Sacramento", "Tallahassee"]

You should consider some key points when filtering an array. First and foremost, the filter(isIncluded:) method in Swift takes a closure for each element in the source array. Further, when you apply a filter on an array, the original array is not modified. If this method returns an element, this element is included in a new filtered array. In this case, filter(isIncluded:) creates a new array with only the elements you want. However, if the method returns false, the element is effectively filtered out and not included in this new array.

Quiz[edit]

1 True or False: The filter array lets you find matching elements in an array.

False
True

2 What is the proper declaration for the filter method?

func filter(_ isIncluded: (Self.Element) throws -> Bool) rethrows -> [Self.Element]
var filter(_ isIncluded: (Self.Element) throws -> Bool) rethrows -> [Self.Element]
bool filter(_ isIncluded: (Self.Element) throws -> Bool) rethrows -> [Self.Element]
char filter(_ isIncluded: (Self.Element) throws -> Bool) rethrows -> [Self.Element]

3 True or False: When you apply the filter method, the original array is not modified. Instead, filter(isIncluded) creates a new array with only the element you're searching for.

True
False

4 In an array called words, what is the proper way to find words that are 4 letters or longer?

let filtered = words.filter { word in return word.count >= 4
let filtered = filter.words { word in return word.count >= 3
let filtered = words.filter { word in return word.count >= 3
let filtered = filter.words { word in return word.count >= 4


Sorting One-Dimensional Arrays[edit]

When working with arrays in Swift, you can sort elements using two methods: sort() and sorted(). Both are effective for sorting arrays; however, they are slightly different in what they return. With sort(), the array is sorted in place, meaning the original array is sorted. With sorted(), the original array elements are copied to a new array with the new sorting. Let's take a look at how you can use these methods.

When working with a simple array of a single type, the easiest way to sort the array is with the sort() method. In this example, the array is sorted in place.

var capitals = ["Phoenix", "Sacramento", "Austin", "Tallahassee", "Santa Fe"]
capitals.sort()

To work with a copy of the original array that is sorted, use the sorted() method. Let's take a look at the subtle difference in using this method.

struct Capitals {
    var capitalnames: String
// creating a custom struct for holding capitals
}

var afewcapitals = [
    afewcapitals(capital: "Phoenix"),
    afewcapitals(capital: "Sacramento"),
    afewcapitals(capital: "Austin"),
    afewcapitals(capital: "Santa Fe"),
 
]

capitalnames.sort {
    $0.capital < $1.capital
}

//Once the custom struct is created, we can sort the struct, copying the elements of capitalnames to sortedCapitals and sorted.

let sortedCapitals = capitalnames.sorted {
    $0.firstName < $1.firstName
}

Quiz[edit]

1 True or False: The sort() method creates a newly sorted array.

True
False

2 Create a new array named sortedUsers that is coped and sorted from the original array named users.

struct users = sortedUsers.sorted {$0.firstName < $1.firstName}
let sortedUsers = users.sorted {$0.firstName < $1.firstName}
struct sortedUsers = users.sorted {$0.firstName < $1.firstName}
let users = sortedUsers.sorted {$0.firstName < $1.firstName}

3 True or False: The sorted() method creates a newly sorted array.

True
False

4 What does the following return? mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows

Sorts the collection in a new array, using the given predicate as the comparison between array sizes
Sorts the collection in place, using the given predicate as the comparison between elements
Sorts the collection in place, using the given predicate as the comparison between array sizes
Sorts the collection in a new array, using the given predicate as the comparison between elements


Mutating Method for One-Dimensional Arrays[edit]

When creating structs that have a variable defined as a constant, some limitations apply in how you can use or alter the struct. Specifically, you may not change the properties of the struct once these properties have been defined as constant.

This can quickly become a challenge when you want to apply a different variable in that structure. This limitation might seem overly cautious; however, it protects you from unintentionally misapplying variable declarations to a struct. Fortunately, the mutating func() allows you to override the constant declaration in an array and change the property inside the method.

struct StateCapitals {
    var capitals: String

    mutating func newtype() {
        Capitals = "Hold"
    }
}
//This defines the structure, embedded with the property inside the method that can be altered.

//Now we can apply this mutating function as follows:

var capitals = StateCapitals(name: "Phoenix")
capitals.newtype()

Using the Reduce Method with One-Dimensional Arrays[edit]

The Reduce() method combines all the elements in an array and returns one new value. Often, Reduce() is used to sum all the integers or characters in an array.

The Swift declaration is as follows:

func reduce<Result>(_ initialResult: Result, _ nextPartialResult: 
(Result, Element) throws -> Result) rethrows -> Result

As seen above, the Reduce() function takes two arguments: the initial value and the closure.

  • The initial value stores the initial value. This argument can also store the value or result of returned by the closure.
  • The closure accepts two arguments. One is an initial value that is used to store the initial value or the value or and the next item in the iteration.

 This article can be improved by:  Reviewing and rewriting the second sentence in the above "closure" bullet. It seems redundant and is confusing.


ComingSoonIcon.png
Coming Soon
  • Preconditions

Python

Python[edit]

Note: Python does not have arrays; lists are used instead

You can instantiate a list using a series of literals. For example:

oddNumbers = [1, 3, 5, 7, 9, 11]
states = ["California", "Florida", "Texas"]

To instantiate an empty list:

emptyArray = []

The first element of a non-empty list is accessed using an index or subscript of 0. For example:

firstState = states[0]

You can determine if a list is empty by checking its length:

if len( states ) > 0:
    print("The array contains " + str(len(states)) + " states.")

or by using if:

if states:
    print("The array contains " + str(len(states)) + " states.")

You can access the last element of a list by using -1 as the index. Access the first element by calling the negative length (e.g., states[-len(states)])

print("The first state in the array is " + states[-len(states)])
print("The last state in the array is " + states[-1])

To iterate over each element at a specific location in a list, use a for loop:

for i in range(0, len(states)):
    print(states[i])

A very easy way to iterate over all elements in a list, is to use a for loop:

for state in states:
    print("State: " + state)

To add one element to the end of a list, use append:

states.append("New York")

You can also insert an element at a specific index in the list:

states.insert(1,"New Jersey")

This shifts the other elements in the list to "make room" for the new element.

Finally, you can remove elements with the del keyword:

del states[2]

Exercises[edit]

ExercisesExercisesIcon.png
  •  M1301-10  Complete  Merlin Mission Manager  Mission M1301-10.

Quiz[edit]

 This article can be improved by:  Addressing question 3: what is the question?

1 For the array: int stats[4]; what is the range of the index?

0 to 5
1 to 6
0 to 3
0 to 4

2 True or False: Arrays can be passed as parameters to a method either by value or by reference.

True
False

3 int [] nums = {2, 3, 5, 8, 9, 11};

0,1,2,3
0,2,4,6
1,3,5,7
1,2,3,4

4 How do you create a one-dimensional string array called holder?

int holder = [String]()
var holder = [String]()
int holder = (String)()
var holder = (String)()

5 How do you set the first value of the array called holder to 50?

holder[one] = 50;
holder[1] = 50;
holder[zero] = 50;
holder[0] = 50;

6 For the array: int [] holder = {1, 2, 3, 4, 5}; how do you access the third element in the holder array?

holder[4]
holder[3]
holder(3)
holder(4)

7 True or False: A method can return a value of type array.

True
False

8 Which of the following statements outputs the fourth value in the holder array?

System.out.println(holder[4]);
System.out.println(holder[3]);
holder[3];
holder[3];

9 A one-dimensional array is an example of a structured data type.

False
True

10 What value is at index 1 in this array? String[] names = {"Michael", "Kobe", "Larry", "Magic"};

Michael
Kobe
Magic
Larry