Реализация сортировки вставкой с использованием итераторов и векторов - PullRequest
Новая
       46

Реализация сортировки вставкой с использованием итераторов и векторов

0 голосов
/ 01 августа 2020

Я пытаюсь реализовать алгоритм сортировки вставкой с использованием итераторов, и он, похоже, не работает, как я думал ... У вас есть идеи, как его реализовать?

Кроме того, я могу ' Я использую такой код: https://www.geeksforgeeks.org/insertion-sort-using-c-stl/, потому что я собираюсь создать анимацию, и она станет более сложной.

Пока это мой исходный код: 

#include <iostream>
#include <vector>
#include <algorithm>



int main()
{
    
    std::vector<int> seq = { 5, 4, 3, 2, 1 };
    
    
    std::vector<int>::iterator itj;
    std::vector<int>::iterator leftmost;
    
    // insertion sort
    for (std::vector<int>::iterator iti = seq.begin() + 1; iti != seq.end(); iti = std::next(iti))
    {
        itj = std::prev(iti);
        leftmost = iti;
        
        while (std::distance(seq.begin(), itj) >= 0 && *itj > *leftmost)
        {   
            std::next(itj) = itj;
            itj = prev(itj);
        }
        std::next(itj) = leftmost;
    }
    
    // printing 
    for (std::vector<int>::iterator iti = seq.begin(); iti != seq.end(); iti = std::next(iti))
    {
        std::cout << *iti << " ";
    }
    

}

Ответы [ 2 ]

1 голос
/ 01 августа 2020

Вот реализация из SGI STL 1 : 

template<class Random_it, class T>
void unguarded_linear_insert(Random_it last, T val) {
    auto next = last;
    --next;
    while (val < *next) {
        *last = *next;
        last = next;
        --next;
    }
    *last = val;
}

template<class Random_it>
void linear_insert(Random_it first, Random_it last) {
    auto val = *last;
    if (val < *first) {
        std::copy_backward(first, last, last + 1);
        *first = val;
    }
    else
        unguarded_linear_insert(last, val);
}

template<class Random_it>
void insertion_sort(Random_it first, Random_it last) {
    if (first == last)
        return;
    for (auto i = first + 1; i != last; ++i)
        linear_insert(first, i);
}

Обратите внимание, как условие val < *first и std::copy_backward используются для упрощения l oop внутри unguarded_linear_insert: только одно условие, а именно val < *next можно проверить в этом l oop.

1 То же реализацию можно найти в libstdc ++.

1 голос
/ 01 августа 2020

Вот очень элегантная реализация сортировки вставкой с использованием итераторов, взятых прямо со справочной страницы на rotate : 

// insertion sort
for (auto i = v.begin(); i != v.end(); ++i) {
    std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
}

Все, что вам нужно сделать, это понять, как работает std::rotate, и это становится легко понять. (rotate в любом случае - действительно мощный алгоритм, с которым вам должно быть комфортно).

...