Повідомлення користувача ioori - Український форум програмістів

1 Відповідь від ioori 22.02.2023 17:33:24

Re: Алгоритм плавного сортування (SmoothSort) (4 відповідей, залишених у C++)

як тоді виглядає алгоритм плавного сортування? В інтернеті майже ніде не зміг знайти його реалізацію на c++

Перейти до форуму: C++ Перейти до теми: Алгоритм плавного сортування (SmoothSort) Перейти до повідомлення 1

2 Тема від ioori 21.02.2023 23:36:29

Тема: Алгоритм плавного сортування (SmoothSort) (4 відповідей, залишених у C++)

Чи все правильно з плавним алгоритмом сортування?
Або можно його якось покращити?

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include <iostream>
#include "doctest.h"

using namespace std;

void SmoothSort(int* arr, int len) {
    int gap = 1, i, j;
    while (gap < len)
        gap = 3 * gap + 1;
    while (gap > 1) {
        gap /= 3;
        for (i = gap; i < len; i++) {
            j = i;
            while (j >= gap && arr[j - gap] > arr[j]) {
                swap(arr[j], arr[j - gap]);
                j -= gap;
            }
        }
        gap--;
    }
}

TEST_CASE("SmoothSort test 1") {
    int arr[] = { 5, 3, 2, 10, 6 };
    int n = (sizeof(arr) / sizeof(arr[0]));
    SmoothSort(arr, n);
    int expected[] = { 2, 3, 5, 6, 10 };
    for (size_t i = 0; i < n; i++)
        CHECK(arr[i] == expected[i]);
}

TEST_CASE("SmoothSort test 2") {
    int arr[] = { -3, -7, -2, -10, -6 };
    int n = (sizeof(arr) / sizeof(arr[0]));
    SmoothSort(arr, n);
    int expected[] = { -10, -7, -6, -3, -2 };
    for (size_t i = 0; i < n; i++)
        CHECK(arr[i] == expected[i]);
}

TEST_CASE("SmoothSort test 3") {
    int arr[] = { 5, 5, 5, 3, 3 };
    int n = (sizeof(arr) / sizeof(arr[0]));
    SmoothSort(arr, n);
    int expected[] = { 3, 3, 5, 5, 5 };
    for (size_t i = 0; i < n; i++)
        CHECK(arr[i] == expected[i]);
}