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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Компилятор Borland C++ 3.1 http://www.cyberforum.ru/cpp-beginners/thread1148602.html
Здравствуйте, на учебе нам поручили делать лабораторные по C++, которые я как раз и сделал. Но, увы строгому преподавателю крайне не нравится что мои программы (которые писал на своём ноутбуке, в Dev...
C++ Курсач.(Вывод графика) Вот задание Модифицируйте текст эталонного проекта "Выпуклая оболочка" так, чтобы индуктивно определить количество вершин выпуклой оболочки лежащей внутри окружности. Координаты центра и радиус... http://www.cyberforum.ru/cpp-beginners/thread1148600.html
Обработка массивов C++
Всем привет. Ребяят, нужна помощь: Задан массив А размера N (N - нечетное число). Вывести его элементы с нечетными номерами в порядке убывания номеров: AN, AN-2, AN-4,..., A1. Условный оператор не...
C++ Программа , которая выводит время, за которое программа работает
Вообщем, нужно что бы считалось время от начала работы программы, и выводилось на экран.
C++ Сортировка, используя кучи Windows (ошибки в коде) http://www.cyberforum.ru/cpp-beginners/thread1148580.html
Форумчане, прошу вашей помощи в ликвидации ошибок в приведенном ниже коде. Я сам не очень силен в C++, поэтому ошибки могут быть совсем простыми. // HeapSortSPO.cpp : Defines the entry point for...
C++ Задан текст, слова которого разделены % Задан текст, слова которого разделены %. Выяснить и вывести на экран, какой процент слов в тексте начинается на заданную букву (буква вводится с клавиатуры) ... подробнее

Показать сообщение отдельно
GraBLYA
-46 / 1 / 0
Регистрация: 28.02.2013
Сообщений: 62

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

15.04.2014, 00:00. Просмотров 627. Ответов 3
Метки (Все метки)

Вечер добрый, знатоки. Компилятор ошибку не отлавливает. Ошибка логическая и вылет программы происходит при входе в цикл:
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;            
            }
        }
    }
 
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru