Introduction of Sorting

Last translate with upstream: 08eb0c5

This article will briefly introduce sorting algorithms.

Introduction

In computer science, a sorting algorithm is an algorithm that puts a specific group of data into some order. There are many sorting algorithms, and most of them have different natures.

Properties

Stability

Stability refers to whether the relative order of equal elements has changed after sorting.

Sorting algorithm with stability will preserve the relative order of equal elements. That is, when we call that a sorting algorithm is stable, we mean that if there are two records R and S compared as equal, and in the original list R comes before S , then in sorted list R will also comes before S .

Radix sort, counting sort, insertion sort, bubble sort, and merging sort are stable sorting algorithms.

Selection sort, heap sort, and quick sort are not stable sorting algorithms.

Time complexity

Main article: Complexity

Time complexity is used to measure the relationship between the running time of an algorithm and the input scale. Commonly it is represented as O()

The simple method of calculating the complexity is generally to count the number of executions of elementary operations, and sometimes it can be approximated by directly measuring the number of loops.

Time complexity is divided into worst-case complexity, average-case complexity, best-case complexity and so on. The worst-case complexity usually needs to be considered in competitive programming, because it represents the algorithm's worst performance, and no input will bring performance worse than that.

The lower bound of the time complexity of the comparison-based sorting algorithms is O(n\log n) .

Of course, there are ones that are not O(n\log n) . E.g., the time complexity of counting sort is O(n+w) , where w represents the size of the range of input data.

Here is an animated illustration of comparison among different sorting algorithms:

Comparison among different sorting algorithms

Space Complexity

Similar to time complexity, we use space complexity to describe the size consumed by an algorithm. Generally, the smaller the space complexity, the better the algorithm.

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments