Structural Programming

Auditory Exercise 11 - Simple Algorithms for Working with Arrays

1. Exercises

1.1 Swap with pointers

void swap (int *a, int *b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

1.2 Finding the min and max value in an array of pointers

void findMinAndMax(int arr[], int size, int *min, int *max) {
    *min = arr[0];
    *max = arr[0];
    
    for (int i = 1; i < size; i++) {
        if (arr[i] < *min) {
            *min = arr[i];
        }
        if (arr[i] > *max) {
            *max = arr[i];
        }
    }
}

int main() {
    int array[100];
    int i,n;
    cin>>n;
    int min = 0, max = 0;
    for(i=0; i<n; i++) {
        cin >> array[i];
    }
    
    findMinAndMax(array, n, &min, &max);
    
    cout << "Minimum value: " << min << endl;
    cout << "Maximum value: " << max << endl;
    return 0;
}

2. Exercise 1

Write functions for sorting array by using the following method for sorting: Bubble sort.

Write functions for reading and printing elements of an array, and write main program to test the sort function.

#include <iostream>

using namespace std;


//Reference vs. without reference
void swap(int& a, int& b) {
  int temp = a;
  a = b;
  b = temp;
}

void inputArray(int array[], int size)
{
    for (int i = 0; i < size; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }
}

void printArray(int array[], int size)
{
    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void bubbleSort(int array[], int size)
 
{
    bool swapped = true;
    while (swapped) {
        swapped = false;
        for (int i = 0; i < size - 1; i++) {
            if (array[i] > array[i + 1]) {
                swap(array[i], array[i + 1]);
                swapped = true;
            }
        }
    }
}


int main()
 
{
    int size;
    cin >> size;

    int array[size];
    inputArray(array, size);
    //Original array
    printArray(array, size);

    bubbleSort(array, size);
    //Bubble sort
    printArray(array, size);

    return 0;
}

3. Exercise 2

Write the following functions for searching an array:

-Linear search

-Binary search

Then write a program that fill an array with numbers from 1 to 1000000, and than generates random number in this range and finds its index by calling the two functions for searching.

3.1 Homework:

For the functions count and compare the number of needed iterations to find the number.

#include <iostream>
#include <cstdlib> // For rand()
#include <ctime> // For time()

using namespace std;

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

int binarySearchIterative(int arr[], int l, int r, int x)
{
    while (l <= r) {
        int m = l + (r - l) / 2;
 
        // Check if x is present at mid
        if (arr[m] == x)
            return m;
 
        // If x greater, ignore left half
        if (arr[m] < x)
            l = m + 1;
 
        // If x is smaller, ignore right half
        else
            r = m - 1;
    }
 
    // If we reach here, then element was not present
    return -1;
}

int binarySearch(int arr[], int l, int r, int key)
 
{
    if (l <= r) {
        int mid = l + (r - l) / 2;

        if (arr[mid] == key) {
            return mid;
        } else
 
if (arr[mid] < key) {
            return binarySearch(arr, mid + 1, r, key);
        } else {
            return binarySearch(arr, l, mid - 1, key);
        }
    }
    return
 
-1;
}

int main()
 
{
    // Initialize the array with numbers from 1 to 1,000,000
    int arr[1000001];
    for (int i = 0; i < 1000001; i++) {
        arr[i] = i + 1;
    }

    // Generate a random number within the range
    srand(time(NULL)); // Seed the random number generator
    int randomNum = 1 + rand() % 1000000; // Generate a random number between 1 and 1,000,000

    // Perform linear search
    int linearSearchIndex = linearSearch(arr, 1000001, randomNum);
    cout << "Linear search: " << linearSearchIndex << endl;

    // Perform binary search
    int binarySearchIndex = binarySearch(arr, 0, 1000000, randomNum);
    cout << "Binary search: " << binarySearchIndex << endl;

    return 0;
}

4. Exercise 3

Write a program that will transofrm the input array a into output array b in the following way:

bi = ai + an − 1 − i

The input array: 1 2 3 5 7

should be transformed into: 8 7 6 7 8

Explanation: Since the input array a is of size n, that b will be the same size. The transformation is done by pairwise addition and replacement of the elements. For each pair of elements a[i] and a[n-1-i], where i is from [0 to n/2-1], the neighborhood sum is stored in b[i], while a[i] is replaced with [n-1-i]. If n is odd, the middle element a[n/2] is multiplied by 2.

#include <iostream>

using namespace std;

#define MAX 100

void transform(int arr[], int n) {
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        arr[i] += arr[j];
        arr[j] = arr[i];
    }

    if (n % 2) {
        arr[n / 2] *= 2;
    }
}

void transformRecursive(int *arr, int start, int n) {
    if (start >= n/2) {
        if (n % 2 == 1) { 
            *(arr + n/2) *= 2;
        }
        return; 
    }

    int end = n - start - 1; 
    int tmp = *(arr + start) + *(arr + end);
    *(arr + start) = tmp;
    *(arr + end) = tmp;

    transform(arr, start + 1, n); 
}

int main() {
    int n;
    int arr[MAX];

    cout << "Enter the size of the array: ";
    cin >> n;

    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    //transform(arr, n);
    transformRecursive(arr, 0, n);

    cout << "Transformed array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}