Сортировка массива c++

Question

Задан массив из 100 символов, который может содержать только цифры. Найти последовательности четных цифр и отсортировать их по максимальному члену этой последовательности. Применить сортировку Шелла. Из задания сделал сделал только саму сортировку Шелла. Каким образом получить последовательности четных цифр и отсортировать их Шеллом по максимальному члену?

#include <iostream>
using namespace std;

int i, j, n, d, k;
void Shell(int n)
{
    int arr[100];
    for (int i = 0; i < size(arr); i++)
    {
        arr[i] = rand() % 10; //заполнение массива рандомными цифрами
    }
    cout << "Исходный массив : " << endl;
    //Вывод исходного массива
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl << "Отсортированный массив : " << endl;
    //сортировка Шелла
    d = n;
    d = d / 2;
    while (d > 0)
    {
        for (i = 0; i < n - d; i++)
        {
            j = i;
            while (j >= 0 && arr[j] > arr[j + d])
            {
                k = arr[j];
                arr[j] = arr[j + d];
                arr[j + d] = k;
                j--;
            }
        }
        d = d / 2;
    }
    for (i = 0; i < n; i++) cout << arr[i] << " "; //вывод отсортированного массива
}


int main()
{
    setlocale(LC_ALL, "Russian");
    Shell(100);
    return 0;
}

Answer 1

Выделите сортировку в отдельную функцию

void ShellSort(int arr[], int n, int start = 0)

и отладьте её сначала без использования start

Затем прибавьте start внутри всех квадратных скобок, например: arr[start + j + d]. У вас готова функция для сортировки части массива.

Теперь заведите переменную Odd=1 и пройдите по массиву.

Если Odd==1 и встретили (на индексе i) чётное - запомните индекс start = i, сделайте Odd = 0

Если Odd==0 и встретили нечётное или массив кончился - сделайте сортировку ShellSort(arr, i-start, start), сделайте Odd=1

Answer 2

У вас всё +- правильно, единственное вы забыли, что нужно перебрать все подмассивы, а не только один.

#include <ctime>
#include <random>
#include <clocale>
#include <iostream>

int main() {
    std::setlocale(LC_ALL, "rus");
    const size_t N = 100;
    int arr[N];

    // Заполнение случайными значениями
    std::srand((unsigned int) std::time(NULL));
    for (size_t i = 0; i < N; ++i) { arr[i] = rand() % 10; }

    // Вывод исходного массива
    std::cout << "Исходный массив: ";
    for (size_t i = 0; i < N; ++i) { std::cout << arr[i] << ' '; }
    std::cout << '\n';

    // Сортировка Шелла
    int val;
    for(size_t d = N / 2; d > 0; d /= 2)
        for (size_t i = 0; i < d; ++i) {
            for(size_t t, k, j = i; j < N; j += d) {
                k = j;
                val = arr[j];

                while (k >= d && arr[t = k - d] > val) {
                    arr[k] = arr[t];
                    k = t;
                }

                arr[k] = val;
            }
        }

    // Вывод отсортированного массива
    std::cout << "Отсортированный массив: ";
    for (size_t i = 0; i < N; ++i) { std::cout << arr[i] << ' '; }

    return 0;
}

Моя версия решения:

#include <ctime>
#include <random>
#include <clocale>
#include <iostream>

template<size_t N>
std::ostream& operator<<(std::ostream& out, const int (&arr)[N]) {
    out << '[';
    if(N) {
        out << arr[0];
        for(size_t i = 1; i < N; ++i)
            out << ", " << arr[i];
    }
    out << ']';
    return out;
}

class Random {
    int _mod;

public:
    Random(int mod): _mod(mod) {
        std::srand((unsigned int) std::time(NULL));
    }

    int gen() { return rand() % _mod; }

    template<size_t N>
    void fill(int (&arr)[N]) {
        for(size_t i = 0; i < N; ++i)
            arr[i] = gen();
    }
};

template<size_t N>
void shell_sort(int (&arr)[N]) {
    int val;
    for(size_t gap = N / 2; gap > 0; gap /= 2)
        for(size_t i = 0; i < gap; ++i)
            for(size_t t, pos, j = i; j < N; j += gap) {
                pos = j;
                val = arr[j];

                while(pos >= gap && arr[t = pos - gap] > val) {
                    arr[pos] = arr[t];
                    pos = t;
                }

                arr[pos] = val;
            }
}

int main() {
    std::setlocale(LC_ALL, "rus");
    const size_t N = 100;

    int arr[N];
    Random rnd(10);

    // Заполнение
    rnd.fill(arr);
    std::cout << "Исходный массив: " << arr << '\n';

    // Сортировка
    shell_sort(arr);
    std::cout << "Отсортированный массив: " << arr;
    
    return 0;
}

БЛОГ НА HUSL

Сортировка массива c++

Ответы (2 шт):