stooge sort сортировка

Question

#include<iostream>
using namespace std;
void StoogeSort(int a[], int start, int end) {
    int temp;
    if (end - start + 1 > 2) {
        temp = (end - start + 1) / 3;
        StoogeSort(a, start, end - temp);
        StoogeSort(a, start + temp, end);
        StoogeSort(a, start, end - temp);
    }
    if (a[end] < a[start]) {
        temp = a[start];
        a[start] = a[end];
        a[end] = temp;
    }
}

помогите понять как это работает

Answer 1

Во-первых у вас в коде ошибка:

вместо temp = (end - start + 1) / 3; должно быть temp = int((end - start + 1) / 3);

Объяснение по этой сортировке можно прочитать на Википедии: Stooge sort

Вот краткое объяснение:

Если в массиве 3 и более элементов, то:

вызываем сортировку для первых 2/3 массива
вызываем сортировку для вторых 2/3 массива
опять вызываем сортировку для первых 2/3 массива.

Если в массиве <3 элементов, то: если первый элемент > последнего, меняем их местами

БЛОГ НА HUSL

stooge sort сортировка

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

Вот краткое объяснение: