Thuật toán Stalin-Sort

👉 Đây là đoạn nói về StalinSort, tưởng như O(n) vì chỉ cần đi qua 1 lần, nhưng nhiều cách cài đặt (ví dụ khi dùng vector.erase hay filter) lại tốn O(n²) vì mỗi lần xóa phần tử giữa mảng, dữ liệu phải dịch chuyển.

C++

#include <vector>
#include <iostream>
template<class T>
void StalinSort(std::vector<T>& L)
{
    auto it  = L.begin();
    auto aux = it;
    while (it != L.end())
    {
        if (*it < *aux)
        {
            it = L.erase(it);
        }
        else
        {
            aux = it;
            it++;
        }
    }
}
 
int main()
{
    std::vector<int> l = {1,2,3,5,4,6,4,8,9};
    StalinSort(l);
    for (auto x : l)
    {
        std::cout << x << std::endl;
    }
}

output:
1 2 3 5 6 8 9

Python

def StalinSort(list):
    i = 0
    length = len(list)
    if length > 0:
        aux = list[0]
    while i < length and length > 0:
        if aux <= list[i] :
            aux = list[i]
            i = i+1
        else:
            del list[i]
            length = length -1
             
             
list = [1,2,3,5,4,6,4,8,9]
StalinSort(list)
print(list)

output:
[1, 2, 3, 5, 6, 8, 9]