Sequential Search and Selection Sort Analysis

Sequential Search Algorithm and Analysis

• Definition and Purpose: The sequential search algorithm is an algorithm used to search a list of items to locate a specific "target" item. It follows a repetitive task of comparing the target item against successive numbers or names in a list until the item is found or the list is exhausted.

• Formal Algorithm Steps:

  1. Get values for $NUMBER$, $n$, $T_1, \dots, T_n$ and $N_1, \dots, N_n$.

  2. Set the value of $i$ to 1 and set the value of $Found$ to $NO$.

  3. While ($Found = NO$) and ($i \le n$) do Steps 4 through 7.

  4. If $NUMBER$ is equal to the $i^{th}$ number on the list, $T_i$, then

  5. Print the name of the corresponding person, $N_i$.

  6. Set the value of $Found$ to $YES$.

  7. Else ($NUMBER$ is not equal to $T_i$), add 1 to the value of $i$.

  8. If ($Found = NO$) then

  9. Print the message 'Sorry, this number is not in our directory'.

  10. Stop.

• Central Unit of Work: The primary unit of work in sequential search is the comparison of the $NUMBER$ being searched for against an individual element in the list.

• Peripheral Tasks: Tasks such as setting initial values for the index ($i$) and markers ($Found$), writing output, and moving the index forward are considered peripheral. These are ignored in high-level efficiency analysis because their contribution to the total work is constant or negligible compared to the repetitive comparison process.

• Analysis of Comparisons:

  • Best Case: Occurs if the $NUMBER$ is the very first item in the list. This requires only 1 comparison.

  • Worst Case: Occurs if the $NUMBER$ is the very last item in the list or is not present at all. In either case, the target must be compared against all $n$ items, requiring $n$ comparisons.

  • Average Case: If the target occurs randomly in the list, the average number of comparisons is approximately $\frac{n}{2}$.

• Real-World Application Example: In a reverse directory with $350,000,000$ entries, if a computer performs $50,000$ comparisons per second:

  • Average Time: $\frac{350,000,000}{2} \times \frac{1}{50,000} = 3,500\text{ seconds}$ (nearly one hour).

  • Worst Case Time: Approximately 2 hours to determine a number is not in the directory.

• Space Efficiency: Sequential search is highly space efficient. Aside from storing the list and the target, it only requires two additional memory locations (one for the index $i$ and one for the $Found$ indicator).

Order of Magnitude and Order n ($O(n)$)

• Concept of Order of Magnitude: This concept explains why constant factors (like peripheral work) are less important than the rate of growth. If $c$ is a constant factor for peripheral work, total work is expressed as $cn$.

• Comparison of Growth Rates:

  • If $c = 2$, work grows at twice the rate of $n$.

  • If $c = 1$, work grows at the same rate as $n$.

  • If $c = \frac{1}{2}$, work grows at half the rate of $n$.

• Definition of $O(n)$: Any algorithm where the amount of work varies as a constant times $n$ is said to be of order of magnitude $n$, written as $O(n)$. Sequential search is an $O(n)$ algorithm in both the worst and average cases.

Selection Sort: Algorithm and Execution

• Definition: Selection sort is a sorting algorithm that organizes a list into ascending or alphabetical order by "growing" a sorted subsection from the back of the list to the front.

• Algorithm Steps:

  1. Get values for $n$ and the $n$ list items.

  2. Set the marker for the unsorted section at the end of the list.

  3. While the unsorted section of the list is not empty, do Steps 4 through 6:

  4. Select the largest number in the unsorted section of the list.

  5. Exchange this number with the last number in the unsorted section of the list.

  6. Move the marker for the unsorted section left one position.

  7. Stop.

• Example Trace (List: 5, 7, 2, 8, 3):

  1. Initial: $5, 7, 2, 8, 3 |$ (Marker at the end; sorted section empty).

  2. Find largest (8), swap with last unsorted (3), move marker: $5, 7, 2, 3 | 8$.

  3. Find largest in unsorted (7), swap with last unsorted (3), move marker: $5, 3, 2 | 7, 8$.

  4. Find largest in unsorted (5), swap with last unsorted (2), move marker: $2, 3 | 5, 7, 8$.

  5. Find largest in unsorted (3), swap with itself, move marker: $2 | 3, 5, 7, 8$.

  6. Single number left (2) is largest, move marker: $| 2, 3, 5, 7, 8$.

Mechanics of Exchanging Values

• Requirement of Temporary Storage: Exchanging two values at positions $X$ and $Y$ requires a third temporary location ($T$). A direct copy ($X = Y$ then $Y = X$) fails because the original value of $X$ is overwritten and lost.

• Correct Exchange Algorithm:

  1. Copy the current value at position $X$ into location $T$.

  2. Copy the current value at position $Y$ into position $X$.

  3. Copy the current value at location $T$ into position $Y$.

Analysis of Selection Sort Efficiency

• Unit of Work: The unit of work is the comparison performed during the "Find Largest" subtask. To find the largest in a list of size $n$, the first number is used as "largest-so-far" and compared to the remaining $n-1$ items.

• Total Comparisons: The number of comparisons decreases as the unsorted section shrinks:     $(n - 1) + (n - 2) + (n - 3) + \dots + 3 + 2 + 1$

• Mathematical Formula: Based on Gauss\'s sum, the total comparisons are:     $\frac{n(n - 1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n$

• Performance Scaling:     | Length $n$ of List | $n^2$ | Number of Comparisons Required |     | :--- | :--- | :--- |     | 10 | 100 | 45 |     | 100 | 10,000 | 4,950 |     | 1,000 | 1,000,000 | 499,500 |

• Work Invariance: Selection sort does the same amount of work regardless of the initial arrangement of numbers. It cannot recognize if a list is already sorted; it will still perform the full sequence of comparisons and exchanges.

• Exchanges: The algorithm performs exactly $n$ exchanges (one for each position in the list), even if a number is exchanged with itself.

• Space Efficiency: It is space efficient, requiring only a few extra memory locations for the iteration marker, the "largest-so-far" tracker, and the temporary storage used for exchanges.

Practice Problems & Case Studies

• Sorting Examples:

  • List (4, 8, 2, 6): After exchange 1: (4, 6, 2, 8). After exchange 2: (4, 2, 6, 8). After exchange 3: (2, 4, 6, 8).

  • List (12, 3, 6, 8, 2, 5, 7): Becomes (7, 3, 6, 5, 2, 8, 12) $\rightarrow$ (2, 3, 6, 5, 7, 8, 12) $\rightarrow$ (2, 3, 5, 6, 7, 8, 12).

  • Already Sorted List (3, 7, 12, 16, 21): The largest element is always at the back of the unsorted section. It exchanges with itself, resulting in no visual change, though operations are still performed.

• The Pancake Problem:

  • Posed by Jacob Goodman (1975). A waiter flips a stack of varying sized pancakes using a spatula to order them from largest (bottom) to smallest (top).

  • The maximum number of flips needed for $n$ pancakes is the $n^{th}$ pancake number ($P_n$).

  • Standard algorithm flipping logic: $P_n \le 2n - 3$.

  • William Gates and Christos Papadimitriou (1979) published an improved algorithm in Discrete Mathematics requiring at most $\frac{5n + 5}{3}$ flips.