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

Дата изменения: 24 декабря 2020

## 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);

### 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 resulting example:

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 resulting example:

>>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 resulting example:

>>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. First, output its 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 resulting example:

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). First, output 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 resulting example:

>>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 numbers from K to L inclusive.

The resulting example:

>> 10
59 87 0 37 57 69 79 19 100 5
K=  >> 2
L=  >> 4
41.3333333333333


✍ 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].Average; slice.Print; 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 resulting example:

>> 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 print(slice.sum);

The resulting example:

>> 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 resulting example:

>> 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 resulting example:

// 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: To find an index of the maximum element it is better to use a.IndexMax method.

The resulting example:

array:  [66,46,26,64,73,62,37,57,46,9]
result:  [66,46,26,64,62,37,57,46,9]


[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: To find an index of the maximum element it is better to use a.IndexMin method.

The resulting example:

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]

### 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 resulting example:

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 resulting example:

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 resulting example:

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 resulting example:

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 resulting example:

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 resulting example:

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 resulting example:

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 resulting example:

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 для набора формулы
Предпросмотр
$${}$$
Формула не набрана
Вставить 