1 Тема від ioori

  • ioori
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 13.11.2022
  • Повідомлень: 5
    • Репутація: 1

Тема: Алгоритм плавного сортування (SmoothSort)

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

#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]);
}
Подякували: leofun011

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 782
    • Репутація: 13453

Re: Алгоритм плавного сортування (SmoothSort)

Це не плавне сортування, а якась варіація сортування гребінцем, причому, з одного боку, проміжок скорочується зашвидко, а з іншого, "черепахи" усуваються додатковим циклом. Біс його зна, наскільки це ефективно і чи взагалі правильно. Я протестував кілька разів на випадкових даних; ніби дійсно працює, але потрібне теоретичне дослідження і бенчмарк.

Подякували: Firefox is dead, leofun012

koala вебсайт

3 Відповідь від ioori

  • ioori
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 13.11.2022
  • Повідомлень: 5
    • Репутація: 1

Re: Алгоритм плавного сортування (SmoothSort)

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

4 Відповідь від wander Востаннє редагувалося wander (22.02.2023 19:48:54)

  • wander
  • wander
  • Replace Team
  • Поза форумом
  • Звідки: No-man's land
  • Дата реєстрації: 28.02.2019
  • Повідомлень: 1 349
    • Репутація: 1276

Re: Алгоритм плавного сортування (SmoothSort)

ioori написав:

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

Ну, я гадаю вам точно потрібні числа Леонардо.

wikipedia написав:

На відміну від пірамідального сортування, тут використовується не двійкова купа, а спеціальна, отримана за допомогою чисел Леонардо.

І потрібно буде будувати дерева (купу), щось схоже як з heap sort, але базуючись на числах Леонардо.

https://www.keithschwarz.com/smoothsort/ написав:

The Leonardo numbers (denoted L(0), L(1), L(2), ...) are given by the following recursive formulation:

  • L(0) = 1

  • L(1) = 1

  • L(n + 2) = L(n) + L(n + 1) + 1

For reference, the first few Leonardo numbers are 1, 1, 3, 5, 9, 15, 25, 41, 67, and 109.

A Leonardo tree of order k (denoted Ltk) is a binary tree with a rigidly-defined shape. Leonardo trees are defined recursively as follows:

  • Lt0 is a singleton node.

  • Lt1 is a singleton node.

  • Ltn + 2 is a node with two children, Ltn and Ltn+1 (in that order)

You can show with a fairly simple inductive proof that the number of nodes in Ltk is L(k), hence the name.

Схоже, весь сенс дерева Леонардо у тому, що кожне таке бінарне дерево повинно мати кількість вузлів, які є числом Леонардо.

https://www.keithschwarz.com/smoothsort/ написав:

Much in the same way that you can build a binomial heap using a collection of binomial trees (not required reading, but highly recommended!), you can build a "Leonardo heap" out of a collection of Leonardo trees.

А, відповідно, купа Леонардо - це набір дерев Леонардо. Якось так.

Подякували: Firefox is dead, leofun01, koala, ioori4

5 Відповідь від Firefox is dead

  • Дата реєстрації: 11.01.2023
  • Повідомлень: 191
    • Репутація: 84

Re: Алгоритм плавного сортування (SmoothSort)

ioori написав:

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

спробуйте самі написати ._.

#include <iostream>
#include <vector>

using namespace std;

void smoothSort(vector<int>& arr) {
    int n = arr.size();
    int gap = n;
    bool swapped = true;
    while (gap > 1 || swapped) {
        gap = max(1, static_cast<int>(gap / 1.3));
        swapped = false;
        for (int i = 0; i + gap < n; i++) {
            if (arr[i] > arr[i + gap]) {
                swap(arr[i], arr[i + gap]);
                swapped = true;
            }
        }
    }
}

int main() {
    vector<int> arr = {7, 3, 5, 1, 9, 8, 4, 2, 6};
    smoothSort(arr);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}