Блочная сортировка

[vova287]

блочную сортировку задали, но задали не просто а с указателями и т.п т .д ,вроде по алгоритму все, не могу понять почему выбивает. Подскажите пожалуйста

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
using namespace std; 

class element //element 
{
public:
 int value;
 element *next;
 element()
 {
 value=NULL;
 next=NULL;
 }
};

class bucket //bucket containing a perticular range of values 
{
public:
element *firstElement;
bucket()
{
firstElement = NULL;
}
};

void main() 
{
 int lowend=0; // minimum element 
 int highend=100; //max element 
 int interval=10; //number of intervals 
 const int size = 20; 
 const int noBuckets=(highend-lowend)/interval; //number of buckets required 
 bucket *buckets=new bucket[noBuckets]; 
 bucket *temp;

 for(int a=0;a<noBuckets;a++) //creation of required buckets 
 {
 temp=new bucket;
 buckets[a]=*temp;
 }

int array[size];     //выделяем память для массива, который будет содержать неотсортированные данные

srand(time(NULL));
for(int i = 0; i < size; i++)     //заполняем массив случайными числами в интервале от 1 до 100
array[i] = rand() % 300;

cout << "Nosorted array: " << endl << endl;
cout << array;     //выводим на печать неотсортированный массив

 for(int j=0;j<19;j++) //sending elments into appropriate buckets
 {
 cout<<array[j]<<endl;
 element *temp,*pre;
 temp=buckets[array[j]/interval].firstElement;
 if(temp==NULL)//if it is the first element of the bucket
 {
 temp=new element;
 buckets[array[j]/interval].firstElement=temp;
 temp->value=array[j];
 }
 else
 {
 pre=NULL;
 while(temp!=NULL) //move till the appropriate position in the bucket
 {
 if(temp->value>array[j])
 break;
 pre=temp;
 temp=temp->next;
 }
 if(temp->value>array[j]) //if the new value is in betwen or at the begining
 {
 if(pre==NULL) //insertion at first if the bucket has elements already
 {
 element *firstNode;
 firstNode=new element();
 firstNode->value=array[j];
 firstNode->next=temp;
 buckets[array[j]/interval].firstElement=firstNode;
 }
 else //insertion at middle
 {
 element *firstNode;
 firstNode=new element();
 firstNode->value=array[j];
 firstNode->next=temp;
 pre->next=firstNode;
 }
 }
 else// if the new value is to be created at last of bucket
 {
 temp=new element;
 pre->next=temp;
 temp->value=array[j];
 }

 }
 }

 cout<<"------------------------The Sorted Elements Are---------------\n";
 for(int jk=0;jk<10;jk++)
 {
 element *temp;
 temp= buckets[jk].firstElement;
 while(temp!=NULL)
 {
 cout<<"*"<<temp->value<<endl;
 temp=temp->next;
 }
 }
 cout<<"--------------------------------END--------------------------------\n";

}

[Abstraction]

Сообщение от vova287

блочную сортировку задали, но задали не просто а с указателями и т.п т .д ,вроде по алгоритму все, не могу понять почему выбивает. Подскажите пожалуйста

Что именно значит - "выбивает"? Если программа вылетает с ошибкой, то можно (и нужно) воспользоваться отладчиком, чтобы найти конкретную строку и значения переменных, при которых происходит трагедия.

Обращаю внимание, что:

for(int i = 0; i < size; i++)     //заполняем массив случайными числами в интервале от 1 до 100
    array[i] = rand() % 300;

Противоречие кода и комментариев. Дальше, имеем:

 int lowend=0; // minimum element 
 int highend=100; //max element 
 int interval=10; //number of intervals 
 const int size = 20; 
 const int noBuckets=(highend-lowend)/interval; //number of buckets required 
 bucket *buckets=new bucket[noBuckets]; 
//...
temp=buckets[array[j]/interval].firstElement;

Вопрос: чему равно значение noBuckets при инициализации buckets? А чему равно максимально возможное значение array[j]/interval?
Вопрос посложнее: что будет при lowend больше нуля - скажем, 50?

[vova287]

у меня вылетает вот здесь

if(temp->value>array[j])

в комментариях ошибся до 20

и тут немного не понял в чем состоит проблема

чему равно значение noBuckets при инициализации buckets? А чему равно максимально возможное значение array[j]/interval?
Вопрос посложнее: что будет при lowend больше нуля - скажем, 50?

[Abstraction]

Сообщение от vova287

в комментариях ошибся до 20

и тут немного не понял в чем состоит проблема

Ой-ой.

1) В каком диапазоне находится возвращаемое rand() значение?
2) В каком диапазоне находится значение выражения rand() % 300?
3) В каком диапазоне находится значение выражения array[j]/interval?
4) Чему равно noBuckets?
5) Чему может быть равно buckets[noBuckets].firstElement?

Ну, и бонусные вопросы дальше по тексту:
6) Сколько раз выполнится тело цикла for(int j=0;j<19;j++), если внутри него j не меняется?
7) При каком условии произойдёт выход из цикла while(temp!=NULL), если внутри него есть одна команда break, выполняющаяся при некотором условии?
8) Чему равно значение выражения (temp->value>array[j]), если а) temp==NULL, б) (temp->value>array[j]) есть истина?