Differences between Bubble Sort and Selection Sort#
The basic idea of Bubble Sort is to compare adjacent elements in the sequence to be sorted one by one, and if their order is incorrect, swap them. By iterating multiple times, the largest (or smallest) element is gradually moved to the end of the sequence until the entire sequence is sorted.
The basic idea of Selection Sort is to select the smallest (or largest) element from the sequence to be sorted and swap it with the first element of the sequence. Then, continue to select the smallest (or largest) element from the remaining unsorted part and swap it with the second element of the sequence, and so on, until the entire sequence is sorted.
In summary, Bubble Sort gradually moves the largest (or smallest) element by comparing adjacent elements and swapping them, while Selection Sort gradually builds a sorted sequence by selecting the smallest (or largest) element and swapping it. Due to the time required for each swap, the average performance of Selection Sort is better than Bubble Sort. However, in practical applications, if the sequence to be sorted is already mostly sorted, Bubble Sort may be faster than Selection Sort.
Time Complexity and Stability of Selection Sort and Bubble Sort#
Bubble Sort:
Time Complexity: Best case O(n), average and worst case O(n^2).
Space Complexity: O(1).
Stability: Bubble Sort is a stable sorting algorithm because during the swapping of adjacent elements, the swap only occurs when the relative order between the elements to be swapped is different.
Selection Sort:
Time Complexity: O(n^2) in best, average, and worst cases.
Space Complexity: O(1).
Stability: Selection Sort is an unstable sorting algorithm. During each selection of the minimum (or maximum) element, the relative order between the same elements may be disrupted.
In conclusion, Bubble Sort is a stable sorting algorithm, while Selection Sort is an unstable sorting algorithm. Selection Sort may change the relative order of the same elements during the process of selecting the minimum (or maximum) element. Therefore, Selection Sort is not suitable when it is necessary to maintain the relative order of the same elements, while Bubble Sort can maintain the relative order of the same elements.
Python Code Examples Illustrating the Difference between Stability and Instability, Using Bubble Sort and Selection Sort for Sorting#
First, we define a student class with name and score attributes:
class Student:
def __init__(self, name, score):
self.name = name
self.score = score
def __str__(self):
return f"{self.name}: {self.score}"
Next, we create an array of students and include two student objects with equal scores but different names:
students = [
Student("Tom", 80),
Student("Alice", 90),
Student("Bob", 80),
Student("Jack", 70),
Student("David", 80)
]
Then, we use Bubble Sort and Selection Sort respectively to sort the array of students based on their scores:
Bubble Sort:
def bubble_sort(students):
n = len(students)
for i in range(n - 1):
for j in range(n - 1 - i):
if students[j].score > students[j + 1].score:
students[j], students[j + 1] = students[j + 1], students[j]
bubble_sort(students)
Selection Sort:
def selection_sort(students):
n = len(students)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if students[j].score < students[min_index].score:
min_index = j
students[i], students[min_index] = students[min_index], students[i]
selection_sort(students)
Finally, we traverse the sorted array of students and output the sorting results:
for student in students:
print(student)
If a stable sorting algorithm, such as Bubble Sort, is used, the output after executing the above code may be:
Jack: 70
Tom: 80
Bob: 80
David: 80
Alice: 90
As can be seen, the relative order of student objects with the same score is maintained after sorting.
If an unstable sorting algorithm, such as Selection Sort, is used, the output after executing the above code may be:
Jack: 70
Bob: 80
David: 80
Tom: 80
Alice: 90
As can be seen, Selection Sort disrupts the relative order of student objects with the same score.
If there is some correlation or sorting rule between the elements with the same score, changing their order may result in the loss of this correlation.
Therefore, the "instability" of a sorting algorithm mainly refers to the possibility of changing the relative order of the same elements before and after sorting.
Bubble Sort is a stable sorting algorithm, while Selection Sort is an unstable sorting algorithm.
Examples Requiring Stable Sorting Algorithms#
Stable sorting algorithms that ensure the relative positions of the same elements remain consistent before and after sorting are necessary in many practical examples. Here are some common real-life examples where maintaining relative positions is important:
History Record Sorting: In many applications, such as browser history, chat records, or operation records in an editor, users may want to view records in chronological order, and records with the same timestamp should be displayed in the order they appeared.
Priority Queue: In task scheduling systems, such as process scheduling in operating systems or task scheduling in thread pools, there may be multiple tasks with the same priority. To handle these tasks fairly, stable sorting can ensure that tasks are scheduled in the order they were added to the queue.
Ranking Calculation: In competitions, races, or voting scenarios, if multiple participants have the same score, it is fair and reasonable to determine their rankings based on the order in which they appeared. Stable sorting algorithms can ensure that the relative order of participants does not change, thus maintaining the correct ranking results.
Feature Extraction: Feature extraction is an important task in machine learning and data analysis. When extracting features from data, if there are data points with the same feature values, stable sorting can ensure that data points with the same feature values maintain their relative positions in the output.
Transaction Processing: In the financial field, when processing transaction records, there may be transactions with the same timestamp or the same price. To ensure the correct processing and order of transactions, stable sorting can maintain the relative order of transaction records.