Searching and Sorting Algorithms

Importance of Searching

  • A search is carried out whenever information needs to be found

  • Modern search engines process huge amounts of data and return relevant results quickly.

  • Efficient searching algorithms are essential because, without them, finding information would take much longer.

Importance of Sorting

  • Sorting arranges data into particular order, making it easier to locate information.

  • Many real-world collections of data, such as registers, databases, timetables and dictionaries, rely on sorting to support efficient searching.

BUBBLE SORT

  • A sort algorithm that uses the brute-force approach

  • The bubble sort algorithm starts at one end of the list and compares pairs of data items. If they are in the wrong order, they are swapped. The comparison of pairs continues to the end of the list, each complete traversal of the list being called a ā€˜passā€™. This process is repeated until there have been no swaps during a pass. This indicates that the items must all be in the correct order.

MERGE SORT

  • Merge sort uses a divide-and-conquer approach.

  • A list is repeatedly divided into smaller sub-lists until such sub-list contains only one item.

  • These sub-lists are then merged back together in the correct order.


SORTING ALGORITHM APPROACHES

1> Brute Force Approach

  • Used in bubble sort

  • It repeatedly performs the same comparisons and swaps until the solution is reached.

2> Divide and Conquer Approach

  • Merge sort uses divide and conquer.

  • It breaks the problem into smaller problems, solves those smaller problems and then combines the solutions.


CHOOSING AN APPROPRIATE SORTING ALGORITHM

  • Bubble Sort - Small lists (difference in execution time is negligible and it is relatively simple to implement)

  • Merge Sort - Large lists (greater efficiency)

LINEAR SEARCH

  • Examines each item in a list one at a time, starting from the beginning.

  • The search continues until the required item is found or the end of the list is reached.

BINARY SEARCH

  • Binary search repeatedly selects the middle item of a list

  • Depending on whether the middle value is too high or too low, half of the list is eliminated from consideration.

  • This process continues until the item is found.

  • This only works for a sorted list (arranged either ascending or descending)

Ā Ā Ā Ā Best-Case Scenario

Ā Ā Ā Ā The required item is the median item or only one comparison is necessary.

Ā Ā Ā Ā Worst-Case Scenario

Ā Ā Ā Ā The search repeatedly chooses median values and eliminates half of the remaining data each Ā Ā Ā Ā time.
Ā Ā Ā Ā (If a list contains 1000 items, approximately 10 comparisons)

CHOOSING SEARCH ALGORITHM

Advantages of Linear Search

  • Simple to implement

  • Works on unsorted data

  • Suitable for small datasets

  • Suitable when only one search is required

Advantages of Binary Search

  • Very efficient for large datasets

  • Requires significantly fewer comparisons

  • Ideal when multiple searches will be performed