Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   [решено] Пара вопросов по Блочной сортировке (http://forum.oszone.net/showthread.php?t=97265)

Drongo 03-01-2008 19:33 708326
Пара вопросов по Блочной сортировке
 
Товарищи! Тут по заданию решил задачу "Блочная сортировка", вроде решил, но такой вопрос, мне кажется, что я не так её решил, как нужно. Не могли бы вы подсказать, насколько я неправильно решил, хотя код рабочий, но можно как-то улучшить конструкцию, например:
1. Хочу, чтобы массив перебирался и вычислялось число у которого чисел в разрядах наибольшее количество, пример: "7" = 1 разряд в числе, "243" - 3 раряда в числе, "23888" - 5 разрядов, "24" - 2 разряда, и т.д. Это нужно для вычисления проходов в цикле for, Чтобы в первом цикле for можно было подставлять вычисленное число, а не вручную, как сейчас "5", мне кажется нужна функция: которая принимает число и переводит его в строку, но я не знаю эту функцию, подскажете?!
Код:
len = strlen(функция ЧислоВСтроку(ar[j]));
2. И ещё почему при размере массива в 20000 функция работает, а с размером уже больше 20 тысяч вылетает в ошибку?! Проверял только до 100000 и выставлял, число в разрядах "6". Что не так?!
Прочитал тему на форуме Последовательность чисел Подумал, а нельзя ли как-нибудь использовать исключающее "И" или "или"?! Для сортировки. Как решено в этой теме 5pliT-ом, если можно то как?!
В общем раскритикуйте мой код или укажате на слабые места, если можно с поправкой. Буду благодарен!
Код:
// Блочная сортировка---------------------------------------------------------------------------
#include <iostream.h>
using std::cout;
using std::cin;
using std::endl;

#include <iomanip.h>
using std::setw;

#include <cstring>

#include <stdlib.h>
#include <ctime.h>
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<<" Inizialization array..."<<endl;
  for(int i = 0; i < size; i++)
      array[i] = rand() % size; // Генерация случайных чисел для заполнения массива первоначальными значениями

  for(int j = 0; j < size; j++)
      cout<<setw(8)<<array[j]; // Вывод НЕСОРТИРОВАННОГО массива

  cout<<"----------------------------------------------------------------------"<<endl<<endl<<endl;

  bucketSort(array, size); // Функция сортировки

  cin>>z;
 
  return 0;
}
//---------------------------------------------------------------------------
void bucketSort(int ar[], const int sz)
{
  const int Rasryad = 10;
  const int Position = 20000;
  int TempArray[Rasryad][Position] = {0};
  int /*lenght = 0,*/ temp, number = 1, Ras, counter = 0;;

//  for(int j = 0; j < sz; j++){
  //    temp = strlen((ar[j]));
    //  if(lenght < temp)
      //    lenght = temp;
    //}

  // Распределяющий проход
  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];
}
//-------------------------------------------------------------------------

5pliT 04-01-2008 21:19 709034
Цитата:
Цитата Drongo
1. Хочу, чтобы массив перебирался и вычислялось число у которого чисел в разрядах наибольшее количество, пример: "7" = 1 разряд в числе, "243" - 3 раряда в числе, "23888" - 5 разрядов, "24" - 2 разряда, и т.д. Это нужно для вычисления проходов в цикле for, Чтобы в первом цикле for можно было подставлять вычисленное число, а не вручную, как сейчас "5", мне кажется нужна функция: которая принимает число и переводит его в строку, но я не знаю эту функцию, подскажете?! »
Число в строку приобразует функция:
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 (n<>0) {
                n/=10;
                x++;
        }
        return x;
}
Цитата:
Цитата Drongo
2. И ещё почему при размере массива в 20000 функция работает, а с размером уже больше 20 тысяч вылетает в ошибку?! Проверял только до 100000 и выставлял, число в разрядах "6". Что не так?! »
Думаю дело в диапозонах значений стандартных типов. Попробуйте использовать не int, а long long например.

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

Drongo 04-01-2008 21:26 709040
Цитата:
Цитата 5pliT
использовать не int, а long long например. »
Возможно, попробую - доложу о результатах! Функцию itoa знаю, но лишь визуально, меня смущал сам прототип! Попробую!
Цитата:
Цитата 5pliT
Количество разрядов можно подсчитать ещё проще »
Просто огромнейшее спасибо!!!

pva 04-01-2008 22:11 709064
Drongo, отсортируйте массив: 123, 456, 7890 Мне кажется в этом месте:
Код:
ar[counter++] = TempArray[a][b];
counter превысит 3, если я правильно понял, конечно. Задали массив 3 числа, а после сортировки получили динее...

Drongo 05-01-2008 19:31 709632
pva, Спасибо за ответ и помощь, но
Цитата:
Цитата pva
Код:
ar[counter++] = TempArray[a][b];
»
я не думаю, поскольку индексирование начинается с нуля "0 1 2 3 4 5 6 7 8 9", и потому счётчик counter++ лишь всегда будет равен переменной sz, если sz = 20000, то и counter после собирающего прохода тоже будет равен 20000, поскольку если элемент в массиве TempArray[a][b] не всегда расположен последовательно, то идёт проверка, если n-й элемент TempArray, не равен нулю, то присвоить массиву ar[] первое значение, и в итоге всё будет правильно, ведь сортируемых чисел только 20000, следовательно, правильных условий тоже будет 20000, сегодня проверял, но всё равно ошибка при значении размера массивов больше чем 20000 то "ошибается", вот тут:
Код:
TempArray[Ras][j] = ar[j]; // Расположение соответсвенно разряду
Почему?! Незнаю, иной раз сортирует 14 элементов, иной раз 2, иной раз 7, почему так, хоть убейте, не знаю?!
----------------------------------------------------------------------
Привет 5pliT, тут кажись ошибка
Цитата:
Цитата 5pliT
while (n<>0) { »
может ты имеешь ввиду:
Код:
while(n < 0 || n > 0)
или
Код:
while(n < 0 && n > 0)
А по поводу
Цитата:
Цитата 5pliT
Попробуйте использовать не int, а long long например »
разницы то нет, в типе 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 06-01-2008 12:02 710004
Цитата:
Цитата Drongo
Привет 5pliT, тут кажись ошибка
Цитата 5pliT:while (n<>0) { » »
Ой, прошу прощения. В голове языки путаются :) <> - это знак "не равно" в паскале. А в си это так: !=

Где у вас ошибка я не знаю, это отлавливать надо. Но думаю, что или в этой строчке:
TempArray[Ras][j] = ar[j];
или в этой:
ar[counter++] = TempArray[a][b];

Drongo 06-01-2008 21:19 710494
Цитата:
Цитата 5pliT
А в си это так: != »
Спасибо я уже догадался! )))
Буду разбираться...

pva 07-01-2008 13:32 711016
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];
}
//-------------------------------------------------------------------------

Drongo 07-01-2008 20:09 711330
Цитата:
Цитата pva
Интересно, на каком компиляторе вы собирали и отлаживали? »
Borland C++ Builder
Цитата:
Цитата pva
vector<int> mem_TempArray(Position*Rasryad); »
Цитата:
Цитата pva
стек »
Этого я не изучал ещё....
Цитата:
Цитата pva
динамическую память. »
- а вот это через оператор new Но похоже не то... А Вам огромное спасибо, за подсказку, а отчего такая ошибка получается?! Подскажите?! Это мне интересно очень!!! Насколько я знаю, vector контейнерный класс, да?!

pva 08-01-2008 16:50 711831
Начиная ещё с первых компьютеров разработали хитрую систему для передачи данных между блоками программы и для выделения памяти под собственные нужды блоков. ПРичём надо было сделать так, чтобы
Код:
// каждый вызов func1 должен иметь собственную память для x
void func1(int z)
{
  int x = z;
  ...

  if (0<x) func1(x-1);
}
Делается это просто. Есть участок памяти, называемый "стек". Он и действует по принципу "последний зашёл, первый вышел". Есть специальный регистр процессора, содержит адрес дна стека (допустим SP). При входе в функцию ей даётся память от SP-n до SP, где n - количество байт, требуемых для функции и SP уменьшается на n. При возврате из функции SP обратно увеличивается на n.
Код:
// древний компьютер (карта памяти в килобайтах):
// R - ПЗУ, P - код программы, S - стек (задом-наперёд), пробелы - свободная память
// 00k RRRRRRRR 16k PPP      SSS 32k
// свободная память постоянно уменьшается с ростом стека
сейчас сохранился тот же подход, с отличием, что страницы памяти стека могут и не быть загружены в физическую память и лежат в произвольном порядке. И ещё есть искусственное ограничение на размер стека. У меня в настройках проекта стояла цифра 1МБ. Более подробно о стеке можно прочитать в википедии.

template<typename T> class vector {...} - это шаблон C++ контейнера с упорядоченным расположением элементов в свободной памяти. Контейнер - не в том смысле, в каком употребляется в гуишных библиотеках, а для хранения одинаковых структур в памяти. В угловых скобках пишется класс, для которого (основные ограничения):
1. есть явный конструктор по умолчанию explicit T() и конструктор копирования T(const T&)
2. нет побочных эффектов при копировании
3. нет чистых вируальных функций
при раскрытии шаблона создаётся новый класс, который имеет такое хитрое имя vector<T>.

можно сделать через оператор new:
Код:
int* mem_TempArray = new int[Position*Rasryad];
...
delete[] mem_TempArray;
но в случае исключения память освобождена не будет (а вектор всегда освобождает за собой память)

Drongo 08-01-2008 23:41 712082
Доброго здоровья и с прошедшим Рождеством!
Цитата:
Цитата pva
"стек". Он и действует по принципу "последний зашёл, первый вышел". »
Да, спасибо большое, я сегодня читал, по классу vector есть ещё list и deque, прочитал, что vector и deque, более "близки" по принципу, добавляют данные только в начало или в конец, а list, может добавлять в середину списка
Цитата:
Цитата pva
template<typename T> »
шаблоны изучал, но не глубинно, ещё знаю, что есть стеки, очереди, деревья, списки, также, что принцип - "первый вошёл - первый вышел", "первый вошёл - последний вышел", но это я ещё буду основательно изучать в скором времени, но коль столкнулся уже сейчас, то почему бы паралельно не захватить багаж знаний касательно сих вещей, Вам,pva, с глубоким уважением жму руку, за терпение к моим вопросам! А так же 5pliT'у! Ошибку компилятор выдавал ту что Вы говорили,
Цитата:
Цитата pva
stack overflow »
, мне казалось, что при размере большем, чем 20000, массив правильно не выделяется, и элементам не "удаётся правильно" расположиться последовательно, поэтому происходит такая ошибка... pva, Вы могли бы мне объяснить эти строки или поправить меня?! Я сейчас напишу, как я их понял.
1.
Код:
vector<int> mem_TempArray(Position * Rasryad);
 int* TempArray[Rasryad];
Вы создаёте массив целых чисел и приводите его к типу vector, а потом создаём массив указателей TempArray на целое число, для того, чтобы хранились не числа, а адреса, так будет "дешевле" для памяти... Поправьте, или дополните мои пробелы в объяснении.
И вот эту строку.
2.
Код:
for(unsigned n = 0; n < Rasryad; ++n) TempArray[n] = &mem_TempArray[Position * n];
Здесь, я немного не понял, &, операция адресации, возвращает адрес своего правого операнда, а потому, думаю, что присваивает адрес массиву указателей! [Position * n] - это расположение элементов соответствено чему?! К примеру, Position = 20000;, а n = 2;, то при умножении, будет TempArray[2] = &mem_TempArray[40000];, тоесть, третьему элементу массива TempArray, присвоится значение... я тут запутался... Объясните пожалуйста...
Кстати, с Вашей модификацией, действительно всё работает на Ура!!!

pva 09-01-2008 19:06 712667
по пунктам:
1. по правилам C++ vector<int> mem_TempArray(Position * Rasryad); читается как объявление переменной типа vector<int> (это как раз хитрое имя типа) с именем mem_TempArray и использованием конструктора
vector<int>::vector<int>(unsigned size, const int& init = int());
второй массив позволяет не переписывать ваш код (на самом деле есть много способов эффективно обойтись без него).
В нашем случае каждому элементу TempArray присваивается адрес каждого последовательного блока размером Position. То есть адрес начала каждой строчки.

2. В C++ можно переопределять почти все операторы. У vector<T> есть операторы:
Код:
const T& vector<T>::operator[](unsigned pos) const;
T& vector<T>::operator[](unsigned pos);
они возвращают ссылку на элемент по номеру pos. Адрес ссылки - это адрес памяти этого элемента.
таким образом, если у нас vector<int>, Position=10000, то каждому n-ному элементу TempArray присваивается адрес _data + n*10000*sizeof(int), где _data - это адрес куска, который занял вектор.

на всякий случай напомню, что для 32-разрядной ОС windows виртуальная память линейная, размером до 4Gb и считается, что типы данных имеют значения (гробо):
short -32K..+32K
long -2G..+2G
int -2G..+2G
unsigned short 0K..+64K
unsigned long 0K..+4G
unsigned int 0K..+4G
то есть теоретически в вектор может поместиться (4G - _data)/sizeof(T) значений. Думаю 100 миллионов int в памяти поместятся легко (только в глубокий свап уйдут)

Drongo 09-01-2008 19:28 712679
Цитата:
Цитата pva
В нашем случае каждому элементу TempArray присваивается адрес каждого последовательного блока размером Position. То есть адрес начала каждой строчки. »
И мы имеем не один громадный массив, а несколько малых по сравнению с двухмерным, вернее адресов на них! Спасибо большое!!!


Время: 22:14.

Время: 22:14.
© OSzone.net 2001-