Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Методы сортировки одномерного массива?

Автор: Wowa 17.2.2005, 11:31

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

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

Автор: Akina 17.2.2005, 11:34

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

Автор: Sardar 17.2.2005, 11:37

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

Автор: maxim1000 17.2.2005, 11:53

Цитата

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

не совсем

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

так что универсальных методов еще не придумали...

Автор: Akina 17.2.2005, 12:05

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

Автор: pablo 17.2.2005, 14:57

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

Автор: Akina 17.2.2005, 15:03

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

Автор: pablo 17.2.2005, 15:04

Ну и что ?

Автор: Wowa 17.2.2005, 16:26

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

Автор: Doc_d0s 17.2.2005, 20:10

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

Код


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

}

Автор: Sardar 17.2.2005, 21:04

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

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

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

Автор: Wowa 17.2.2005, 22:44

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

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

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

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

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

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

Автор: Sardar 17.2.2005, 23:13

Угу, если пишем рекурсивно(что проще но и опаснее smile

) , то в начале вызова функции:

Код

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

Сама сортировка похожа на пузырёк smile

Пример на JS(ибо быстро smile

)

Код

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

Автор: Гость_Артём 22.2.2005, 14:50

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

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

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

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

Автор: chaos 22.2.2005, 15:12

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

Автор: pablo 22.2.2005, 16:44

Сортировка вставками хорошо работает при маленьких объемах данных. При больших она медленная, О(n^2).

Быстрая сортировка хорошо работает когда данные помешены в разнобой:(n * log(n)), но плохо когда они почти отсортированны, O(n^2).
Пузырьковая сортировка работает медленно почти всегда. O(n^2)
Пирaмидальная сортировка работает хорошо всегда, O(n * log(n)),только требует построения из масива структуры данных: пирамиду.
Сортировка методом Шелла немного быстрее вставками, но медленнее чем быстрая, если данные находятся в разнобой, её производительность О(n^(3/2)).

Так что для разной ситуации, надо выбирать разный алгоритм.

Автор: Sardar 22.2.2005, 19:22

Гость_Артём это простейшая задача из области разбора выражений, конкретно лексический анализ. Потребуется знание автоматов и их реализация в компе(таблично управляемый как раз что нужно) Читаем теорию, а пока достаём lex или flex, генерим парсер, компилируем, наслаждаемся.

Автор: IEZ 23.2.2005, 00:33

Загнать этот одномерный массив в STL и там уже сортировать специальными функциями.

Автор: cardinal 23.2.2005, 00:47

http://forum.vingrad.ru/index.php?showtopic=12322