Сортировка

[Praud]

Нужно сортировать данные комбинированием методов быстрой сортировки и методом вставки.
Отдельно понятно, а как их скомбинировать?) Пример можно на любом одномерном массиве

[Praud]

не? никто не знает что это и с чем естся?)

[Praud]

Вот дословно задание
Сортировка таблицы комбинированием методов “быстрой сортировки” и
вставки.

[Stilet]

Я точно не знаю.

[Poma][a]

Все просто..
Для простоты берем одномерный массив.. И начинаем применять к нему итерации QSort'a.. Как только кол-во элементов в некоторой группе, которую мы сейчас собираемся сортировать, не превышает 10, мы сразу сортируем эту группу не QSort'ом, а сортировкой вставками

[challengerr]

Пример быстрой сортировки: http://algolist.manual.ru/sort/quick_sort.php
Пример сортировки вставками: http://algolist.manual.ru/sort/insert_sort.php

Цитата:

http://algolist.manual.ru/sort/quick_sort.php

1.Из-за рекурсии и других "накладных расходов" Quicksort может оказаться не столь уж быстрой для коротких массивов. Поэтому, если в массиве меньше CUTOFF элементов (константа зависит от реализации, обычно равна от 3 до 40), вызывается сортировка вставками. Увеличение скорости может составлять до 15%

Для проведения метода в жизнь можно модифицировать функцию quickSortR, заменив последние 2 строки на
if ( j > CUTOFF ) quickSortR(a, j);
if ( N > i + CUTOFF ) quickSortR(a+i, N-i);


Таким образом, массивы из CUTOFF элементов и меньше досортировываться не будут, и в конце работы quickSortR() массив разделится на последовательные части из <=CUTOFF элементов, отсортированные друг относительно друга. Близкие элементы имеют близкие позиции, поэтому, аналогично сортировке Шелла, вызывается insertSort(), которая доводит процесс до конца.
template<class T>
void qsortR(T *a, long size) {
quickSortR(a, size-1);
insertSort(a, size); // insertSortGuarded быстрее, но нужна функция setmax()
}
.

[Praud]

Спасибо! Будут вопросы - напишу.

[Praud]

Разобрался, описал для массива целых чисел.
Теперь левел ап задачи.

Предположим есть некий столбец в таблице, который необходимо сортировать по алфовиту данными методами. Есть идеи?

[Poma][a]

Есть идеи?

А есть проблемы?

[Praud]

Небольшие...
Выскакивает StackOverflow Exception

 public void QSort(int first, int last)
       {
           const int Z = 10;
           string count;
           int f = first, l = last;
           int mid = a[0,(f + l) / 2][0].GetHashCode();
           do
           {
               while (a[0,f][0].GetHashCode() < mid) f++;
               while (a[0,l][0].GetHashCode() > mid) l--;
               if (f <= l) //перестановка элементов
               {
                   count = a[0,f];
                   a[0,f] = a[0,l];
                   a[0,l] = count;
                   f++;
                   l--;
               }
           } while (f < l);

           if (l > Z) QSort(first, l);
           if (last > Z) QSort(f, last);
       }

На входе a[,] типа string.
Вызываю db.QSort(0, 15-1);
В таблице 15 строк. Пытаюсь сортировать первый столбец.