C++, Сортировка вставками

Question

C++, Сортировка вставками

Я не знаю что написать Ведьмин Ученик (159), закрыт 11 месяцев назад

Библиотечный метод
Продемонстрируйте работу метода сортировки вставками по возрастанию. Для этого выведите состояние данного массива после каждой вставки на отдельных строках. Если после рассмотрения очередного элемента массив не изменился, то его выводить не нужно. Если массив упорядочен изначально, то следует не выводить ничего.

Ввод:
4
2 1 5 3
Вывод:
1 2 5 3
1 2 3 5

Answer 1

 #include  
#include  
#include 

using namespace std; 
using T = int;

void show(vector::iterator begin, vector::iterator end) { 
    for (auto& it = begin; it != end; ++it) cout << *it << ' '; 
    cout.put('\n'); 
}

void sort_and_show(vector::iterator begin, vector::iterator end) { 
    if (begin >= end) return; 
    for (auto i = begin + 1; i != end; ++i) { 
        auto n = 0; 
        for (auto j = i; j != begin && *j < *(j - 1); --j) { 
            iter_swap(j - 1, j); 
            ++n; 
        } 
        if (n) show(begin, end); 
    } 
}

int main() { 
    size_t n; 
    cin >> n; 
    vector box(n); 
    for (auto& x : box) cin >> x; 
    if (is_sorted(box.begin(), box.end())); 
    else sort_and_show(box.begin(), box.end()); 
}

Answer 2

 #include  
#include  
#include  
 
void printArray(const std::vector& arr) { 
    for (int num : arr) { 
        std::cout << num << " "; 
    } 
    std::cout << std::endl; 
} 
 
void insertionSort(std::vector& arr) { 
    int n = arr.size(); 
    for (int i = 1; i < n; ++i) { 
        int key = arr[i]; 
        int j = i - 1; 
         
        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            --j; 
        } 
         
        arr[j + 1] = key; 
        printArray(arr); 
    } 
} 
 
int main() { 
    int n; 
    std::cin >> n; 
     
    std::vector arr(n); 
    for (int i = 0; i < n; ++i) { 
        std::cin >> arr[i]; 
    } 
 
    std::cout << "Initial array:" << std::endl; 
    printArray(arr); 
 
    insertionSort(arr); 
 
    return 0; 
}

Answer 3

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

using namespace std;
using T = int;

void show(vector<T>::iterator begin, vector<T>::iterator end) {
for (auto& it = begin; it != end; ++it) cout << *it << ' ';
cout.put('\n');
}

void sort_and_show(vector<T>::iterator begin, vector<T>::iterator end) {
if (begin >= end) return;
for (auto i = begin + 1; i != end; ++i) {
auto n = 0;
for (auto j = i; j != begin && *j < *(j - 1); --j) {
iter_swap(j - 1, j);
++n;
}
if (n) show(begin, end);
}
}

int main() {
size_t n;
cin >> n;
vector<T> box(n);
for (auto& x : box) cin >> x;
if (is_sorted(box.begin(), box.end()));
else sort_and_show(box.begin(), box.end());
}