Sorting Algorithms in AI

- Overview

In computer science, a sorting algorithm is an algorithm that puts the elements of a list in a specific order. The most commonly used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in a sorted list. Sorting is also often useful for normalizing data and producing human-readable output. More formally, the output of any sorting algorithm must satisfy two conditions:

• The output is in non-decreasing order (each element is not less than the previous element according to the desired total order);
• The output is the permutation of the input (reordered, but keeping all original elements).

Also, input data is often stored in arrays that allow random access, rather than lists that only allow sequential access; although with appropriate modifications, many algorithms can be applied to either type of data.

Sorting, as a basic operation on data, has attracted widespread interest from the beginning of computing. Many excellent algorithms have been devised. In recent years, with the advent of big data (even terabytes of data), efficiency has become more and more important for data processing, and researchers have put a lot of effort into improving the efficiency of sorting algorithms.

- Sorting Algorithms in AI

Most of the state-of-the-art sorting algorithms employ parallel computing to process large datasets and have achieved outstanding results. Machine learning is a field that has developed rapidly in recent years and has been widely used in different fields. The advent of ImageNet classification with deep convolutional neural networks in 2012 was a huge breakthrough, nearly halving the error rate of object recognition and spurring the rapid adoption of deep learning by the computer vision community. 

In March 2016, AlphaGo used neural networks to defeat human world champion Li in the game of Go, a major challenge for artificial intelligence (AI). The great success of machine learning has shown that computer artificial intelligence can surpass human knowledge in complex tasks, even from scratch. Since then, machine learning algorithms have been widely used in various fields such as human vision, natural language understanding, and medical image processing, and have achieved fruitful results. 

A neural network model inspired by the biology of the human brain has an input layer, an output layer, and a hidden layer. The hidden layer consists of many connected artificial neurons. These neurons adjust to the input and output data to accurately reflect the relationship. The essence of neural network is the mapping from input data to output data. 

Once the training phase is complete, we can apply this network of neurons to predict unknown data. This is the so-called inference phase. The accuracy and efficiency of the inference stage inspired us to apply machine learning skills to ranking. In a way, we can think of sorting as a mapping from data to dataset locations. 

[Olden, Norway - Civil Engineering Discoveries]

- Fundamental Types of Algorithms

Algorithms are categorized according to the concepts used to accomplish the task. While there are many types of algorithms, the most basic types of computer science algorithms are: 

• Divide and Conquer Algorithms - Divide a problem into smaller subproblems of the same type; solve those smaller problems and combine those solutions to solve the original problem.
• Brute Force Algorithms - try all possible solutions until a satisfactory one is found.
• Randomized Algorithms - Use random numbers at least once during a computation to find a solution to a problem.
• Greedy Algorithms - Find the optimal solution at the local level, aiming to find the optimal solution for the whole problem.
• Recursive Algorithms - Solve the lowest and simplest version of the problem, then solve larger and larger versions of the problem until a solution to the original problem is found.
• Backtracking Algorithms - Divide the problem into sub-problems, each of which can be attempted to solve; however, if the desired solution is not reached, move backwards in the problem until a path is found to move it forward.
• Dynamic Programming Algorithms - Decompose a complex problem into a set of simpler sub-problems, then solve each sub-problem only once, storing their solutions for future use instead of recomputing their solutions.