2.6 Standard Algorithms

Introduction

In computational thinking, standard algorithms are fundamental methods used to solve common problems. Understanding these algorithms helps to develop problem-solving skills and provides a foundation for more complex programming tasks.

Definition

Standard Algorithms are well-established, widely-used algorithms that solve common computational problems such as sorting and searching. They serve as building blocks for more complex algorithms and are studied because they are efficient, reliable, and reusable.

Main Idea

The two most common categories of standard algorithms are:

• Sorting Algorithms — arrange data in a specific order.
• Searching Algorithms — find a specific item within a collection of data.

These algorithms are fundamental because they are used in almost every software application, from databases to web search engines.

Core Concept

Sorting Algorithms

These algorithms are used to arrange data in a specific order (ascending or descending).

Bubble Sort: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Selection Sort: Divides the list into a sorted and an unsorted part, and repeatedly selects the smallest (or largest) element from the unsorted part to move to the sorted part.

Merge Sort: Divides the list into halves, recursively sorts each half, and then merges the sorted halves.

Insertion Sort: An in-place sorting algorithm that builds the final sorted array one element at a time, shifting elements greater than the current element to the right.

Searching Algorithms

Linear Search: A searching algorithm that sequentially checks each element in a list until the target element is found or the end of the list is reached.

Binary Search: A searching algorithm that works on sorted arrays by repeatedly dividing the search interval in half. It efficiently finds the position of a target value within the array.

Detailed Explanation

Bubble Sort

Bubble sort works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. Larger elements "bubble" to the end of the list.

Example: Sort [5, 3, 8, 1] in ascending order.

• Pass 1: [3, 5, 1, 8]
• Pass 2: [3, 1, 5, 8]
• Pass 3: [1, 3, 5, 8]

Selection Sort

Selection sort divides the list into a sorted part and an unsorted part. It repeatedly finds the smallest element in the unsorted part and moves it to the sorted part.

Example: Sort [5, 3, 8, 1].

• Find smallest (1) → swap with 5 → [1, 3, 8, 5]
• Find smallest in unsorted (3) → already in place → [1, 3, 8, 5]
• Find smallest in unsorted (5) → swap with 8 → [1, 3, 5, 8]

Merge Sort

Merge sort divides the list into halves, sorts each half, and then merges them back together.

Example: Sort [5, 3, 8, 1].

• Divide: [5, 3] and [8, 1]
• Sort halves: [3, 5] and [1, 8]
• Merge: [1, 3, 5, 8]

Insertion Sort

Insertion sort builds the sorted array one element at a time by inserting each element into its correct position.

Example: Sort [5, 3, 8, 1].

• Start with [5]
• Insert 3 → [3, 5]
• Insert 8 → [3, 5, 8]
• Insert 1 → [1, 3, 5, 8]

Linear Search

Linear search checks each element one by one until the target is found.

Example: Search for 8 in [5, 3, 8, 1].

• Check 5 → not 8
• Check 3 → not 8
• Check 8 → found!

Binary Search

Binary search works on sorted arrays. It repeatedly divides the search interval in half.

Example: Search for 5 in [1, 3, 5, 8, 10].

- Middle = 5 → found!

Example: Search for 8 in [1, 3, 5, 8, 10].

• Middle = 5 → 8 > 5 → search right half [8, 10]
• Middle = 8 → found!

Intermediate Level

At the intermediate level, you should understand the trade-offs.

Key point: Binary search is much faster than linear search, but it requires the list to be sorted first.

Important Points

• - Standard algorithms solve common problems.
• - Two main categories: sorting and searching.
• - Sorting algorithms: Bubble, Selection, Merge, Insertion.
• - Searching algorithms: Linear, Binary.
• - Bubble, Selection, Insertion: O(n²).
• - Merge Sort: O(n log n).
• - Linear Search: O(n).
• - Binary Search: O(log n) but requires sorted data.

Remember

• - Sorting = arrange in order.
• - Searching = find an item.
• - Bubble Sort = compare adjacent, swap.
• - Selection Sort = find smallest, move to sorted.
• - Merge Sort = divide, sort, merge.
• - Insertion Sort = insert into correct position.
• - Linear Search = check one by one.
• - Binary Search = divide and conquer (sorted only).

Common Mistakes

• - Using binary search on an unsorted list (it will not work).
• - Confusing bubble sort with selection sort.
• - Thinking that merge sort is slower than bubble sort (it is faster for large lists).
• - Forgetting that linear search works on any list, but binary search only works on sorted lists.
• - Assuming that all sorting algorithms have the same time complexity.
• - Not understanding that insertion sort is efficient for nearly sorted data.

Quick Revision

• Standard algorithms: sorting and searching.
• Sorting: Bubble, Selection, Merge, Insertion.
• Searching: Linear, Binary.
• Bubble, Selection, Insertion: O(n²).
• Merge Sort: O(n log n).
• Linear Search: O(n).
• Binary Search: O(log n), requires sorted data.

60-Second Revision

• Sorting = arrange data.
• Searching = find data.
• Bubble = adjacent swap; Selection = smallest first; Merge = divide and merge; Insertion = insert in place.
• Linear = one by one; Binary = divide and conquer (sorted only).
• Merge Sort = O(n log n); Binary Search = O(log n).
• Warning: Binary search only works on sorted lists.