|
| |
|
|
| |
для: alex19921992
(22.05.2007 в 05:40)
| | | Исходный массив разбивается на n частей , в каждую из которых попадают элементы с шагом n, начиная от от 0,1,..., n-1, то есть:
0, n, 2n, 3n
1, n+1, 2n+1, 3n+1
2, n+2, 2n+2, 3n+2
...
|
Каждая часть сортируется отдельно с использованием алгоритма вставок или алгоритма обмена, Затем выбирается меньший шаг и алгоритм повторяется... Несмотря на увеличение циклов, суммарное число перестановок будет меньшим...
P.S. Шаг удобнее выбрать равным степеням 2. Сортировкой Шелла удобно сортироваь небольшие массивы... | |
| |
|
|
| |
|
|
| |
для: mefestofel
(22.05.2007 в 00:30)
| | | что такое сортировка шелла? | |
| |
|
|
| |
|
|
| |
для: alex19921992
(21.05.2007 в 18:31)
| | | Попробуйте 'быструю сортировку':
void Sort(int in[], int m, int n)
{
int i,j,res;
if (m>=n) return;
for(i=m, j=n, res=1;i<j;res>0?j--:i++)
if (in([i]>in[j])
{
int k = in[i]; in[i]=in[j]; in[j]=k;
res=-res;
}
Sort(in,m,i-1);
Sort(in,i+1,n);
}
|
Можно доработать алгоритм, когда останется по 40 элементов в массиве, можно использовать сортировку вставками - увеличение скорости на 25% - лучший метод - это комбинация 'быстрой сортировки, сортировки вставками, сортировки Шелла', также на олимпиадах Вам могут подсунуть масиив, в котором средний элемент всегда будет максимумом или минимумом(O(n2) операций), в таких случаях можно перемешать элементы массива... | |
| |
|
|
| |
|
|
| |
для: mefestofel
(21.05.2007 в 18:03)
| | | heapsort - пирамидальная сортировка основанная на составлении бинарного дерева... дальнейшие описания для меня непонятны.
>Тоже не понятно по сравнению с теми методами что я привел?
вы привели только названия методов, а не сами методы. я понимаю только пузырьковую и сортировку выбором(ищем макс. эл-т перемещаем в конец массива и повторяем те же методы только для массива на один эл-т меньше)
мне же надо деьальный разбор именно quicksort ибо его на олимпиадах всегда хватает, а вот пузырек или выбор не всегда катят... | |
| |
|
|
| |
|
|
| |
для: alex19921992
(21.05.2007 в 14:52)
| | | > heapsort
Выкладывайе, посмотрим на него
>тоже не понятно
Тоже не понятно по сравнению с теми методами что я привел?
Тема интересная, можем расшириться и описать каждый метод + примеры... | |
| |
|
|
| |
|
|
| |
для: mefestofel
(20.05.2007 в 22:21)
| | | есть еще heapsort но про него мне тоже не понятно | |
| |
|
|
| |
|
|
| |
для: beginner-c++
(20.05.2007 в 14:44)
| | |
if (j<low) quicksort (j,low);
|
Тут точно ошибка. Не может j стать меньше low. | |
| |
|
|
| |
|
|
| |
для: alex19921992
(10.05.2007 в 16:29)
| | | - сортировка вставками
- вставка погружением
- сортировка Шелла
- обменная сортировка
- Шейкер-сортировка
- сортировка подсчетом
- сортировка рекурсивным разделением
- сортировка слиянием
- 'быстрая сортировка'
Каждый из методов имеет свои + и -
последний особо интересный... | |
| |
|
|
| |
|
|
| |
для: beginner-c++
(20.05.2007 в 14:44)
| | | непонятна строка:
while (i<=j);
тут у нас цыкл ниче не делает, так как стоит точка с запятой. если и меньше либо равно жи, то цыкл пропустится. если нет, то прога повиснет. зачем? | |
| |
|
|
| |
|
|
| |
для: oleg_alexeev
(11.05.2007 в 13:43)
| | | Имеется код быстрой сортировки:
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
int array[100000]; //massiv
void quicksort (long high, long low) // funkcija sortirovki
{
long i,j;
int p, temp;
i=low;
j=high;
p=array[(low+high)/2];
do
{
while (array[i]<p) i++;
while (array[j]>p) j--;
if(i<=j)
{
temp=array[i];
array[i]=array[j];
array[j]=temp;
i++;
j--;
}
}
while (i<=j);
if (j<low) quicksort (j,low);
if (high>i) quicksort (high,i);
}
main()
{
int size;
int i;
cin>>size;
for (i=0; i<size; i++)
cin>>array[i];
quicksort (size-1,0);
for (i=0; i<size; i++)
cout<<array[i]<<" ";
getchar();
return 0;
}
|
на некоторых наборах элементов массива работает, на некоторых нет - не подскажете в чем причина? | |
| |
|
|
|
