C/C++ - [решено] Пара вопросов по Блочной сортировке

[Drongo]

Товарищи! Тут по заданию решил задачу "Блочная сортировка", вроде решил, но такой вопрос, мне кажется, что я не так её решил, как нужно. Не могли бы вы подсказать, насколько я неправильно решил, хотя код рабочий, но можно как-то улучшить конструкцию, например:

1. Хочу, чтобы массив перебирался и вычислялось число у которого чисел в разрядах наибольшее количество, пример: "7" = 1 разряд в числе, "243" - 3 раряда в числе, "23888" - 5 разрядов, "24" - 2 разряда, и т.д. Это нужно для вычисления проходов в цикле for, Чтобы в первом цикле for можно было подставлять вычисленное число, а не вручную, как сейчас "5", мне кажется нужна функция: которая принимает число и переводит его в строку, но я не знаю эту функцию, подскажете?!



Код:

Код: Выделить всё

len = strlen(функция ЧислоВСтроку(ar[j]));

2. И ещё почему при размере массива в 20000 функция работает, а с размером уже больше 20 тысяч вылетает в ошибку?! Проверял только до 100000 и выставлял, число в разрядах "6". Что не так?!

Прочитал тему на форуме

C/C++ - Последовательность чисел

Подумал, а нельзя ли как-нибудь использовать исключающее "И" или "или"?! Для сортировки. Как решено в этой теме 5pliT-ом, если можно то как?!

В общем раскритикуйте мой код или укажате на слабые места, если можно с поправкой. Буду благодарен!



Код:

Код: Выделить всё

// Блочная сортировка---------------------------------------------------------------------------
#include 
using std::cout;
using std::cin;
using std::endl;
#include 
using std::setw;
#include 
#include 
#include 
using std::time;
void bucketSort(int ara[], const int sze);
int main()
{
   const int size = 20000;
   int array[size] = {0};
   int z = 1;
   srand(time(0));
   cout

[5pliT]

Цитата Drongo:



1. Хочу, чтобы массив перебирался и вычислялось число у которого чисел в разрядах наибольшее количество, пример: "7" = 1 разряд в числе, "243" - 3 раряда в числе, "23888" - 5 разрядов, "24" - 2 разряда, и т.д. Это нужно для вычисления проходов в цикле for, Чтобы в первом цикле for можно было подставлять вычисленное число, а не вручную, как сейчас "5", мне кажется нужна функция: которая принимает число и переводит его в строку, но я не знаю эту функцию, подскажете?!

C/C++ - [решено] Пара вопросов по Блочной сортировке

Число в строку приобразует функция:

char * itoa ( int value, char * str, int base );

обычно её можно найти в stdlib.h.

Или можно написать самому примерно так:



Код:

Код: Выделить всё

char* itoa(int val, int base) { 
	char buf[32] = {0}; 
	int i=30; 
	for(;val&&i;--i,val/=base) 
	buf[i]="0123456789abcdef"[val%base]; 
	return &buf[i+1]; 
}

Количество разрядов можно подсчитать ещё проще примерно так:



Код:

Код: Выделить всё

int rzr(int nn) {
	int n=nn,x=0;
	while (n0) { 
		n/=10;
		x++;
	}
	return x;
}

Цитата Drongo:



2. И ещё почему при размере массива в 20000 функция работает, а с размером уже больше 20 тысяч вылетает в ошибку?! Проверял только до 100000 и выставлял, число в разрядах "6". Что не так?!

C/C++ - [решено] Пара вопросов по Блочной сортировке

Думаю дело в диапозонах значений стандартных типов. Попробуйте использовать не int, а long long например.




Цитата Drongo:



Прочитал тему на форуме Последовательность чисел Подумал, а нельзя ли как-нибудь использовать исключающее "И" или "или"?! Для сортировки. Как решено в этой теме 5pliT-ом, если можно то как?!

C/C++ - [решено] Пара вопросов по Блочной сортировке

Исключающее ИЛИ можно использовать для обмена значений. Я не думаю что алгоритм блочной сортировки не меняет элементы массива местами, поэтому тот код также подойдёт.

[pva]

Цитата 5pliT:



использовать не int, а long long например.

C/C++ - [решено] Пара вопросов по Блочной сортировке

Возможно, попробую - доложу о результатах! Функцию itoa знаю, но лишь визуально, меня смущал сам прототип! Попробую!
Цитата 5pliT:



Количество разрядов можно подсчитать ещё проще

C/C++ - [решено] Пара вопросов по Блочной сортировке

Просто огромнейшее спасибо!!!

[pva]

Drongo, отсортируйте массив: 123, 456, 7890 Мне кажется в этом месте:



Код:

Код: Выделить всё

ar[counter++] = TempArray[a][b];

counter превысит 3, если я правильно понял, конечно. Задали массив 3 числа, а после сортировки получили динее...

[Drongo]

pva, Спасибо за ответ и помощь, но
Цитата pva:





Код:

Код: Выделить всё

ar[counter++] = TempArray[a][b];

C/C++ - [решено] Пара вопросов по Блочной сортировке

я не думаю, поскольку индексирование начинается с нуля "0 1 2 3 4 5 6 7 8 9", и потому счётчик counter++ лишь всегда будет равен переменной sz, если sz = 20000, то и counter после собирающего прохода тоже будет равен 20000, поскольку если элемент в массиве TempArray[a] не всегда расположен последовательно, то идёт проверка, если n-й элемент TempArray, не равен нулю, то присвоить массиву ar[] первое значение, и в итоге всё будет правильно, ведь сортируемых чисел только 20000, следовательно, правильных условий тоже будет 20000, сегодня проверял, но всё равно ошибка при значении размера массивов больше чем 20000 то "ошибается", вот тут:



Код:

Код: Выделить всё

TempArray[Ras][j] = ar[j]; // Расположение соответсвенно разряду

Почему?! Незнаю, иной раз сортирует 14 элементов, иной раз 2, иной раз 7, почему так, хоть убейте, не знаю?!

----------------------------------------------------------------------

Привет 5pliT, тут кажись ошибка
Цитата 5pliT:



while (n0) {

C/C++ - [решено] Пара вопросов по Блочной сортировке

может ты имеешь ввиду:



Код:

Код: Выделить всё

while(n < 0 || n > 0)

или

Код:

Код: Выделить всё

while(n < 0 && n > 0)

А по поводу
Цитата 5pliT:



Попробуйте использовать не int, а long long например

C/C++ - [решено] Пара вопросов по Блочной сортировке

разницы то нет, в типе int переменная хранится в 4-х байтах, этого хватит даже больше, чем на миллион если поставлю, кроме того, пробовал без сортировки используя только несортированный массив выводить из функции bucketSort - так функция принимает и выводит значения, вот если бы была ошибка алгоритма, то сортировки бы не было, но тем не менее при размере массива в 20000 всё работает, а больше ни в какую, причём почему-то несколько значений даже "пробуют" сортироваться, вот если не будет трудно, то попробуй на своём компиляторе скопировать мой код и попробовать изменить всего два значения, я их выделил жирным шрифтом:



Код:

Код: Выделить всё

int main()
{
 const int size = 20000;
 int array[size] = {0};
....

и тут:



Код:

Код: Выделить всё

void bucketSort(int ar[], const int sz)
{
 const int Rasryad = 10; 
 const int Position = 20000;
 int TempArray[Rasryad][Position] = {0};
....

Разряды не трогаем, поскольку в 50000 и в 20000 по 5 разрядов в числе, попробуй пожалуйста, посмотри что за ошибка?! Проблема явно не в типе переменной, стопроцентно!

[5pliT]

Цитата Drongo:



Привет 5pliT, тут кажись ошибка

Цитата 5pliT:while (n0) { »

C/C++ - [решено] Пара вопросов по Блочной сортировке

Ой, прошу прощения. В голове языки путаются - это знак "не равно" в паскале. А в си это так: !=



Где у вас ошибка я не знаю, это отлавливать надо. Но думаю, что или в этой строчке:

TempArray[Ras][j] = ar[j];

или в этой:

ar[counter++] = TempArray[a];

[pva]

Цитата 5pliT:



А в си это так: !=

C/C++ - [решено] Пара вопросов по Блочной сортировке

Спасибо я уже догадался! )))

Буду разбираться...

[pva]

Drongo, с алгоритмом похоже всё в порядке. Интересно, на каком компиляторе вы собирали и отлаживали? у меня сразу при входе в bucketSort вышла ошибка stack overflow. Варианта решения 2: сказать компилятору увеличить стек или использовать динамическую память. Вот в таком виде всё заработало:

Код: Выделить всё

void bucketSort(int ar[], const int sz)
{
   const int Rasryad = 10;
   const int Position = 100000;
   vector<int> mem_TempArray(Position*Rasryad);
   int* TempArray[Rasryad];
   for(unsigned n=0; n<Rasryad; ++n) TempArray[n] = &mem_TempArray[Position*n];
   int /*lenght = 0, temp,*/ number = 1, Ras, counter = 0;;
   // Распределяющий проход
   for(int i = 0; i < 5; i++){ // Проход столько, сколько разряда у числа
       for(int j = 0; j < sz; j++){ // Проход столько, сколько чисел в массиве
           Ras = ar[j] / number % 10; // Вычисление позиции разряда
           TempArray[Ras][j] = ar[j]; // Расположение соответсвенно разряду
         }
       // Собирающий проход после каждого распределяющего
	   counter = 0;
       for(int a = 0; a < Rasryad; a++){
           for(int b = 0; b < Position; b++){
               if(TempArray[a][b] != 0){
                  ar[counter++] = TempArray[a][b];
                  TempArray[a][b] = 0;
                 }
             }
         }
       number *= 10;
     }
    for(int i = 0; i < sz; i++) // Вывод сортированного массива
      cout<<setw(8)<<ar[i];
}
//-------------------------------------------------------------------------

[pva]

Цитата pva:



Интересно, на каком компиляторе вы собирали и отлаживали?

C/C++ - [решено] Пара вопросов по Блочной сортировке

Borland C++ Builder


Цитата pva:



vector mem_TempArray(Position*Rasryad);

C/C++ - [решено] Пара вопросов по Блочной сортировке

Цитата pva:



стек

C/C++ - [решено] Пара вопросов по Блочной сортировке

Этого я не изучал ещё....


Цитата pva:



динамическую память.

C/C++ - [решено] Пара вопросов по Блочной сортировке

- а вот это через оператор new Но похоже не то... А Вам огромное спасибо, за подсказку, а отчего такая ошибка получается?! Подскажите?! Это мне интересно очень!!! Насколько я знаю, vector контейнерный класс, да?!

[pva]

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



Код:

Код: Выделить всё

// каждый вызов func1 должен иметь собственную память для x
void func1(int z)
{
   int x = z;
   ...
   if (0

Делается это просто. Есть участок памяти, называемый "стек". Он и действует по принципу "последний зашёл, первый вышел". Есть специальный регистр процессора, содержит адрес дна стека (допустим SP). При входе в функцию ей даётся память от SP-n до SP, где n - количество байт, требуемых для функции и SP уменьшается на n. При возврате из функции SP обратно увеличивается на n.



Код:

Код: Выделить всё

// древний компьютер (карта памяти в килобайтах):
// R - ПЗУ, P - код программы, S - стек (задом-наперёд), пробелы - свободная память
// 00k RRRRRRRR 16k PPP      SSS 32k
// свободная память постоянно уменьшается с ростом стека

сейчас сохранился тот же подход, с отличием, что страницы памяти стека могут и не быть загружены в физическую память и лежат в произвольном порядке. И ещё есть искусственное ограничение на размер стека. У меня в настройках проекта стояла цифра 1МБ. Более подробно о стеке можно прочитать в википедии.



template class vector {...} - это шаблон C++ контейнера с упорядоченным расположением элементов в свободной памяти. Контейнер - не в том смысле, в каком употребляется в гуишных библиотеках, а для хранения одинаковых структур в памяти. В угловых скобках пишется класс, для которого (основные ограничения):

1. есть явный конструктор по умолчанию explicit T() и конструктор копирования T(const T&)

2. нет побочных эффектов при копировании

3. нет чистых вируальных функций

при раскрытии шаблона создаётся новый класс, который имеет такое хитрое имя vector.



можно сделать через оператор new:



Код:

Код: Выделить всё

int* mem_TempArray = new int[Position*Rasryad];
...
delete[] mem_TempArray;

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