Модераторы: bsa
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Strand Sort 
V
    Опции темы
Djen1k
Дата 15.11.2009, 00:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 12
Регистрация: 4.3.2009

Репутация: нет
Всего: нет



Нужно реализовать алгоритм сортировки Strand Sort (функции передают указатели на начало и конец массива)
Всё, что удалось найти по данному алгоритму, это вот такой вот псевдокод
Код


procedure strandSort( A : list of sortable items ) defined as:
  while length( A ) > 0
    clear sublist
    sublist[ 0 ] := A[ 0 ]
    remove A[ 0 ]
    for each i in 0 to length( A ) do:
      if A[ i ] > sublist[ last ] then
        append A[ i ] to sublist
        remove A[ i ]
      end if
    end for
    merge sublist into results
  end while
  return results
end procedure



С вот таким вот примером:
Unsorted List    Sublist    Sorted List
3 1 5 4 2        
1 4 2................3 5    
1 4 2.................................3 5
2......................1 4............3 5
2......................................1 3 4 5
........................2...............1 3 4 5
.........................................1 2 3 4 5

Я что-то немножко не понимаю, как именно вставлять элементы из Sublist в Sorted List мы же вытягиваем просто возрастающую последовательность, и вставляем её, но может получится,что эл-ты нужно вставлять между эл-тами результирующего массива, что-то я тогда не понимаю этот способ сортировки...


Это сообщение отредактировал(а) Djen1k - 15.11.2009, 00:05
PM MAIL   Вверх
A5uKa
Дата 15.11.2009, 13:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


TЋ♥s F1rȜ iƧ BurȠiƞg
***


Профиль
Группа: Awaiting Authorisation
Сообщений: 1928
Регистрация: 30.8.2008

Репутация: 2
Всего: 16



Цитата

Нужно реализовать алгоритм сортировки Strand Sort

не знаю такого

Цитата

как именно вставлять элементы из Sublist в Sorted List 

В смысле ? равно написать...

Цитата

но может получится,что эл-ты нужно вставлять между эл-тами результирующего массива

Может быть только то, что ты напишешь в коде. В этом коде - не может. В том и суть сортировки, что они по порядку добавляются.
PM   Вверх
Luyan
Дата 16.11.2009, 00:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 3.12.2008

Репутация: 2
Всего: 7



суть читай здесь
http://www.itl.nist.gov/div897/sqg/dads/HTML/strandSort.html
Код

#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;
}

PM   Вверх
Djen1k
Дата 16.11.2009, 01:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 12
Регистрация: 4.3.2009

Репутация: нет
Всего: нет



Спасибо,буду разбираться smile 
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »


 




[ Время генерации скрипта: 0.0779 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.