Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/88: Рейтинг темы: голосов - 88, средняя оценка - 4.75
Monte-Cristo
2796 / 1384 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
1

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

31.03.2009, 20:10. Просмотров 16121. Ответов 12
Метки нет (Все метки)

Недавно была необходимость сравнить некоторые алгоритмы сортировок... Если кому-нибудь понадобятся... вообщем вот...

Алгоритмы реализованы ввиде функций, с передачей парметров: Массива 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;
    }
}
5
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.03.2009, 20:10
Ответы с готовыми решениями:

Алгоритмы сортировок
Наиболее часто задаваемые вопросы по С++. Реализация распространенных...

Алгоритмы сортировок
Добрый день. Если у кого есть, просьба выложить коды следующих сортировок:...

Алгоритмы сортировок массива
Помогите пожалуйста написать программу на с++, которая будет содержать разные...

Сортировка вектора с демонстрационной диаграммой. Сравнить различные алгоритмы сортировок по количеству операций.
Сортировка вектора.

ЛР: Сравнение сортировок
нужно экспериментально сравнить временную сложность и провести качественный...

12
jelenad
0 / 0 / 0
Регистрация: 16.04.2009
Сообщений: 1
19.04.2009, 22:26 2
Сортировка Shell -как это все сделать используя аплеты java?
0
Gulnaz
5 / 5 / 1
Регистрация: 14.03.2008
Сообщений: 74
21.04.2009, 15:03 3
Любопытно,какой метод работает быстрее всех для очень больших массивов?
0
Gravity
569 / 563 / 64
Регистрация: 29.01.2009
Сообщений: 1,274
21.04.2009, 15:05 4
Цитата Сообщение от Gulnaz Посмотреть сообщение
Любопытно,какой метод работает быстрее всех для очень больших массивов?
Метод быстрой сортировки (Хоара).
0
Gulnaz
5 / 5 / 1
Регистрация: 14.03.2008
Сообщений: 74
21.04.2009, 15:09 5
А для небольших массивов?
0
grrrrr
45 / 45 / 13
Регистрация: 21.04.2009
Сообщений: 265
30.06.2009, 09:50 6
Monte-Cristo, а метод простого включения и метод вставками это один и тот же алгоритм?
0
Monte-Cristo
2796 / 1384 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
30.06.2009, 22:15  [ТС] 7
Сортировка включением (вставками - by insertion). Исходное множество элементов делят на две части: уже упорядоченную и неупорядоченную. Вначале упорядоченная часть состоит, как правило, из одного элемента – первого элемента, а все остальные элементы находятся в неупорядоченной части. Из неупорядоченной части берут очередной элемент и включают его в упорядоченную часть, помещая (вставляя) на нужное место (т.е. так, чтобы выполнялось отношение порядка). Так продолжают до тех пор, пока последний элемент из неупорядоченной части не будет включен в упорядоченную часть. Простой вариант сортировки включением – это метод прямого (простого) включения, улучшенный – сортировка методом Шелла.
0
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;
0
M128K145
Эксперт JavaЭксперт С++
8327 / 3548 / 420
Регистрация: 03.07.2009
Сообщений: 10,708
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;
}
будет работать немного быстрее и не нужна еще дна переменная. Но такой подход работает только с целыми числами
0
Evg
Эксперт CАвтор FAQ
19305 / 7159 / 533
Регистрация: 30.03.2009
Сообщений: 20,036
Записей в блоге: 30
06.07.2009, 16:25 10
По поводу того, какой метод сортировки работает быстрее. Самого быстрого метода нет, потому как в одном случае может быстрее отработать один метод,а вдругом - другой. Под случаями я имею ввиду входной массив. При этом в реальной жизни как правило оказывается, что массив - это не случайный набор элементов, а какой-то специфический, а потому в каждом конкретном случае разработчики выбирают свой алгоритм.

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

Тьфу!!!Я забыла,что распределение и есть поразрядная))))
0
ISergey
Maniac
Эксперт С++
1409 / 920 / 148
Регистрация: 02.01.2009
Сообщений: 2,749
Записей в блоге: 1
07.07.2009, 16:33 12
Цитата Сообщение от Юляшка Посмотреть сообщение
Хм...а поразрядная сортировка есть?
Алгоритмы сортировок
в самом низу
1
Robert69
Заблокирован
11.12.2014, 17:39 13
А можно Монте-Кристо на паскале?
0
11.12.2014, 17:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2014, 17:39

меню сортировок
Первый case работает хорошо.а два последних не хотят... #include&lt;iostream&gt;...

Несколько сортировок
Пишу программу, которая сортирует матрицу случайных значений пятью...

Варианты сортировок
Здравствуйте! Вот есть два способа сортировки: #include &lt;iostream&gt; using...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru