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

Подкорректировать код (сортировка распределением) - C++

Восстановить пароль Регистрация
 
GraBLYA
-46 / 1 / 0
Регистрация: 28.02.2013
Сообщений: 62
15.04.2014, 00:00     Подкорректировать код (сортировка распределением) #1
Вечер добрый, знатоки. Компилятор ошибку не отлавливает. Ошибка логическая и вылет программы происходит при входе в цикл:
C++
1
 while (j > (l[k] - 1))
Алгоритм слизал с хаб*ара.

Может не правильно перевел с java на сишку, из за идентичного синтаксиса мог что-то упустить.
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 //FlashSort, применив которую получим
    //почти упорядоченный массив
 void FlashSort(int *a , int size)  {
    
        //int n = a.length; //Размерность массива
        int m = size * 0.42; //Количество классов
        int  *l  = new int[m]; //Вспомогательный массив
        
        int i = 0, j = 0, k = 0; //Счётчики в циклах
        for (i = 0; i< size; i++)
        l[i]= 0;
        int anmin = a[0]; //Минимальный элемент
        int nmax = 0; //Индекс максимального элемента
        cout<<" 1 \n";
        //Ищем минимальный и максимальный элементы
        for (i = 1; i < size; i++) {
            if (a[i] < anmin)
                anmin = a[i];
            if (a[i] > a[nmax])
                nmax = i;
        }
        
        //Минимум = максимум? Тогда массив
        //состоит из одинаковых элементов.
        //А значит, он отсортирован!
        if (anmin == a[nmax])
            return;
        cout<<" 2 \n";
        //Неизменяемая часть квантиля
        double c1 = ( m - 1) / (a[nmax] - anmin);
        cout<<" 3 \n";
        //Заполняем массив распределения
        //Каждый элемент вспомогательного массива -
        //это количество чисел соответствующего класса
        for (i = 0; i < size; i++) {
            k = (c1 * (a[i] - anmin));
            l[k]++;
        }
        cout<<" 4 \n";
        //Во вспомогательном массиве каждый элемент
        //(начиная со 2-го)увеличим на величину предыдущего.
        //После этого каждый элемент вспомогательного массива
        //это индекс элемента в основном массиве на котором 
        //должны заканчиваются числа соответсвующего класса
        for (k = 1; k < m; k++){
            l[k] += l[k - 1];
            cout<<"l[k] = "<< l[k];
        }
        cout<<" 5 \n";
        //Меняем местами первый и максимальный элемент в массиве
        //Это делается для того чтобы в основном цикле алгоритма
        //максимальный элемент сразу поставить на своё место
        int hold = a[nmax];
        a[nmax] = a[0];
        a[0] = hold;
    
        //Основной алгоритм
        cout<<" 6 \n";
        //Количество элементов, перемещённых
        // в их правильные классы
        int nmove = 0; 
        
        //Временный контейнер, в которую будем помещать элементы
        //на чьи места только что вставили "правильные" элементы
        int flash;
        
        //Индекс неупорядоченного элемента 
        //начинающего новый класс, элементы которого ещё
        //не перемещены
        j = 0;
        
        //Класс очередного перемещаемого элемента
        //это число всегда в пределах от 1..m-1
        k = m - 1;      
     
        int o = 0;
        while (nmove < size - 1) 
        {       
            cout<<" j = "<< j << "(l[k]-1) ="<< (l[k]-1)<<endl;
            while (j > (l[k] - 1)) 
                {
                j++;
                cout<< "c1 = "<<c1<<endl;
                k = (c1 * (a[j] - anmin));
             
            }
            flash = a[j];
            cout<< " j = "<< j << "  l[k] ="<< l[k]<<endl;
            while (!(j == l[k])) {
                
            //  cout<<o++<<endl;
                hold = a[l[k] - 1];
                a[l[k] - 1] = flash;
                flash = hold;
                
                l[k]--;
                nmove++;
               
            }           
        }
         
  //     for (i = 0; i < size; i ++)
   //     cout<<a[i]<<" ";
    }
 
    //Финальная сортировка простыми вставками
    //Досортировывает то что не отсортировало FlashSort
void InsertionSort(int *a, int size)  
    {
        int i, j, hold;
        for (i=size-3; i>=0; i--) { 
            if (a[i+1] < a[i]) {
                hold = a[i];
                j=i;
                while (a[j+1] < hold) {
                    a[j] = a[j+1];
                    j++;
                }
                a[j] = hold;            
            }
        }
    }
За помощь буду крайне благодарен.

Добавлено через 22 минуты
Собственно код на Java
Java
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import java.util.Arrays;
 
public class FlashSortAlgorithm extends SortAlgorithm {
 
    void sort(int[] a) throws Exception {
    
       FlashSort(a); //Сначала FlashSort
       InsertionSort(a); //Напоследок сортировка вставками
       
    }
 
    //FlashSort, применив которую получим
    //почти упорядоченный массив
    private void FlashSort(int [] a) throws Exception {
    
        int n = a.length; //Размерность массива
        int m = n * 0.42; //Количество классов
        int [] l = new int[m]; //Вспомогательный массив
 
        int i = 0, j = 0, k = 0; //Счётчики в циклах
        int anmin = a[0]; //Минимальный элемент
        int nmax = 0; //Индекс максимального элемента
        
        //Ищем минимальный и максимальный элементы
        for (i = 1; i < n; i++) {
            if (a[i] < anmin)
                anmin = a[i];
            if (a[i] > a[nmax])
                nmax = i;
        }
        
        //Минимум = максимум? Тогда массив
        //состоит из одинаковых элементов.
        //А значит, он отсортирован!
        if (anmin == a[nmax])
            return;
        
        //Неизменяемая часть квантиля
        double c1 = ((double) m - 1) / (a[nmax] - anmin);
        
        //Заполняем массив распределения
        //Каждый элемент вспомогательного массива -
        //это количество чисел соответствующего класса
        for (i = 0; i < n; i++) {
            k = (int) (c1 * (a[i] - anmin));
            l[k]++;
        }
        
        //Во вспомогательном массиве каждый элемент
        //(начиная со 2-го)увеличим на величину предыдущего.
        //После этого каждый элемент вспомогательного массива
        //это индекс элемента в основном массиве на котором 
        //должны заканчиваются числа соответсвующего класса
        for (k = 1; k < m; k++){
            l[k] += l[k - 1];
        }
 
        //Меняем местами первый и максимальный элемент в массиве
        //Это делается для того чтобы в основном цикле алгоритма
        //максимальный элемент сразу поставить на своё место
        int hold = a[nmax];
        a[nmax] = a[0];
        a[0] = hold;
    
        //Основной алгоритм
        
        //Количество элементов, перемещённых
        // в их правильные классы
        int nmove = 0; 
        
        //Временный контейнер, в которую будем помещать элементы
        //на чьи места только что вставили "правильные" элементы
        int flash;
        
        //Индекс неупорядоченного элемента 
        //начинающего новый класс, элементы которого ещё
        //не перемещены
        j = 0;
        
        //Класс очередного перемещаемого элемента
        //это число всегда в пределах от 1..m-1
        k = m - 1;      
        
        while (nmove < n - 1) {     
            while (j > (l[k] - 1)) {
                j++;
                k = (int) (c1 * (a[j] - anmin));
            }
            flash = a[j];
            while (!(j == l[k])) {
                k = (int) (c1 * (flash - anmin));
 
                hold = a[l[k] - 1];
                a[l[k] - 1] = flash;
                flash = hold;
 
                l[k]--;
                nmove++;
            }           
        }
    }
 
    //Финальная сортировка простыми вставками
    //Досортировывает то что не отсортировало FlashSort
    private void InsertionSort(int [] a) throws Exception {
        int i, j, hold;
        for (i=a.length-3; i>=0; i--) { 
            if (a[i+1] < a[i]) {
                hold = a[i];
                j=i;
                while (a[j+1] < hold) {
                    a[j] = a[j+1];
                    j++;
                }
                a[j] = hold;            
            }
        }
    }
 
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
bav1003
0 / 0 / 1
Регистрация: 11.04.2014
Сообщений: 3
15.04.2014, 16:54     Подкорректировать код (сортировка распределением) #2
А как проверяли? Вроде бы, все работает:
(2:1)user@linux:~/test/c++/java>java t_FlashSort
enter n:3
3 2 1
1 2 3
enter n:10
5 4 3 2 1 9 7 8 6 0
0 1 2 3 4 5 6 7 8 9
enter n:^C
(2:1)user@linux:~/test/c++/java>./t_sort
enter n:3
3 2 1
2
3
4
5
6
j = 0(l[k]-1) =2
j = 0 l[k] =3
1 2 3
enter n:10
5 4 3 2 1 9 8 7 6 0
2
3
4
l[k] = 10l[k] = 10l[k] = 10 5
6
j = 0(l[k]-1) =9
j = 0 l[k] =10
0 1 2 3 4 5 6 7 8 9
enter n:^C
В Вашем в коде на C++ я не обнаружил функции sort:
C++
1
2
3
4
 void sort(int *a , int size)  {
        FlashSort(a,size);
        InsertionSort(a,size);
 }
Может быть в этом дело?
GraBLYA
-46 / 1 / 0
Регистрация: 28.02.2013
Сообщений: 62
15.04.2014, 19:07  [ТС]     Подкорректировать код (сортировка распределением) #3
Конечно же работает, ведь сортировка вставками все сделает без проблем в любом случае.
C++
1
InsertionSort(int *a, int size)
Я проверял смотря на результаты только
C++
1
FlashSort(int *a , int size)
,
которые должны быть почти готовым результатом, но видел только 2-3 перестановки на массив в 15 элементов и даже намёка на сортировку не наблюдал.
bav1003
0 / 0 / 1
Регистрация: 11.04.2014
Сообщений: 3
15.04.2014, 23:09     Подкорректировать код (сортировка распределением) #4
Ну тогда попробуйте:
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
...
          //А значит, он отсортирован!
          if (anmin == a[nmax])
              return;
          cout<<" 2 \n";
          //Неизменяемая часть квантиля
// !!!!!!!!!!!!!!!!!!!!! строка 30 из первого сообщения !!!!!!!!!
         double c1 = ( (double) m - 1) / (a[nmax] - anmin); // вместо double c1 = ( m - 1) / (a[nmax] - anmin);
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 
          cout<<" 3 \n";
          //Заполняем массив распределения
          //Каждый элемент вспомогательного массива -
          //это количество чисел соответствующего класса
          for (i = 0; i < size; i++) {
...
              flash = a[j];
              cout<< " j = "<< j << "  l[k] ="<< l[k]<<endl;
              while (!(j == l[k])) {
                  
              //  cout<<o++<<endl;
// !!!!!!!!!!!!!!!!!!!!! строка 90 из первого сообщения !!!!!!!!!
                k = (int) (c1 * (flash - anmin));           // Из java-кода
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                  hold = a[l[k] - 1];
                  a[l[k] - 1] = flash;
                  flash = hold;
                  
                  l[k]--;
Yandex
Объявления
15.04.2014, 23:09     Подкорректировать код (сортировка распределением)
Ответ Создать тему
Опции темы

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