Форум C++

Не подскажете, как сделать быструю сортировку массива целых чисел? тока не надо ссылки мне давать и примеры кода! в инете нет ничего вразумительного! мне тока сам принцип сортировки и все.

"Быстрая" - имеется ввиду название алгоритма или небольшой быстрый код? Я бы воспользовался обычной "пузырьковой" сортировкой, которую проходят на информатике:

1) заводим флаг, ставим его в true
2) начинаем цикл while(флаг)
3) ставим флаг в false
4) проходим циклом for(int i = 1; i < длина_массива; i++) по массиву
5) если массив[i] < массив[i-1], то меняем эти эл-ты местами и ставим флаг = true

int vector[10] = { 1,3,5,6,7,9,0,2,3,2 }; bool f; int t; f = true; while(f) {  f = false;  for(int i = 1;i < 10;i++)  {   if(vector[i] < vector[i-1])   {    t = vector[i];    vector[i] = vector[i-1];    vector[i-1] = t;    f = true;   }  } } for(int i=0;i<10;i++) {  cout << vector[i] << ","; }

Можно еще воспользоваться, если не ошибаюсь, std::vector<int>

Принцип быстрой сортировки (quicksort) без кода:

1. В исходном массиве выбираем некий элемент a[i] (в самом простом случае i - это середина массива)
2. Проходим по двум получившимся подмассивам a[0]...a[i-1] и a[i+1]...a[n] и сравниваем их элементы с a[i]. В первом подмассиве ищем элемент, больший a[i], а во втором ищем элемент, меньший a[i]. Когда находим такие элементы, то обмениваем их местами. Получаются два массива. Все элементы в первом меньше a[i], а во втором больше a[i].
3. Для каждого из этих массивов вызываем эту процедуру рекурсивно.

но вдруг a[i] например, наименьший элемент? что тогда?

Я написал не вполне верно. Там a[i] сохраняется во временную переменную, и иногда делается обмен с ней. Но суть в том, что исходный массив разбивается на два и все элементы первого меньше чем некое среднее значение, а все элементы второго больше него.

Когда при выборе среднего значения мы попадаем на наименьшее или наибольшее - то просто время работы увеличивается. В самом худшем случае (когда всегда выбираем минимум или максимум) оно будет пропорционально n^2, где n - число элементов в массиве.

Имеется код быстрой сортировки:

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

на некоторых наборах элементов массива работает, на некоторых нет - не подскажете в чем причина?

непонятна строка:
while (i<=j);
тут у нас цыкл ниче не делает, так как стоит точка с запятой. если и меньше либо равно жи, то цыкл пропустится. если нет, то прога повиснет. зачем?

if (j<low) quicksort (j,low);

Тут точно ошибка. Не может j стать меньше low.

- сортировка вставками
- вставка погружением
- сортировка Шелла
- обменная сортировка
- Шейкер-сортировка
- сортировка подсчетом
- сортировка рекурсивным разделением
- сортировка слиянием
- 'быстрая сортировка'
Каждый из методов имеет свои + и -
последний особо интересный...

есть еще heapsort но про него мне тоже не понятно

> heapsort
Выкладывайе, посмотрим на него
>тоже не понятно
Тоже не понятно по сравнению с теми методами что я привел?
Тема интересная, можем расшириться и описать каждый метод + примеры...

heapsort - пирамидальная сортировка основанная на составлении бинарного дерева... дальнейшие описания для меня непонятны.
>Тоже не понятно по сравнению с теми методами что я привел?
вы привели только названия методов, а не сами методы. я понимаю только пузырьковую и сортировку выбором(ищем макс. эл-т перемещаем в конец массива и повторяем те же методы только для массива на один эл-т меньше)
мне же надо деьальный разбор именно quicksort ибо его на олимпиадах всегда хватает, а вот пузырек или выбор не всегда катят...

Попробуйте 'быструю сортировку':

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) операций), в таких случаях можно перемешать элементы массива...

что такое сортировка шелла?

Исходный массив разбивается на 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. Сортировкой Шелла удобно сортироваь небольшие массивы...