Форум программистов [Powered by Invision Power Board]

Код

#include <iostream>
using namespace std;
void RotateElem(int x[], int n, int kol)
{
    int raz = 0, ishod = n-kol, num = n;
    int first = raz;
    int tmp = x[raz];
    while(true)
    {
        --num;
        x[raz] = x[ishod];
        raz = ishod;
        ishod -= kol;
        if (ishod < 0)
            ishod += n;
        if (ishod == first)
        {
            x[raz] = tmp;
            if (--num <= 0)
                break;
            if (--raz < 0)
                raz += n;
            if (--ishod < 0)
                ishod += n;
            first = raz;
            tmp = x[raz];
        }
    }
}
void MergeSort(int x[], int l, int m, int r)
{
    int i = l-1, j = m;
    while (j < r)
    {
        // пропусткаем элементы, которые не нуждаются в перемещении
        do
        {
            ++i;
        }while ((i < j) && !(x[j] < x[i]));
        if (i >= j)
            break;
        int t = j;
        // узнаем размер цепочки, которая нуждается в перемещении
        do
        {
            ++j;
        }while ((j < r) && (x[j] < x[i]));
        int num = j-t;
        // перемещаем
        RotateElem(&x[i], j-i, num);
        i += num;
    }
}
void strandSort(int x[], int n)
{
    int m, q = 0;
    do
    {
        //находим самое большое вхождение
        m = q;
        do
        {
            ++q;
        }while ((q < n) && !(x[q] < x[q-1]));
        MergeSort(x, 0, m, q);
    }while (q < n);
}

int main()
{
    //int a[5] = {10, -1,  0, -22, 6};
    int a[5] = {3, 1, 5, 4, 2};
    strandSort(a, 5);
    for( int i = 0; i < 5; i++ )
        cout << a[i] << "  ";
    cout << endl;
    system("pause");
    return 0;
}