slice is a subarray of the original array

Back

Go ahead

Содержание:

Theory: slices, Sorting algorithms
Labs and tasks

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

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.

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.

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;

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):

A_k, A_{2 * k}, A_{3 * 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:

а₂, а₄, а₆, ... а_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, ... а₁

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):

a₂, a₄, a₆, ... a₁, a₃, a₅ ...

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:

a₂, a₄, a₆, ..., a₇, a₅, a₃, a₁

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:

a₂, a₄, a₆, .....

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] 
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.

{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]

Back

Go ahead