Форум программистов, компьютерный форум CyberForum.ru

Алгоритмы сортировок - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 92, средняя оценка - 4.74
Monte-Cristo
 Аватар для Monte-Cristo
2805 / 1370 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
31.03.2009, 20:10     Алгоритмы сортировок #1
Недавно была необходимость сравнить некоторые алгоритмы сортировок... Если кому-нибудь понадобятся... вообщем вот...

Алгоритмы реализованы ввиде функций, с передачей парметров: Массива A и кол-ва элементов массива n

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Метод простого извлечения
void SimpleExtract(int *A, int n)
{
    int i,y;
 
    for(i=n-1; i>0; i--)
    {
        int max=0;
 
        for (int y=1; y<=i; y++)
            {
                if(A[y]>A[max]) max=y;
            }
 
        int temp = A[i];
        A[i] = A[max];
        A[max] = temp;
    }
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Метод распределения
void Raspredel(int *A, int n)
{
  const int m = 100; // m - число, которое должно быть больше максимального элемента массива A
  int Amount[m];
  int i;
 
  for (i=0; i<m; i++) Amount[i] = 0;
    for (i=0; i<n; i++)
    {
        ++Amount[A[i]];
    }
 
    int k=0;
 
    for (i=0; i<m; i++)
    {
        for (int j=0; j<Amount[i]; j++)
        {
            A[k] = i;
            ++k;
        }
    }
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Метод простого включения
void SimplePut (int *A, int n)
{
    int i,j,Tmp;
 
    for (i=1;i<n;i++)
    {
        Tmp=A[i];
        j=i-1;
 
        while (A[j]>=Tmp && j>=0)
            { A[j+1]=A[j]; j--;}
 
        A[j+1]=Tmp;
    }
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
// Метод подсчета
void Counting(int *A, int *B, int n)
{
    for (int i=0; i<n; i++)
    {
        int k = 0;
 
        for (int j=0; j<n; j++)
            if (A[j] < A[i] || (A[j] == A[i] && j<i)) k++;
 
        B[k] = A[i];
    }
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Метод Шелла
void  Shell(int *A, int n)
{
    int h = n/2;
 
    while (h>0)
    {
        for (int i=0; i<n-h; i++)
        {
            int j = i;
        
            while (j>=0)
            {
                if (A[j] > A[j+h])
                {
                    int tmp = A[j];
                    A[j] = A[j+h];
                    A[j+h] = tmp;
                    j = j-h;
                } 
                else j--;
            }
 
        }
        h = h/2;
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
jelenad
Сообщений: n/a
19.04.2009, 22:26     Алгоритмы сортировок #2
Сортировка Shell -как это все сделать используя аплеты java?
Gulnaz
 Аватар для Gulnaz
5 / 5 / 0
Регистрация: 14.03.2008
Сообщений: 74
21.04.2009, 15:03     Алгоритмы сортировок #3
Любопытно,какой метод работает быстрее всех для очень больших массивов?
Gravity
 Аватар для Gravity
556 / 550 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
21.04.2009, 15:05     Алгоритмы сортировок #4
Цитата Сообщение от Gulnaz Посмотреть сообщение
Любопытно,какой метод работает быстрее всех для очень больших массивов?
Метод быстрой сортировки (Хоара).
Gulnaz
 Аватар для Gulnaz
5 / 5 / 0
Регистрация: 14.03.2008
Сообщений: 74
21.04.2009, 15:09     Алгоритмы сортировок #5
А для небольших массивов?
grrrrr
 Аватар для grrrrr
45 / 45 / 7
Регистрация: 21.04.2009
Сообщений: 265
30.06.2009, 09:50     Алгоритмы сортировок #6
Monte-Cristo, а метод простого включения и метод вставками это один и тот же алгоритм?
Monte-Cristo
 Аватар для Monte-Cristo
2805 / 1370 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
30.06.2009, 22:15  [ТС]     Алгоритмы сортировок #7
Сортировка включением (вставками - by insertion). Исходное множество элементов делят на две части: уже упорядоченную и неупорядоченную. Вначале упорядоченная часть состоит, как правило, из одного элемента – первого элемента, а все остальные элементы находятся в неупорядоченной части. Из неупорядоченной части берут очередной элемент и включают его в упорядоченную часть, помещая (вставляя) на нужное место (т.е. так, чтобы выполнялось отношение порядка). Так продолжают до тех пор, пока последний элемент из неупорядоченной части не будет включен в упорядоченную часть. Простой вариант сортировки включением – это метод прямого (простого) включения, улучшенный – сортировка методом Шелла.
Doc.X
11 / 11 / 0
Регистрация: 23.06.2009
Сообщений: 8
05.07.2009, 18:42     Алгоритмы сортировок #8
Слияния на паскале

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var
  mas,b:array[0..Max+1]of Longint;
procedure Msort(l,r:longint);
var i,j,k:longint;
begin
  if l>=r then exit;
  Msort(l,(l+r) div 2);
  Msort((l+r) div 2+1,r);
  j:=l;k:=(l+r) div 2+1;
  for i:=l to r do
    if (k>r) or((j<=(l+r) div 2) and(mas[j]<mas[k])) then
    begin b[i]:=mas[j];inc(j);end else
    begin b[i]:=mas[k];inc(k);end;
  for i:=l to r do mas[i]:=b[i];
end;
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
06.07.2009, 15:39     Алгоритмы сортировок #9
Monte-Cristo, вот в некоторых примерах ты используешь обычный обмен, например:
C++
1
2
3
4
5
6
7
if (A[j] > A[j+h])
{
    int tmp = A[j];
    A[j] = A[j+h];
    A[j+h] = tmp;
    j = j-h;
}
но мне кажется, что такой подход:
C++
1
2
3
4
5
if (A[j] > A[j+h])
{
    A[j] ^= A[j+h] ^= A[j] ^= A[j+h];
    j = j-h;
}
будет работать немного быстрее и не нужна еще дна переменная. Но такой подход работает только с целыми числами
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16828 / 5249 / 321
Регистрация: 30.03.2009
Сообщений: 14,133
Записей в блоге: 26
06.07.2009, 16:25     Алгоритмы сортировок #10
По поводу того, какой метод сортировки работает быстрее. Самого быстрого метода нет, потому как в одном случае может быстрее отработать один метод,а вдругом - другой. Под случаями я имею ввиду входной массив. При этом в реальной жизни как правило оказывается, что массив - это не случайный набор элементов, а какой-то специфический, а потому в каждом конкретном случае разработчики выбирают свой алгоритм.

Вообще если кому интересны методы сортировки - в сборнике Дональда Кнута там порядка 200 страниц отведено под это дело
Юляшка
3 / 3 / 1
Регистрация: 14.12.2008
Сообщений: 30
07.07.2009, 16:26     Алгоритмы сортировок #11
Хм...а поразрядная сортировка есть?

Тьфу!!!Я забыла,что распределение и есть поразрядная))))
ISergey
Maniac
Эксперт С++
 Аватар для ISergey
1331 / 864 / 50
Регистрация: 02.01.2009
Сообщений: 2,622
Записей в блоге: 1
07.07.2009, 16:33     Алгоритмы сортировок #12
Цитата Сообщение от Юляшка Посмотреть сообщение
Хм...а поразрядная сортировка есть?
Алгоритмы сортировок
в самом низу
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2014, 17:39     Алгоритмы сортировок
Еще ссылки по теме:

ЛР: Сравнение сортировок C++
C++ Несколько сортировок
C++ Сравнение сортировок

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Robert69
Заблокирован
11.12.2014, 17:39     Алгоритмы сортировок #13
А можно Монте-Кристо на паскале?
Yandex
Объявления
11.12.2014, 17:39     Алгоритмы сортировок
Ответ Создать тему
Опции темы

Текущее время: 20:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru