Какие методы сортировки одномерного массива вы знаете?

Желательно приводить метод сортировки на англ. яз и описание.

algolist.manual.ru
Давно пора бы в Избранное занесть...

Вообще стоит держать массив уже отсортированным. Т.е. не массив, а дерево(любое). По моему в обычной ситуации быстрее "быстрой сортировки" ничего нет, но если нужны какие то еще результаты(побочное дерево и т.п.), то применяем что то другое.

Цитата

Вообще стоит держать массив уже отсортированным. Т.е. не массив, а дерево(любое). По моему в обычной ситуации быстрее "быстрой сортировки" ничего нет

не совсем
есть еще сортировка слиянием: она гарантированно дает O(n*log n), тогда как быстрая иногда может дать O(n*n)
а для "почти отсортированных" массивов вообще, насколько мне не изменяет память, неплохо подходит "пузырек"
так что универсальных методов еще не придумали...

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

Для почти отсортированных масивов лучше сортировки шелла не найти, производительность О(n^(3/2)).
Он медленнее быстрой сортировки, но быстрее пузерька.

pablo
А если это массив из 5 элементов?

Ну и что ?

тут: http://liebknecht-gymnasium.bei.t-online.d...arstellung.html
можно посмотреть разные варианты сортировки в действии

Вот тебе сырец простого слияния ман найдешь на алголисте:

Код

#include <conio.h> #include <iostream.h> #include <stdio.h> #include <stdlib.h> const n=11; void slei(int a[],const int n1); FILE *f1; void main() { int i,a[2*n]; f1=fopen("C:\\f.dat","r");   printf("Do sortirovki i..."); printf("\n\n\t\t"); for (i=0;i<n;i++)  {   fscanf(f1," %d",&a[i]);   printf("  %d",a[i]);  } printf("\n"); fclose(f1); slei (a,n); printf ("\nposle\n"); printf("\n\t\t"); for (i=0;i<n;i++)    {  printf("  %d",a[i]);    } printf("\n\t\t"); getch(); } void slei(int a[],const int n1) { int i,j,k,l,t; int h,m,p,q,r; int up=1; p=1; do{ m=n1; h=1; if(up)  {   i=0;   j=n-1;   k=n1;   l=2*n1-1;  }  else  {   k=0;   l=n1-1;   i=n1;   j=2*n1-1;  }    do      {   if(m>=p)    q=p;   else    q=m;    m=m-q;     if(m>=p)    r=p;   else    r=m;     m=m-r;    while((q!=0) && (r!=0))  {   if(a[i]<a[j])   {    a[k]=a[i];    k=k+h;    i++;    q--;   }   else   {    a[k]=a[j];    k=k+h;    j--;    r--;   }  }  while(r!=0)  {   a[k]=a[j];   k=k+h;   j--;   r--;  }  while(q!=0)  {   a[k]=a[i];   k=k+h;   i++;   q--;  }  h=-h;  t=k;  k=l;  l=t;   }        while(m!=0);          up=!up;    p=p*2; }   while(p<=n-1);         if(!up)       for(i=0;i<n;i++)           a[i]=a[i+n]; }

Цитата(maxim1000 @ 17.2.2005, 10:53)

а для "почти отсортированных" массивов вообще, насколько мне не изменяет память, неплохо подходит "пузырек"

Нет, для малеьнких и почти отсортированных массивов лучше всего "Сортировка вставками" работает. Обычно в ральном коде если менее 7 элементов осталось, быстрая сортировка на сортировку вставками переключается.

Цитата(Sardar @ 17.2.2005, 19:04)

в ральном коде если менее 7 элементов осталось, быстрая сортировка на сортировку вставками переключается.

переключается автоматом что-ли*
Добавлено @ 22:44

Цитата(Sardar @ 17.2.2005, 19:04)

в ральном коде если менее 7 элементов осталось, быстрая сортировка на сортировку вставками переключается.

переключается автоматом что-ли?

Угу, если пишем рекурсивно(что проще но и опаснее ) , то в начале вызова функции:

Код

если((индекс1-индекс2+1)<7) то сортировка_вставками(массив, индекс1,(индекс2-индекс1+1));

Сама сортировка похожа на пузырёк
Пример на JS(ибо быстро )

Код

function insertionSort(target, offset, length) {   var i,j,temp,temp2;   for(i=offset+1;i<offset+length;i++)      for(j=i; j>offset;j--) {         if(target[j]<target[j-1])  {            var temp=target[j];            target[j]=target[j-1];            target[j-1]=temp;         } else break;      }   return true; }

Люди здрасте!
В связи с тем что я начал изучать недавно c++ у меня возникли некоторые проблемы.
Мне очень нужен алгоритм или программы поиска ОДНОГО СЛОВА ИЗ ВСЕГО ТЕКСТА, но не с помощью FindDialog а посредством чего нибудь другого, т.е. после запуска программы она должна "брать" из RichEdit'а текст (весь который там находится) и проверять совпадения слов со словами находящимися в БД.
Например, в поле RichEdit вводишь:

{
...
вверх 10
влево 15
вниз 5
...
}

и программа должна испонить команду - передвинуть, например, Shape вверх на 10 пикселей, влево на 15 и вниз на 5.

Помогите пожалуйста!!!!
Заранее благодарен.

можеш воспользоваться стандартной функцией qsort или STL'евским sort