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

    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:

      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] 
    enter N number please:  
    >> 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:= 0 to n + m - 1 do
          if a[ia] < b[ib] then
          begin
            Result[] := a[ia]; 
            ia += 1;
          end
          else
          begin
            Result[] := 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]

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    *
    *


    Вставить формулу как
    Блок
    Строка
    Дополнительные настройки
    Цвет формулы
    Цвет текста
    #333333
    Используйте LaTeX для набора формулы
    Предпросмотр
    \({}\)
    Формула не набрана
    Вставить