Implementation and Optimization of List Sorting Algorithms Without Built-in Functions

Fundamental Concepts of Sorting Algorithms

Sorting is one of the most fundamental and important operations in programming practice. When built-in functions are unavailable, we need to manually implement sorting algorithms. This article uses Python as an example to explore two classical sorting methods: selection sort and bubble sort.

Implementation of Selection Sort Algorithm

The core idea of selection sort is to select the smallest (or largest) element from the unsorted portion each time and place it at the end of the sorted portion. Here is an improved implementation based on the Q&A data:

data_list = [-5, -23, 5, 0, 23, -6, 23, 67]
new_list = []

while data_list:
    minimum = data_list[0]
    for x in data_list:
        if x < minimum:
            minimum = x
    new_list.append(minimum)
    data_list.remove(minimum)

print(new_list)

The time complexity of this algorithm is O(n²), where n is the length of the list. Each loop requires traversing the remaining elements to find the minimum value, then removing that value from the original list.

Detailed Algorithm Steps

Initial state: data_list = [-5, -23, 5, 0, 23, -6, 23, 67], new_list = []

First iteration: find minimum value -23, after removal data_list becomes [-5, 5, 0, 23, -6, 23, 67], new_list becomes [-23]

Second iteration: find minimum value -6, after removal data_list becomes [-5, 5, 0, 23, 23, 67], new_list becomes [-23, -6]

This process continues until data_list is empty, and new_list becomes the sorted result.

Supplemental Bubble Sort Algorithm

Another common sorting method is bubble sort, which achieves sorting through comparison and swapping of adjacent elements:

l = [64, 25, 12, 22, 11, 1, 2, 44, 3, 122, 23, 34]

for i in range(len(l)):
    for j in range(i + 1, len(l)):
        if l[i] > l[j]:
            l[i], l[j] = l[j], l[i]

print(l)

Bubble sort also has O(n²) time complexity, but in some cases performs slightly better than selection sort.

Algorithm Performance Analysis

Both algorithms belong to comparison sorts with O(n²) time complexity and O(1) (in-place sorting) or O(n) (creating new list) space complexity. Selection sort has fewer swap operations, while bubble sort can terminate early in the best case (already sorted).

Practical Application Recommendations

For small datasets, these simple algorithms are sufficient. However, when processing large-scale data, more efficient algorithms like quicksort or merge sort should be considered. Understanding these fundamental algorithms helps deeply grasp core computer science concepts.