Chapter 9: Searching, Sorting & Recursion

Topics

• 9.1 - Searching
• 9.2 - Sorting
• 9.3 - Recursion
• 9.4 - Recursive Searching and Sorting

9.1 Searching

• The necessity of searching grows with data size.
  • Example: A user wants to find a used car in a database based on criteria (e.g., price, color).
• Searching: The process of finding data matching specific criteria.
  • Typically begins at the start of a dataset and moves linearly until the target item is found.
  • If not found, it implies absence in the dataset.
• Linear Search:
  • Definition: A method of searching where each element is checked in sequence until the desired item is found.
  • Implementation: Iterate through the list; if a match is found, return the index.
  • Pseudocode:
  1. For every index in the list:
  2. Get the current number at that index position.
  3. If the current number matches the target number:
     • Return the index.
  4. Return "not found".

Example of Linear Search in Java

```java
import java.util.ArrayList;
public class Java0901 {
public static void main(String args[]) {
System.out.println();
System.out.println("Java0713.java\n");
int[] array = {2,1,3,4,5,6};
int position = linearSearch(array, 5);
if(position != -1)
System.out.println("Key was found in position " + position);
else
System.out.println("Key was not found");
}

public static int linearSearch(int[] array, int key) {
for(int i = 0; i < array.length; i++) {
int element = array[i];
if(element == key) {
return i;
}
}
return -1;
}
}

Output: "Key was found in position 4"  
- **ArrayList Implementation:** Similar structure, using ArrayList instead of arrays.  

java
import java.util.ArrayList;
public class Java0902 {
public static void main(String args[]) {
System.out.println();
System.out.println("Java0714.java\n");
ArrayList list = new ArrayList();
list.add(2); list.add(1); list.add(3); list.add(4);
list.add(5); list.add(6);
int position = linearSearch(list, 5);
if(position != -1)
System.out.println("Key was found in position " + position);
else
System.out.println("Key was not found");
}

public static int linearSearch(ArrayList arrayL, int key) {
for(int i = 0; i < arrayL.size(); i++) {
int element = arrayL.get(i);
if(element == key) {
return i;
}
}
return -1;
}
}

Output: "Key was found in position 4"  

- **Limitations of Linear Search:**  
  - Efficiency decreases as dataset size increases.  
  - Worst case: Search for the millionth item requires iterating through all elements.  

---  

## 9.2 Sorting  
- As datasets grow, data management and sorting become crucial for efficiency in searching.  
- **Unorganized Data Problem:** Searching through disorganized data can be time-consuming.  
- **Need for Sorting:**  
  - Sorted data simplifies searching as it allows more straightforward navigation through the dataset.  
  - Example: Finding the value "4" in  
    `1  2  7  4  4  5  7  6  9  0  7  2  4  32  5  2  75  3  34  5  23  4  5  3` takes longer than in a sorted list  
    `0  1  2  2  3  4  4  5  5  5  6  7  7  7  9  32  34  75`.

### Sorting Algorithms  
- **Selection Sort:**  
  - Definition: A sorting algorithm that repeatedly finds the minimum value and moves it to the front.  
  - Example: Sorting `{5, 3, 4, 1, 6, 2}` with Selection Sort.  
    1. Starting index was `0`.  
    2. Find minimum (1) and swap it with 5.  
    3. Now considered sorted: `1 | 3  4  5  6  2`  
    4. Repeat to sort the entire list.  
  - Pseudocode for Selection Sort:  
    1. Traverse each index up to the second to last element.  
    2. Find minimum in the rest of the list.  
    3. Swap current index with minIndex.  

#### Example of Selection Sort in Java  

java
// Java0903.java
public class Java0903 {
public static void main(String args[]) {
System.out.println();
System.out.println("Java0715.java\n");
int[] array = {2,1,3,0,4,6,5,7,9,8};
selectionSort(array);
for(int x:array) System.out.print(x + " ");
}

public static void selectionSort(int[] array) {
for(int index = 0; index < array.length - 1; index++) {
int minIndex = index;
for(int i = index; i < array.length; i++) {
if(array[i] < array[minIndex]) {
minIndex = i;
}
}
int tempValue = array[index];
array[index] = array[minIndex];
array[minIndex] = tempValue;
}
}
}

Output: `0 1 2 3 4 5 6 7 8 9`  
- **Insertion Sort:**  
  - Comparison-based sorting; sorts each current element based on the elements already sorted to its left.  
  - Defined process:  
    1. Beginning with the second element, traverse to place it correctly in the sorted left side.  
    2. Shift elements as needed until the new element can fit.  

#### Example of Insertion Sort in Java  

java
// Java0904.java
public class Java0904 {
public static void main(String args[]) {
System.out.println();
System.out.println("Java0716.java\n");
int[] array = {2,1,3,0,4,6,5,7,9,8};
insertionSort(array);
for(int x:array) System.out.print(x + " ");
}

public static void insertionSort(int[] array) {
for(int index = 1; index < array.length; index++) { int currentIndexValue = array[index]; int sortedIndex = index - 1; while(sortedIndex > -1 && array[sortedIndex] > currentIndexValue) {
array[sortedIndex + 1] = array[sortedIndex];
sortedIndex--;
}
array[sortedIndex + 1] = currentIndexValue;
}
}
}

Output: `0 1 2 3 4 5 6 7 8 9`  
- Insertion sort is efficient on small datasets or datasets that are already mostly sorted.  

---  

## 9.3 Recursion  
- **Recursion:** A special programming technique where a method calls itself to perform iterative processes without using traditional loops (for, while, etc.).  
- **Definition of Recursion:** The process in computer programming where a method calls itself.  

### Example of Recursion  

java
// Java1001.java
// This program demonstrates recursion without an exit.
public class Java1001 {
static int k = 0;
public static void main(String args[]) {
count();
}
public static void count() {
k++;
System.out.print(k + " ");
count();
}
}

Output: `1 2 3...` followed by a StackOverflowError (due to infinite recursion)  
- Recursion simulates iteration, but must include a base case to terminate calls and prevent crashes.  

#### Example of Controlled Recursion  

java
// Java1002.java
// Demonstrates using base case to control recursion
public class Java1002 {
static int k = 0;
public static void main(String args[]) {
System.out.println("CALLING ITERATIVE COUNT METHOD");
count1();
System.out.println("\n\nCALLING RECURSIVE COUNT METHOD");
count2();
System.out.println("\n\nEXECUTION TERMINATED");
}

public static void count1() {
for (int k = 1; k <= 100; k++)
System.out.print(k + " ");
}

public static void count2() {
k++;
System.out.print(k + " ");
if (k < 100)
count2();
}
}

Output (Iterative): `1 to 100`  
Output (Recursive): `1 to 100`  
- **Recursion Rule:**  
  - Every recursive method must have an exit or base case to prevent infinite loops.  
  - Base case checks conditions to cease recursive calls.  

#### Skip Method  
- **Skip Method:**  
    - Functionality: Skip a specified number of lines.  
    - Iterative version uses a for loop.  
    - Recursive version needs a check against non-positive values.  

java
// Java1003.java
// Demonstrates Skip Method
public class Java1003 {
public static void main(String args[]) {
System.out.println("CALLING ITERATIVE SKIP METHOD");
skip1(4);
System.out.println("CALLING RECURSIVE SKIP METHOD");
skip2(3);
System.out.println("EXECUTION TERMINATED");
}

public static void skip1(int n) {
for (int k = 1; k <= n; k++)
System.out.println();
}

public static void skip2(int n) {
if (n > 0) {
System.out.println();
skip2(n-1);
}
}
}

Output: Skipped lines as desired.  

### Count Method Demonstration  
- **Count(a,b) Method:** Count recursively from a to b.  

java
// Java1004.java
// Demonstrates Count(a,b) method
public class Java1004 {
public static void main(String args[]) {
System.out.println("CALLING ITERATIVE COUNT METHOD");
count1(10,25);
System.out.println("\n\nCALLING RECURSIVE COUNT METHOD");
count2(26,40);
System.out.println("\n\nEXECUTION TERMINATED");
}

public static void count1(int a, int b) {
for (int k = a; k <= b; k++)
System.out.print(k + " ");
}

public static void count2(int a, int b) {
if (a <= b) {
System.out.print(a + " ");
count2(a+1,b);
}
}
}

Output (Iterative): `10 to 25`  
Output (Recursive): `26 to 40`  
The importance of a changing condition to reach a base case is highlighted.  

### Recursive Call Examples  
- **Post vs. Pre Recursive Calls:** Explore how placement of the recursion can change output order.  

java
public static void count1(int a, int b) {
if (a <= b) {
System.out.print(a + " ");
count1(a+1,b);
}
}

public static void count2(int a, int b) {
if (a <= b) {
count2(a+1,b);
System.out.print(a + " ");
}
}

- The stack's Last-In-First-Out (LIFO) behavior shows the outcome differences.  

### Key Takeaways on Recursion  
- Must have a base case for termination.  
- Stack memory allocation for calls demonstrates behavior in execution order.  
- Return methods often lead to more elegant and simpler solutions than using void methods.  

---  

## 9.4 Recursive Searching and Sorting  
- **Recursion in Searching:** Example of recursive linear search.  

java
public static int linear2(int list[], int key, int k) {
if (k == list.length) return -1;
else if (list[k] == key) return k;
else return linear2(list,key,k+1);
}

- **Recursive Binary Search:** Understand similar principles with dynamic parameter handling.  

java
public static int binary2(int list[], int key, int lo, int hi) {
if (lo > hi) return -1;
else {
int mid = (lo + hi) / 2;
if (list[mid] == key) return mid;
else if (key > list[mid]) return binary2(list,key,mid+1,hi);
else return binary2(list,key,lo,mid-1);
}
}
```

• Merging recursive functionality with an effective iterative sorting algorithm such as Merge Sort leads to powerful techniques in programming.
• Merge Sort Algorithm Overview:
• Step 1: Find the midpoint of the list.
• Step 2: Sort the first half of the list recursively.
• Step 3: Sort the second half of the list recursively.
• Step 4: Merge the two halves together iteratively.
• Effective sorting in recursion utilizes breaking down problems into simpler components to achieve efficient outcomes.

Conclusion

• Recognizing the suitable algorithm (searching, sorting, or recursion) based on dataset characteristics is crucial.
• Toolkits such as recursive algorithms offer a natural approach when faced with complex and sizable datasets, fostering elegant and manageable code structures.