CS-Week 3

Algorithms are the set of instructions to solve problems, and their execution speed and memory usage vary. In programming, many algorithms are based on data search and sorting. This article will introduce several data retrieval and sorting algorithms.

Linear search

Suppose there is an array [20, 500, 10, 5, 100, 1, 50] and you need to find the number 50. The linear search algorithm checks each element in the array one by one until the target value is found or the complete array is traversed.

The algorithm flow chart is as follows:

The pseudo-code for linear search is as follows:

<code>检查每个元素：如果找到目标值：返回true返回false</code>

C language implementation:

 <code class="language-c">#include <cs50.h> #include <stdio.h> int main(void) { int numbers[] = {20, 500, 10, 5, 100, 1, 50}; int n = get_int("number: "); for (int i = 0; i </stdio.h></cs50.h></code>

The time complexity of linear search is O(n).

Binary search

The binary search algorithm is suitable for sorted arrays. It improves efficiency by continuously narrowing the search range.

The pseudo-code for binary search is as follows:

<code>如果数组为空：返回false如果中间元素等于目标值：返回true如果中间元素大于目标值：在左半部分继续查找否则：在右半部分继续查找</code>

The time complexity of binary search is O(log n).

Big O notation

The large O notation is used to describe the time complexity of the algorithm. The following figure shows the curves of different time complexities:

The x-axis represents the input data volume, and the y-axis represents the solution time. O(log n) represents the optimal time complexity, and O(n²) represents the worst time complexity.

Sorting algorithm

The sorting algorithm is used to convert unordered data into ordered data. Sort data can improve search efficiency, such as binary search.

Select Sort

The pseudocode for selecting the sorting algorithm is as follows:

<code>对于每个元素：找到剩余元素中的最小值将最小值与当前元素交换</code>

Select the time complexity of sorting to be O(n²), regardless of whether the data has been sorted or not.

Bubble sort

The bubble sorting algorithm sorts data by repeatedly comparing and exchanging adjacent elements.

The pseudocode of the bubble sorting algorithm is as follows:

<code>重复n-1 次：对于每个元素：如果相邻元素顺序错误：交换它们如果未进行任何交换：结束排序</code>

The time complexity of bubble sorting is O(n²) in worst case and O(n) in best case.

This article is based on the cs50x 2024 source code.

The above is the detailed content of CS-Week 3. For more information, please follow other related articles on the PHP Chinese website!