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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 92, средняя оценка - 4.74
Monte-Cristo
2789 / 1375 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
#1

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

31.03.2009, 20:10. Просмотров 13519. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритмы сортировок (C++):

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

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

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

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

Сравнение сортировок - C++
Помогите с подсчетом количества сравнений в сортировках. Проблема заключается в том, что количество операций у сортировок практически...

меню сортировок - C++
Первый case работает хорошо.а два последних не хотят... #include&lt;iostream&gt; #include&lt;ctime&gt; using namespace std; void main() { ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
jelenad
Сообщений: n/a
19.04.2009, 22:26 #2
Сортировка Shell -как это все сделать используя аплеты java?
Gulnaz
5 / 5 / 0
Регистрация: 14.03.2008
Сообщений: 74
21.04.2009, 15:03 #3
Любопытно,какой метод работает быстрее всех для очень больших массивов?
0
Gravity
562 / 556 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
21.04.2009, 15:05 #4
Цитата Сообщение от Gulnaz Посмотреть сообщение
Любопытно,какой метод работает быстрее всех для очень больших массивов?
Метод быстрой сортировки (Хоара).
0
Gulnaz
5 / 5 / 0
Регистрация: 14.03.2008
Сообщений: 74
21.04.2009, 15:09 #5
А для небольших массивов?
0
grrrrr
45 / 45 / 7
Регистрация: 21.04.2009
Сообщений: 265
30.06.2009, 09:50 #6
Monte-Cristo, а метод простого включения и метод вставками это один и тот же алгоритм?
0
Monte-Cristo
2789 / 1375 / 30
Регистрация: 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
Эксперт С++
8288 / 3508 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
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
17815 / 6025 / 388
Регистрация: 30.03.2009
Сообщений: 16,554
Записей в блоге: 26
06.07.2009, 16:25 #10
По поводу того, какой метод сортировки работает быстрее. Самого быстрого метода нет, потому как в одном случае может быстрее отработать один метод,а вдругом - другой. Под случаями я имею ввиду входной массив. При этом в реальной жизни как правило оказывается, что массив - это не случайный набор элементов, а какой-то специфический, а потому в каждом конкретном случае разработчики выбирают свой алгоритм.

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

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

Несколько сортировок - C++
Пишу программу, которая сортирует матрицу случайных значений пятью сортировками. Для A&gt;B Программа работает на &quot; Ура&quot;. Но как B&gt;A...

Варианты сортировок - C++
Здравствуйте! Вот есть два способа сортировки: #include &lt;iostream&gt; using namespace std; int main () { const int n=20; ...

3 вида сортировок - C++
Добрый вечер, помогите решить лабораторную. Мне надо написать программу которая сортирует одномерный массив методом выбора, пузырька и...

ЛР: Сравнение сортировок - C++
нужно экспериментально сравнить временную сложность и провести качественный анализ трех сортировок: выбором шейкерная слиянием...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.12.2014, 17:39
Ответ Создать тему
Опции темы

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