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

Подскажите что не в моем коде(Сортировка слиянием) - C++

Восстановить пароль Регистрация
 
ShookTrooper
0 / 0 / 0
Регистрация: 19.03.2012
Сообщений: 3
05.04.2012, 03:36     Подскажите что не в моем коде(Сортировка слиянием) #1
Я не очень понимаю где именно неверно в моем коде. Хотел рассортировать массив методом слияния. Если найдете заранее спасибо!

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
int* getFirstHalf(int* array, int n){
    int size=n/2+n%2;
   int* a=new int[size];
   for (char i=0; i<size;i++)
    a[i]=array[i];
   return a;
}
 
int* getSecondHalf(int* array, int n){
   int size=n/2;
   int* b=new int[size];
   for (char i=0; i<size; i++)
      b[i]=array[i+size];
   return b; 
}
 
 
 
int* merge(int* a, int* b, int n){
    int* c = new int[n];
   int imax=sizeof(a)/4;
   int jmax=sizeof(b)/4;
   int i=0;
   int j=0;
   int k=0;
   while (i<=n/2+n%2 && j<=n/2)
   {
    if (a[i]<b[j]){
        c[k]=a[i];
        i++;
        k++;
    }
        else{
        c[k]=b[j];
        k++;
        j++;
    }
    if (i>=n/2+n%2)
      {
        for (;j<n/2;j++)
         {
            c[k]=b[j];
            k++;
         }
      }
      if (j>=n/2)
      {
        for (;i<n/2+n%2;i++){
            c[k]=a[i];
            k++;
         }
 
      }
 
   }
    return c;
}
 
 
int* merge_sort(int* array, int n){
    if (n==1) return array;
   int* a = getFirstHalf(array,n);
   int* b = getSecondHalf(array,n);
    merge_sort(a, n/2);
   merge_sort(b, n/2 );
   array=merge(a, b, n);
}
 
 
 
int main(){
   const n=3;
   int A[n]={4,2,1};
 
 
   printf("before: \n");
   for (char i=0; i<n; i++)
    cout<<A[i]<<"  ";
   merge_sort(A, n);
   printf("\nafter:\n");
   for (char i=0; i<n; i++)
    cout<<A[i]<<"  ";
  
    getch(); return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alexey31415
 Аватар для alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 04:23     Подскажите что не в моем коде(Сортировка слиянием) #2
Цитата Сообщение от ShookTrooper Посмотреть сообщение
for (char i=0; i<size;i++)
* a[i]=array[i]
i не char,а int,как вы вообще представляете себе работу этого цикла
Цитата Сообщение от ShookTrooper Посмотреть сообщение
int imax=sizeof(a)/4;
* int jmax=sizeof(b)/4
тут нужно было написать sizeof(имя_массива)/sizeof(T),где Т - тип переменной в массиве

Добавлено через 7 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<vector>//MergeSort.h
using std::vector;
 
class MergeSort
{
public:
    MergeSort(int);
    void sort();
private:
    int size;
    vector<int> data;
    void sortSubVector(int,int);
    void merge(int,int,int,int);
};
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
using std::cin;
using std::cout;
using std::endl;
 
#include<cstdlib>
using std::rand;
using std::srand;
 
#include<ctime>
using std::time;
 
#include<vector>
using std::vector;
 
#include "MergeSort.h"
 
MergeSort::MergeSort(int vectorSize)
{
    size = (vectorSize > 0 ? vectorSize : 10);
    srand(time(0));
 
    for(int i = 0;i < size;i++)
        data.push_back(10 + rand()%90);
}
 
void MergeSort::sort()
{
    sortSubVector(0,size-1);
}
 
void MergeSort::sortSubVector(int low,int high)
{
    if((high - low) >= 1)
    {
        int middle1 = (low + high)/2;
        int middle2 = middle1 + 1;
 
        sortSubVector(low,middle1);
        sortSubVector(middle2,high);
 
        merge(low,middle1,middle2,high);
    }
}
 
void MergeSort::merge(int left,int middle1,int middle2,int right)
{
    int leftIndex = left;
    int rightIndex = middle2;
    int combinedIndex = left;
    vector<int> combined(size);
 
 
    while(leftIndex <= middle1 && rightIndex <= right)
    {
        if(data[leftIndex] <= data[rightIndex])
            combined[combinedIndex++] = data[leftIndex++];
        else
            combined[combinedIndex++] = data[rightIndex++];
    }
 
    if(leftIndex == middle2)
    {
    while(rightIndex <= right)
        combined[combinedIndex++] = data[rightIndex++];
    }
    else
    {
        while(leftIndex <= middle1)
        combined[combinedIndex++] = data[leftIndex++];
    }
 
    for(int i = left;i <= right;i++)
        data[i] = combined[i];
 
    cout <<endl;
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
05.04.2012, 04:47     Подскажите что не в моем коде(Сортировка слиянием) #3
char это целочисленный тип, и цикл с использованием char как счетчик будет нормально работать, естественно если не нужно больше 255 итераций ( и то это если unsigned char, если signed то 127 ). Но зачем? Чем не устраивает int? В идеале вообще в качестве счетчиков и размерностей массивов желательно использовать тип size_t.
alexey31415
 Аватар для alexey31415
59 / 59 / 3
Регистрация: 16.05.2010
Сообщений: 632
05.04.2012, 05:01     Подскажите что не в моем коде(Сортировка слиянием) #4
Цитата Сообщение от Toshkarik Посмотреть сообщение
char это целочисленный тип, и цикл с использованием char как счетчик будет нормально работать
точно,что-то я поспешил,спасибо,теперь уж точно не забуду
Yandex
Объявления
05.04.2012, 05:01     Подскажите что не в моем коде(Сортировка слиянием)
Ответ Создать тему
Опции темы

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