# Lesson #15. Arrays (slices, Sorting algorithms, Lists)

Дата изменения: 4 июля 2023

## Theory: slices, Sorting algorithms

Lection in pdf format

+ and * operations for arrays
• a + b – concatenation of two arrays into result array
• a * N – concatenation of N copies of a into result array
• ### Slices

• Array slice is a subarray of original array
• Slices are read-only and cannot be assigned values.
• The slice type is the same as the array.
• Slices work with arrays, strings, and lists.
• It has one of two forms: a[x:y] or a[x:y:step]. Expressions x and y can be omitted.
• Examples:

begin var a := Arr(0,1,2,3,4,5,6,7,8,9); println(a[:4]); // 0 1 2 3 println(a[4:]); // 4 5 6 7 8 9 println(a[:a.Length-1]); // 0 1 2 3 4 5 6 7 8 println(a[:]); // 0 1 2 3 4 5 6 7 8 9 (copy of a) println(a[::2]); // 0 2 4 6 8 println(a[1::2]); // 1 3 5 7 9 println(a[4:1:-1]); // 4 3 2 println(a[::-1]); // 9 8 7 6 5 4 3 2 1 0 (reverse of a) end.

### Array sorting algorithms

Selection sort
• this algorithm iterates over the array over and over, moving one value to the correct position
• it selects the smallest unsorted value
• so, at the next iteration, we will find the minimum in the array after the current element and change it with it, if necessary. Thus, after the i-th iteration, the first i elements will stay in their places.
• the sorted portion of the array is at the beginning
• 1 2 3 4 5 6 7 8 9 10 11 procedure SelectionSort(a: array of integer); begin for var i := 0 to a.High-1 do begin var (min,imin) := (a[i],i); for var j := i + 1 to a.High do if a[j] < min then (min,imin) := (a[j],j); Swap(a[imin],a[i]); end; end;

Bubble sort
• Let’s iterate over the array from left to right.
• If the current element is greater than the next one, we swap them.
• We do this until the array is sorted.
• Note that after the first iteration, the largest element will be at the end of the array, in the correct place.
• After two iterations, the two largest items will be in the correct place, and so on.
• 1 2 3 4 5 6 7 procedure BubbleSort(a: array of integer); begin for var i := 0 to a.High-1 do for var j := a.High downto i+1 do if a[j] < a[j-1] then Swap(a[j], a[j-1]); end;
Insertion sort

The Insertion sort algorithm iterates through the elements of the array one at a time, and places each new taken element in a suitable place among the previously ordered elements.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 procedure SortByInsert(a: array of integer); begin for var i:=1 to a.High do begin var x := a[i]; var j := i - 1; while (j >= 0) and (x < a[j]) do begin a[j+1] := a[j]; j -= 1; end; a[j+1] := x; end; end;
Standard sort
Sort(a); SortByDescending(a);

### List type

List definition

var l := new List<integer>; // l.Count = 0

To add an element to the end of a list:

l.Add(8); // or: l += 8;

Loop over the list:

for var i:=0 to l.Count-1 do Print(l[i]); foreach var x in l do Print(x);

List fill:

var l := Lst(5,2,3);

Methods

l.Insert(ind,x); // insert x by index ind l.RemoveAt(ind); // delete element by index ind l.RemoveRange(ind,count) // delete a range of elements l.RemoveAll(x -> x.IsOdd); // delete elements by condition l.IndexOf(3); // index of first element or -1 l.FindIndex(x -> x > 4); // index of first element or -1 l.Clear; l.Reverse; l.Sort;

### Slices

Lab 1:
To do: an array A of size N and an integer K (1 <= K <= N) are given. Print its elements with ordinal numbers (i.e. indexes) that are multiples of K (i.e. devisable by K):

Ak, A2 * k, A3 * k ...

Do not use the if statement.

✍ Algorithm:

begin var n:=ReadInteger('how many elements'); var a:=ReadArrReal(n); var k:=ReadInteger('K='); a[k-1 : : k].Print; end.
{0.2 points} Task 1:

To do: An array of size N is given. Print its elements in reverse order.

The expected output:

how many elements
>> 10
array:
25 5 68 42 48 32 100 77 50 47
result:
47 50 77 100 32 48 42 68 5 25


[Program name: 14task-01.pas]

{0.3 points} Task 2:

To do: An array A of size N is given (N is an even number). Display its elements with even ordinal numbers in ascending order of ordinal numbers:

а2, а4, а6, ... аn

Do not use the conditional operator.

The expected output:

>>10
64 64 21 72 22 82 62 50 30 25
64 72 82 50 25


[Program name: 14task-02.pas]

{0.3 points} Task 3:

To do: An array A of size N is given (N is an odd number). Display its elements with odd ordinal numbers, i.e. in descending order of ordinal numbers:

аn, аn-2, аn-4, ... а1

Do not use the conditional operator.

The expected output:

>>9
array: 89 67 32 43 49 67 93 75 31
result: 31 93 49 32 89


[Program name: 14task-03.pas]

Lab 2:

To do: An array A of size N is given. Using slices operations and the + operation for arrays, get an array containing first the elements with even ordinal numbers(in ascending order of ordinal numbers), and then — elements with odd ordinal numbers (also in ascending order of ordinal numbers):

a2, a4, a6, ... a1, a3, a5 ...

Do not use conditional operator.

The expected output:

how many elements
>> 9
4 96 8 94 14 80 93 49 6
96 94 80 49 4 8 14 93 6


✍ Algorithm:

begin var n:=ReadInteger('how many elements'); var a:=arrRandomInteger(n); a.Println; var slice:=a[1::2]+a[::2]; slice.Print end.
{0.3 points} Task 4:

To do: An array A of size N is given (N is odd number). Using slices operations and the + operation for arrays, get an array containing first its elements with odd indexes (in ascending order of their ordinal numbers), and then — elements with even indexes (in descending order of ordinal numbers). Create a slice to store a concatenation of those two slices:

a2, a4, a6, ..., a7, a5, a3, a1

Do not use conditional operator.

The expected output:

>>9
array: 80 81 71 37 55 78 26 33 53
result: 81 37 78 33 53 26 55 71 80


[Program name: 14task-04.pas]

Lab 3:

To do: An array of size N and integers K and L (1 <= K <= L <= N) are given. Find the arithmetic mean (average) of the elements of an array with ordinal numbers from K to L inclusive.

The expected output:

>>10
29 2 97 35 55 52 67 97 4 96
k= >>2
l= >>5
resulting slice:  [2,97,35,55]
average = 47.25


✍ Algorithm:

begin var n := ReadInteger; var a := arrRandomInteger(n); a.Println; var k := ReadInteger('k='); var l := ReadInteger('l='); var slice := a[k - 1:l]; println('resulting slice: ', slice); print(\$'average = {slice.Average}'); end.
Lab 4:

To do: An array of size N is given. Find the minimum element of its even-numbered elements:

a2, a4, a6, .....

The expected output:

>> 10
96 79 71 87 61 21 51 74 67 89
slice: [79,87,21,74,89]
21


✍ Algorithm:

begin var n:=ReadInteger; var a:=arrRandomInteger(n); a.Println; println('slice: ',a[1::2]); print(a[1::2].min); end.
{0.3 points} Task 5:

To do: An array of size N and integers K and L (1 <= K <= L <= N) are given. Calculate the sum of array elements except for elements with indexes from K to L inclusive.

Note: you should use here the sum method:

print(a[?:?:?].sum); // or slice.sum.print;

The expected output:

>> 10
35 26 82 63 54 47 37 95 26 88
K =  >> 4
L =  >> 8
257


[Program name: 14task-05.pas]

{0.4 points} Task 6:

To do: An array of size N (N is even) is given. Change the first half in it with the second (assume that the length of the array is an even number). Do not change the order of the elements in the halves.

The expected output:

>> 10
68 57 63 91 52 56 78 51 33 83
result: [56,78,51,33,83,68,57,63,91,52]


[Program name: 14task-06.pas]

Lab 5: Insertion and deletion in an array

To do 1: An array of N integers is given. It’s necessary to insert an element x on k-th index, k<=N.

To do 2: An array of N integers is given. It’s necessary to delete an element with index k, k<N.

The expected output:

// to do 1:
array: [5, 12, 1, 3, 11, 19]
enter a number to insert 2
enter an order number 3
result:  [5,12,1,2,3,11,19]

// to do 2:
array: [5, 12, 1, 3, 11, 19]
enter an order number
>> 2
result: [5,12,3,11,19]


✍ Algorithm:

// to do 1: begin var a := arr(5, 12, 1, 3, 11, 19); var x := ReadInteger ('enter a number to insert'); var k := ReadInteger ('enter an order number'); a := a[:k] + Arr(x) + a[k:]; print('result: ', a) end.
// to do 2: begin var a := arr(5, 12, 1, 3, 11, 19); var k := ReadInteger ('enter an order number'); a := a[:k] + a[k+1:]; print('result: ', a) end.
{0.4 points} Task 7:

To do: An array of integers is given. Find maximum element of the array and delete it. You should use slice to implement the task.

Note 1: To find an index of the maximum element it is better to use a.IndexMax method.
Note 2: Don’t forget to check if maximum is the last element of the array. In this case you should complete the task another way (use if statemnet).

The expected output:

array:  [5, 12, 1, 3, 11, 19]
result:  [5, 12, 1, 3, 11]


[Program name: 14task-07.pas]

{0.4 points} Task 8:

To do: An array of integers and N number are given (N is entered). Find minimum element of the array and insert N number before this element. You should use slice to implement the task.

Note 1: To find an index of the minimum element it is better to use a.IndexMin method.
Note 2: Don’t forget to check if minimum is the last element of the array. In this case you should complete the task another way (use if statemnet).

The expected output:

array:  [20,3,18,33,93,58,30,56,15,3]
>> 20
result:  [20,20,3,18,33,93,58,30,56,15,3]


[Program name: 14task-08.pas]

1. Open taskBook of pascalAbc.net IDE:
2. Choose ArrSlice group in the dropdown menu and click html-page button:
3. Complete the tasks giving the files the proper names (ArrSlice1.pas etc.)

### Array sorting algorithms

Lab 6:

To do: calculate a time to execute the algorithm of Bubble sort

✍ Algorithm:

procedure MySort(a: array of integer); begin // bubble sort for var i := 1 to arr.High - 1 do for var j := 0 to arr.High - i do if arr[j] > arr[j + 1] then Swap(arr[j], arr[j + 1]); end; begin var a:=arrRandomInteger(20000); // note the time var t:=System.DateTime.Now; // run the algorithm MySort(a); // note the time of algorithm end var t1:=System.DateTime.Now; println('The time to execute the algorithm: ',t1-t); //t:=System.DateTime.Now; end.
{0.5 points} Task 9:

To do: Calculate a time to execute the algorithm of Selection sort and Insertion sort. Compare the time and output the result

Note: You should create two procedures with sorting algorithms (copy those algorithms from the Theory materials). And you’ll need to note a current time four times (before starting each algorithm and before finishing it).

The expected output:

The time to execute the Insertion algorithm:  00:00:00.5804751
The time to execute the selection algorithm:  00:00:00.9035547


[Program name: 14task-09.pas]

### Merging of two sorted arrays

Lab 7:

To do: Two sorted arrays a and b are given. Merge them into third sorted array.

Resulting example:

array 1: [1,3,11,19]
array 2: [1,13,21]
result: [1,1,3,11,13,19,21]


✍ Algorithm:

function Merge(a, b: array of integer; n, m: integer): array of real; begin Assert((0 < n) and (n < a.Length)); Assert((0 < m) and (m < b.Length)); a[n] := integer.MaxValue; // barrier b[m] := integer.MaxValue; // barrier SetLength(Result, m + n); var (ia, ib) := (0, 0); for var iс := 0 to n + m - 1 do if a[ia] < b[ib] then begin Result[iс] := a[ia]; ia += 1; end else begin Result[iс] := b[ib]; ib += 1; end; end; begin var a := arr(1, 3, 11, 19); var b := arr(1, 13, 21); println('array 1:',a); println('array 2:',b); setLength(a, 5); // for extra element setLength(b, 4); // for extra element print('result: ', Merge(a, b, 4, 3)) // [1,1,3,11,13,19,21] end.
{0.5 points} Task 10:

To do: Calculate a time to execute the algorithm of the lab before this task (with the function to Merge two arrays). Compare the time with a time, needed to complete the merging using standard sort algorithm:

var c:=a+b; sort(c);

The expected output:

array 1: [1,3,11,19]
array 2: [1,13,21]
result array c: [1,1,3,11,13,19,21]
the time with standard sort method 00:00:00.0009962
result:  [1,1,3,11,13,19,21]
the time with function to merge 00:00:00.0009984


[Program name: 14task-10.pas]

Lab 8:

To do: An array of integers and n number is given (n is entered). You should output the index of the n number in the array, or ‘there is no n’ message if n is not in the array.

The expected output:

array:  [3,3,24,41,57,59,84,88,89,95]
enter n to find it:
>> 41
index of n is:  3

✍ Algorithm:

begin var a := arrrandominteger(10); sort(a); println('array: ', a); var n := readinteger('enter n to find it: '); var index := a.BinarySearch(n); if (n > 0) then print('index of n is: ', index) else print('there is no n ') end.
{0.5 points} Task 11:

To do: An array of integers and n number are given (n is entered). You should use a.BinarySearch(n) standard method to delete that n from the array. Also, you should use slices to do it.

Note: to use BinarySearch() method you need the array to be sorted first. So, use Sort() method before searching.

The expected output:

array:  [6,71,85,33,41,75,75,84,38,57]
sorted array:  [6,33,38,41,57,71,75,75,84,85]
enter n to delete it:
>> 38
result:  [6,33,41,57,71,75,75,84,85]


[Program name: 14task-11.pas]

### Lists

Lab 9:

To do: An array of N integers is given. Insert all even elements of the array into L1, and all odd elements into L2.

The expected output:

array: [17,25,8,17,21,9,19,22,19,24]
L1: 8 22 24
L2: 17 25 17 21 9 19 19


✍ Algorithm:

begin var a := arrrandominteger(10, 5, 25); println(a); var L1 := new List<integer>; var L2 := new List<integer>;   foreach var x in a do if x.IsEven then L1 += x else L2 += x; L1.println; L2.println; end.
{0.2 points} Task 12:

To do: An array of integers is given (fill it with random generated numbers in the range [-5,20]). Insert all positive elements of the array into L1 list, and all negative elements into L2 list.

The expected output:

array:  [17,16,15,5,-2,2,-3,-5,16,-5]
L1: 17 16 15 5 2 16
L2: -2 -3 -5 -5


[Program name: 14task-12.pas]

{0.4 points} Task 13:

To do: A list of integers is given. Find maximum element of the list and delete it. You should use L.RemoveAt(k); standard list method.

Note: To find an index of the maximum element it is better to use L.IndexMax method.

The expected output:

List: 0 93 71 88 99 44 50 36 72 1
result:  [0,93,71,88,44,50,36,72,1]


[Program name: 14task-13.pas]

{0.4 points} Task 14:

To do: A list of integers and N number are given (N is entered). Find minimum element of the list and insert N number before this element. You should use L.Insert(ind,n); standard method.

Note: To find an index of the minimum element it is better to use L.IndexMin method.

The expected output:

76 45 84 47 85 27 12 74 21 47
enter n:
>> 20
result:  [76,45,84,47,85,27,20,12,74,21,47]


[Program name: 14task-14.pas]

Вставить формулу как
Дополнительные настройки
Цвет формулы
Используйте LaTeX для набора формулы
Предпросмотр
$${}$$
Формула не набрана
Вставить