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. |
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; |
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; |
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; |
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); |
Sort(a);
SortByDescending(a);
List type
List definition
var l := new List<integer>; // l.Count = 0 |
var l := new List<integer>; // l.Count = 0
To add an element to the end of a list:
Loop over the list:
for var i:=0 to l.Count-1 do
Print(l[i]);
foreach var x in l do
Print(x); |
for var i:=0 to l.Count-1 do
Print(l[i]);
foreach var x in l do
Print(x);
List fill:
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; |
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;
Labs and tasks
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:
{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:
{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:
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:
{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; |
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 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. |
// 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]
enter N number please:
>> 20
result: [20,20,3,18,33,93,58,30,56,15,3]
[Program name: 14task-08.pas]
Extra tasks:
- Open taskBook of pascalAbc.net IDE:
- Choose
ArrSlice group in the dropdown menu and click html-page button:
- 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. |
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. |
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:
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. |
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. |
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]
