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

Сортировка с слиянием - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Plazma
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
08.04.2012, 23:09     Сортировка с слиянием #1
Добрый вечер!
Помогите с подсчетом перестановок и сравнений при сортировке с слиянием. Вот нашел код, и ищу легкий способ чтоб посчитать, если хотите выложу код..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.04.2012, 23:09     Сортировка с слиянием
Посмотрите здесь:

C++ Сортировка слиянием
C++ Сортировка слиянием
Сортировка слиянием C++
C++ сортировка слиянием
C++ Сортировка слиянием
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.04.2012, 23:24     Сортировка с слиянием #2
Так же как и в быстрой сортировке(qsort) подсчитывать. Тут есть рядом тема.
Посчитать число сравнений в QuickSort
Plazma
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
08.04.2012, 23:33  [ТС]     Сортировка с слиянием #3
в Quiсk sort-e понятно, сравниваем опорный элемент с остальными из-за этого size-1, а при сортировке с слиянием как? имею ввиду почему добавляем в каунтер size-1?
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.04.2012, 23:36     Сортировка с слиянием #4
покажи функцию сортировки
Plazma
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
09.04.2012, 07:30  [ТС]     Сортировка с слиянием #5
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int a[100];
void merge(int,int,int);
void merge_sort(int low,int high)
{
 int mid;
 if(low<high)
 {
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
void merge(int low,int mid,int high)
{
 int h,i,j,b[10000],k;
 h=low;
 i=low;
 j=mid+1;
 
 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   b[i]=a[h];
   h++;
  }
  else
  {
   b[i]=a[j];
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 for(k=low;k<=high;k++) a[k]=b[k];
}
Добавлено через 7 часов 48 минут
так, куда нужно писать код для подсчета перестановок и сравнивании ?
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
09.04.2012, 10:41     Сортировка с слиянием #6
Потрясающе! Хитро работает, я б не догадался. Правда дополнительный массив использует, к сожалению. Сам додумал?
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int counter;//счётчик перестановок
int a[100];
void merge(int,int,int);
void merge_sort(int low,int high)
{
 int mid;
 if(low<high)
 {
  counter=0;
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
void merge(int low,int mid,int high)
{
 int h,i,j,b[10000],k;
 h=low;
 i=low;
 j=mid+1;
 
 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   b[i]=a[h];
   counter++;
   h++;
  }
  else
  {
   b[i]=a[j];
   counter++;
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   b[i]=a[k];
   counter++;
   i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   counter++;
   i++;
  }
 }
 for(k=low;k<=high;k++) {a[k]=b[k];counter++;}
}
или лучше так
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int a[100];
void merge(int,int,int);
void merge_sort(int low,int high)
{
 int mid;
 if(low<high)
 {
  counter=0;
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
void merge(int low,int mid,int high)
{
 int h,i,j,b[10000],k;
 h=low;
 i=low;
 j=mid+1;
 
 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   b[i]=a[h];
   h++;
  }
  else
  {
   b[i]=a[j];
   j++;
  }
  i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i++;
  }
 }
 for(k=low;k<=high;k++) {a[k]=b[k];}
 counter+=2*(high-low);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2012, 20:15     Сортировка с слиянием
Еще ссылки по теме:

C++ Сортировка слиянием
Сортировка слиянием C++
Сортировка слиянием C++

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

Или воспользуйтесь поиском по форуму:
Plazma
5 / 5 / 0
Регистрация: 20.11.2010
Сообщений: 51
10.04.2012, 20:15  [ТС]     Сортировка с слиянием #7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Сам додумал?
К сожалению, нет. Не достиг пока такого уровня. Кстати ваш counter на втором коде не правильно высчитывает количество перестановок.
Yandex
Объявления
10.04.2012, 20:15     Сортировка с слиянием
Ответ Создать тему
Опции темы

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