Arrays (continued)

Arrays (continued)

Functions for array parameters of arbitrary length

// Find the largest element, defined for 
// arrays of any size
int largest(int arr[], int len) {

  int max = arr[0];
  for(int i = 0; i < len; i++) {
    if (arr[i] > max) { max = arr[i]; }
  }
  return max;

}

Compare to the definition of the same function for the arrays of fixed size:

const int N = 25000;

// Finds the largest element of the array
// It assumes that the array length N >= 1.
int largest(int arr[N]) {

  int max = arr[0];
  for(int i = 0; i < N; i++) {
    if (arr[i] > max) { max = arr[i]; }
  }
  return max;

}

Print the elements of the array

#include <iostream>
using namespace std;

// Print the array of integers 
void print(int arr[], int len);

int main() {
  int data[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
  print (data, 10);
}

void print(int arr[], int len) {
  for(int i = 0; i < len; i++) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}


1 2 4 8 16 32 64 128 256 512

Function contains

// returns true if arr contains x
bool contains(int arr[], int len, int x) {

  for(int i = 0; i < len; i++) {
    if (arr[i] == x) return true;
  }
  return false;

}

Unique integers

Ask the user to input 10 integers, and store in an array those that are unique. Then print them out.

#include <iostream>
using namespace std;

const int N = 10;

// Prints the contents of the array
void print(int arr[], int len);
// Returns true if arr contains x
bool contains(int arr[], int len, int x);

int main() {
  
  int arr[N] = {0}; // the array to store numbers
  int len = 0; // the length of the array

  for(int n = 0; n < N; n++) {
    int input = 0;
    cout << "Please enter a number: ";
    cin >> input;
    if (!contains(arr, len, input)) {
      arr[len] = input;
      len++;
    }
  }

  print(arr, len);

}

void print(int arr[], int len) {
  for(int i = 0; i < len; i++) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}

// Returns true if arr contains x
bool contains(int arr[], int len, int x) {
  for(int i = 0; i < len; i++) {
    if (arr[i] == x) return true;
  }
  return false;
}


Please enter a number: 0 
Please enter a number: 5
Please enter a number: 7
Please enter a number: 2
Please enter a number: 7
Please enter a number: 2
Please enter a number: 20
Please enter a number: 5
Please enter a number: 0
Please enter a number: 1
0 5 7 2 20 1

Replacing all occurrences of x with y

We want to write a function that replaces all occurrences of x with y in the given array.

// replaces all occurrences of x with y
void replace(int arr[], int len, int x, int y) {

  for(int i = 0; i < len; i++) {
    if (arr[i] == x) 
      arr[i] = y;
  }

}

Function find. Implementation I.

#include <iostream>
const int NOT_FOUND = -1;

// Returns the index if the first occurrence of x in arr.
// If there is none, returns -1 (which means not found)
int find(int arr[], int len, int x) {
  for(int i = 0; i < len; i++) { 
    if (arr[i] == x) return i;
  }
  return NOT_FOUND;
}

int main() {
  int data[5] = {1, 7, 3, 95, 11};
  int i = find(data, 5, 95);
  if (i != NOT_FOUND) 
    std::cout << "Found at " << i << std::endl;
}

Found at 3

Function find. Implementation II.

#include <iostream>
// If arr[i] == x for some i, return true and set index = i,
// otherwise return false.
bool find2(int arr[], int len, int x, int &index) {
  for(int i = 0; i < len; i++) { 
    if (arr[i] == x) {
      index = i;
      return true;
    }
  }
  return false;
}
int main() {
  int data[5] = {1, 7, 3, 95, 11};
  int i = 0;
  if (find2(data, 5, 95, i))
    std::cout << "Found at " << i << std::endl;
}

Found at 3

Function sort.

We are using the selection sort algorithm.

#include <iostream>
using namespace std;

const int SIZE = 10;

// Prints the contents of the array
void print(int arr[], int size);

// Swap
void swap(int &x, int &y);

// Sort in the ascending order
void sort(int arr[], int size);

int main() {
  int numbers[SIZE] = {50, 10, 25, 77, 15, 13, 68, 34, 71, 18}; 
  print(numbers, SIZE); // print it unsorted

  sort(numbers, SIZE);
  print(numbers, SIZE); // print it sorted
}

void sort(int arr[], int size) {

  // we iteratively make our array sorted, first we put 
  // the smallest element at the front, then search for the second
  // smallest element, put it at the second place i nthe array, 
  // and keep doing so until there is no elements left.

  for (int i = 0; i < size; i++) {
    // find the smallest element
    int index_min = i; 
    for (int j = i+1; j < size; j++) {
      if (arr[index_min] > arr[j]) {
        index_min = j;
      }
    }
    // and put it in front
    swap(arr[i], arr[index_min]);
  }

}

void print(int arr[], int size) {
  for(int i = 0; i < size; i++) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}

void swap(int &x, int &y) {
  int t = x;
  x = y;
  y = t;
}

50 10 25 77 15 13 68 34 71 18 
10 13 15 18 25 34 50 68 71 77

Some optimizations to the above sorting functions are possible: