Algorithms 101: Stable vs Unstable Sorting in Python

When sorting algorithms are discussed, one important characteristic to consider is whether they are stable or unstable. This distinction can have significant implications, especially when dealing with data that contains equal elements where the relative order matters.

1. What is a Stable Sort?

[English] A stable sort is a sorting algorithm that maintains the relative order of records with equal keys (values). In other words, if two elements have the same key, their order in the sorted output will be the same as their order in the input.

Example:
Consider a list of tuples where the first element is a name and the second is an age. If we sort by age using a stable sort, the relative order of names with the same age will be preserved.

data = [("John", 25), ("Jane", 22), ("Doe", 25), ("Alice", 22)]
sorted_data = sorted(data, key=lambda x: x[1])

print(sorted_data)
# Output: [('Jane', 22), ('Alice', 22), ('John', 25), ('Doe', 25)]

What Happens: Even though both John and Doe have the same age (25), John appears before Doe in the sorted list, just as in the original list. This demonstrates the stability of Python’s built-in sort.

Behind the Scenes: Stability is important when multiple criteria are used for sorting. You can first sort by a secondary criterion and then by the primary criterion, knowing that the secondary order will be preserved within the primary order.

[Chinese] 稳定排序是一种保持相同键（值）记录的相对顺序的排序算法。换句话说，如果两个元素具有相同的键，它们在排序输出中的顺序将与它们在输入中的顺序相同。

示例:
考虑一个元组列表，其中第一个元素是姓名，第二个是年龄。如果我们使用稳定排序按年龄排序，则相同年龄的姓名的相对顺序将被保留。

data = [("John", 25), ("Jane", 22), ("Doe", 25), ("Alice", 22)]
sorted_data = sorted(data, key=lambda x: x[1])

print(sorted_data)
# 输出: [('Jane', 22), ('Alice', 22), ('John', 25), ('Doe', 25)]

What Happens: 尽管 John 和 Doe 的年龄相同（25），John 在排序列表中仍然出现在 Doe 之前，就像在原始列表中一样。这展示了 Python 内置排序的稳定性。

Behind the Scenes: 稳定性在使用多个标准进行排序时非常重要。您可以先按次要标准排序，然后按主要标准排序，知道次要顺序将在主要顺序内被保留。

2. What is an Unstable Sort?

[English] An unstable sort, on the other hand, does not guarantee the relative order of records with equal keys. If two elements have the same key, their order in the sorted output may not be the same as their order in the input.

Example:
If Python’s sort were unstable, sorting the same list as before could result in John and Doe appearing in any order, even though they have the same age.

Unstable Sorting Behavior:

# Hypothetical example (Python's sort is stable, but let's consider an unstable scenario)
data = [("John", 25), ("Jane", 22), ("Doe", 25), ("Alice", 22)]
# Assume the sort is unstable
unstable_sorted_data = sorted(data, key=lambda x: x[1], reverse=True)

# Possible output:
# [('John', 25), ('Doe', 25), ('Jane', 22), ('Alice', 22)]
# or
# [('Doe', 25), ('John', 25), ('Jane', 22), ('Alice', 22)]

What Happens: In an unstable sort, John and Doe might switch places because the algorithm does not guarantee that their original order will be preserved.

Behind the Scenes: Unstable sorts can be problematic when the input data requires that the relative order of equal elements be maintained, such as when sorting multi-level criteria.

[Chinese] 不稳定排序则不保证相同键记录的相对顺序。如果两个元素具有相同的键，它们在排序输出中的顺序可能与它们在输入中的顺序不同。

示例:
如果 Python 的排序是不稳定的，排序相同列表可能导致 John 和 Doe 出现的顺序不同，尽管它们的年龄相同。

不稳定排序行为:

# 假设例子（Python 的排序是稳定的，但让我们考虑不稳定的情况）
data = [("John", 25), ("Jane", 22), ("Doe", 25), ("Alice", 22)]
# 假设排序是不稳定的
unstable_sorted_data = sorted(data, key=lambda x: x[1], reverse=True)

# 可能的输出:
# [('John', 25), ('Doe', 25), ('Jane', 22), ('Alice', 22)]
# 或
# [('Doe', 25), ('John', 25), ('Jane', 22), ('Alice', 22)]

What Happens: 在不稳定排序中，John 和 Doe 可能会交换位置，因为算法不保证它们的原始顺序会被保留。

Behind the Scenes: 当输入数据要求保持相等元素的相对顺序时，例如在排序多层标准时，不稳定排序可能会出现问题。

3. Is Python’s Built-in Sort Stable or Unstable?

[English] Python’s built-in sort() method and the sorted() function are both stable. This means that when you sort a list of objects that have equal keys, their relative order will be preserved in the sorted output.

Example Demonstrating Stability:

data = [("apple", 2), ("banana", 2), ("cherry", 1)]
sorted_data = sorted(data, key=lambda x: x[1])

print(sorted_data)
# Output: [('cherry', 1), ('apple', 2), ('banana', 2)]

What Happens: Since Python’s sort is stable, "apple" and "banana" retain their original order relative to each other in the sorted list, even though they have the same key.

Behind the Scenes: The stability of Python’s sort is particularly useful when you need to perform multi-level sorting by first sorting on a secondary key and then on a primary key, while ensuring that the secondary order is preserved within the primary order.

[Chinese] Python 内置的 sort() 方法和 sorted() 函数都是稳定的。这意味着当你对具有相同键的对象列表进行排序时，它们的相对顺序将在排序后的输出中保留。

演示稳定性的示例:

data = [("apple", 2), ("banana", 2), ("cherry", 1)]
sorted_data = sorted(data, key=lambda x: x[1])

print(sorted_data)
# 输出: [('cherry', 1), ('apple', 2), ('banana', 2)]

What Happens: 由于 Python 的排序是稳定的，即使“apple”和“banana”具有相同的键，它们在排序列表中的相对顺序仍然保持不变。

Behind the Scenes: Python 排序的稳定性在需要通过首先按次要键排序然后按主要键排序时特别有用，同时确保次要顺序在主要顺序内被保留。

4. When to Choose Stable vs Unstable Sorts?

[English] Stable Sort:

• Multi-level sorting: When sorting data on multiple keys, a stable sort ensures that the order of equal keys in the first sort is preserved in subsequent sorts.
• Data Integrity: In scenarios where the relative order of equal elements carries meaning (e.g., in lists of objects with timestamps), a stable sort is necessary.

Unstable Sort:

• Performance Consideration: In some algorithms, an unstable sort may be faster due to fewer constraints, though this depends on the specific algorithm and implementation.
• Single-level sorting: If you are only sorting on a single key and the relative order of equal elements doesn’t matter, an unstable sort can be considered if it offers performance benefits.

[Chinese] 稳定排序:

• 多层次排序: 当对数据进行多键排序时，稳定排序确保第一次排序中相等键的顺序在随后的排序中保持不变。
• 数据完整性: 在相等元素的相对顺序具有意义的场景中（例如，在带有时间戳的对象列表中），需要稳定排序。

不稳定排序:

• 性能考虑: 在某些算法中，由于约束较少，不稳定排序可能更快，尽管这取决于具体的算法和实现。
• 单层次排序: 如果你只对单个键进行排序，并且相等元素的相对顺序无关紧要，可以考虑不稳定排序，如果它提供性能优势。

In summary, whether you choose a stable or unstable sort depends on the nature of your data and your specific sorting requirements. Python’s built-in sort being stable is a powerful tool, particularly in cases where multi-level sorting is required.