1D Arrays - Recap, Searching and Sorting

1D Arrays Recap

• This lecture covers one-dimensional arrays, searching, and sorting.
• It includes examples and algorithms demonstrated in C++.

1D Array Initialization and Access

• Integer array initialization:

  int values[5]; // Initialize values int for (int i = 0; i < 5; i++) cin >> values[i];
  cout << values int << endl;
  
  for (int i = 0; i < 5; i++) cout << values[i];
  cout << endl;
  

• Character array initialization:

  char valueschar[6];
  valueschar[0] = 'H';
  valueschar[1] = 'e';
  valueschar[2] = 'l';
  valueschar[3] = 'l';
  valueschar[4] = 'o';
  valueschar[5] = '\0';
  cout << valueschar << endl;
  
  int i = 0;
  while (valueschar[i] != '\0') {
      cout << valueschar[i];
      i++;
  }
  cout << endl;
  

• Sending an array as a parameter:
  cpp void readArrayValues(int arr[], int size) { for (int i = 0; i < size; ++i) { cin >> arr[i]; } }

  • The function readArrayValues takes an integer array arr and its size size as input, then populates the array with values entered by the user via cin.

Searching Algorithms

• Searching: Process of finding a given item in an array.
  • Can return true if found, false if not.
  • Alternatively, can return the index of the item if found, and -1 if not.
• Sorting: Rearranging the items in an array into a specific order.

Linear Search

• Simple algorithm that accepts an array, its size, and the element to find.
• Steps:
  1. Set the current element as the first element.
  2. Compare the current element to the element to find.
  3. If equal:
     • The element has been found.
     • The result is true or the index of the current element.
     • Go to Step 5.
  4. If not equal:
     • The element has not been found.
     • Increment the current element to the next element.
     • If the current element exceeds the array size, the element is not in the array, and the result is false or -1. Go to Step 5; otherwise, go to Step 2.
  5. Return the result of the search.
• Linear search using a for-loop:
  cpp int linearSearch(int arr[], int size, int searchElement) { for (int i = 0; i < size; ++i) { if (arr[i] == searchElement) { return i; } } return -1; }
• Linear search with a while-loop: cpp int searchList(int arr[], int size, int searchElement) { int index = 0; // index to process the array bool found = false; // flag, true when target is found while (index < size && !found) { if (arr[index] == searchElement) { // found the target found = true; // set the flag } else { index++; // increment loop index } } if (!found) return -1; else return index; }
  • Best-case scenario.
  • Worst-case scenario.
  • What if more than one target element is in the array?
  • Is there a way to exit the algorithm early if the element cannot be in the rest of the array?

Sorting Algorithms

• Sorting is important because searching in a sorted list is much easier than in an unsorted list.
• Examples: dictionary entries, phone book, card catalog in library, bank statements.
• Most data displayed by computers is sorted.
• Two sorting algorithms discussed:
  • Bubble sort
  • Selection sort

Bubble Sort

• Accepts an array and its size as parameters.
• The largest element is "bubbled" up to the right when sorting in ascending order.
• Code:
  cpp void bubbleSort(int arr[], int size) { for (int i = 0; i < size - 1; ++i) { for (int j = 0; j < size - i - 1; ++j) { if (arr[j] > arr[j + 1]) { swop(arr[j], arr[j + 1]); } } } }
• Example: Consider the array [4, 8, 9, 3, 6].
  • Pass 1, $i = 0$, $j$ runs from 0 to 4 - [4, 8, 3, 6, 9]
  • Pass 2, $i = 1$, $j$ runs from 0 to 3 - [4, 3, 6, 8, 9]
  • Pass 3, $i = 2$, $j$ runs from 0 to 2 - [3, 4, 6, 8, 9]
  • Pass 4, $i = 3$, $j$ runs from 0 to 1 - [3, 4, 6, 8, 9] (no changes)

Selection Sort

• Accepts an array and its size as a parameter.
• The smallest element in the unsorted portion is swapped with the element in the current position.
• Code:
  cpp void selectionSort(int arr[], int size) { for (int i = 0; i < size - 1; ++i) { int minIndex = i; for (int j = i + 1; j < size; ++j) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex != i) { swop(arr[i], arr[minIndex]); } } }
• Example: Consider the array [4, 8, 9, 3, 6].
  • Pass 1, $i = 0$, $j$ runs from 1 to 4 - [3, 8, 9, 4, 6]
  • Pass 2, $i = 1$, $j$ runs from 2 to 4 - [3, 4, 9, 8, 6]
  • Pass 3, $i = 2$, $j$ runs from 3 to 4 - [3, 4, 6, 8, 9]
  • Pass 4, $i = 3$, $j$ runs from 4 to 4 - [3, 4, 6, 8, 9]

Binary Search

• Must be applied to a sorted array.
• Governed by three values: first, last, and midpoint.
• The algorithm determines the midpoint of the array.
• If the item being searched for is smaller than the midpoint, the part of the array to the left of the midpoint is considered; otherwise, the part from the midpoint to the right is considered.
• If last is smaller than first, the element is not in the array.
• Code:
  cpp bool binarySearch(int arr[], int size, int searchElement) { int first = 0, last = size - 1; while (first <= last) { int middle = (first + last) / 2; if (arr[middle] == searchElement) { return true; } else if (arr[middle] < searchElement) { first = middle + 1; } else { last = middle - 1; } } return false; }
• Apply the algorithm to the sorted array [3, 4, 6, 8, 9], searching for each element in the array as well as 12.
• Change the function to return the index of the search element and -1 if not found.