searching and sorting - korea
Searching and Sorting
Searching
Searches are algorithms used to locate a specific element in a data structure such as an array or list.
Types of Search Algorithms
Sequential Search
Definition:
Locates a target value in an array/list by examining each element from start to finish.
If found, return the index of the first occurrence; otherwise, return -1.
Efficiency:
Time complexity is O(n), where n is the number of elements in the list.
Example: Searching the sorted array for the value 42 involves examining each element sequentially.
Binary Search
Definition:
Locates a target value in a sorted array/list by successively eliminating half of the array from consideration.
Efficiency:
Time complexity is O(log n), meaning it examines far fewer elements than a linear search.
Example: Searching a sorted array for the value 42 using binary search examines fewer elements compared to sequential search.
Implementation of Search Algorithms
Sequential Search Implementation
def sequential_search(array, target):
for i in range(len(array)):
if array[i] == target:
return i
return -1 Binary Search Implementation
def binary_search(sorted_array, target):
min_index = 0
max_index = len(sorted_array) - 1
while min_index <= max_index:
mid_index = (min_index + max_index) // 2
if sorted_array[mid_index] < target:
min_index = mid_index + 1
elif sorted_array[mid_index] > target:
max_index = mid_index - 1
else:
return mid_index
return -1 Sorting
Definition
Sorting: Rearranging the values in an array or collection into a specific order (usually in their natural ordering).
Sorting is a fundamental problem in computer science that can be solved in numerous ways.
Sorting Algorithms
There are many sorting algorithms; Wikipedia lists over 40 unique algorithms. The support varies in terms of efficiency and memory usage.
Types of Sorting Algorithms
Selection Sort: Ordinarily selects the smallest (or largest) unplaced value and puts it in the correct position.
Find the smallest value, swap with first element. Continue the process.
Insertion Sort: Sorts by building an increasingly larger sorted portion of the array.
Merge Sort: Recursively divides the array in half and sorts each half.
Selection Sort In-depth
Steps:
Look through the list to find the smallest value and swap it to index 0.
Repeat for the second smallest value to index 1.
Continue until the entire list is sorted.
Selection Sort Example
Initial Array: [101, 112, 131, 141, 151, 161]
After Each Pass:
After 1st pass: [101, 112, 131, 141, 151, 161]
The array is sorted in n - 1 passes, where n is the number of elements.
Selection Sort Implementation
def selection_sort(elements):
for j in range(len(elements) - 1):
min_index = j
for k in range(j + 1, len(elements)):
if elements[k] < elements[min_index]:
min_index = k
if j != min_index:
elements[j], elements[min_index] = elements[min_index], elements[j]Insertion Sort
Definition: Shift each element into a sorted sub-array.
Steps: Loop through indices i from 1 to n - 1, inserting the value at position i into the correct position in the sorted list from index 0 to i - 1.
Insertion Sort Example
Array Sequence: [64, 54, 58, 87, 55]
Insert 54 before 64.
Insert 58 before 64; 55 before 58.
Insertion Sort Implementation (Using ArrayLists)
def insertion_sort(lst):
for i in range(1, len(lst)):
current = lst.pop(i)
index = i - 1
while index >= 0 and current < lst[index]:
index -= 1
lst.insert(index + 1, current)Insertion Sort Implementation (Using Arrays)
def insertion_sort(elements):
for j in range(1, len(elements)):
temp = elements[j]
possible_index = j
while possible_index > 0 and temp < elements[possible_index - 1]:
elements[possible_index] = elements[possible_index - 1]
possible_index -= 1
elements[possible_index] = temp Properties of Insertion Sort
Requires n - 1 passes to sort n elements.
Worst-case scenario occurs if initially sorted in reverse leading to maximum moves and comparisons.
Best-case scenario occurs if already sorted with minimal moves required.
The Complexity of An Algorithm
Definition
Complexity: The amount of resources needed (e.g., elementary operations or loop iterations) for running an algorithm.
Lower complexity corresponds to faster algorithms.
Measuring Complexity
Complexity f(n) is defined in terms of input size n.
Approximating complexity typically involves counting iterations in the worst-case scenario.
Example Complexity Calculations
Example 1: Sequential search:
x = 0, for i in range(n): x += 1
Answer: n (Linear).
Example 2: Nested loop:
x = 0, for i in range(n): for j in range(n): x += 1
Answer: n^2 (Quadratic).
Example 3: Binary search:
While condition with log scale: x = 1 while int(math.pow(2, x)) <= n: x += 1
Answer: log_2(n).