Заметки о рекурсии

[Гром]

ysv_, Alf,

По стандарту записи
*  - ОДИН любой символ - он не может быть пустым - пустой бывает строка - пустой символ = НОНСЕНС - ибо = нет символа!!!

? - означает любые символы в любом колличестве - т.е. в том числе и пустые!!!!

Стандарт содран с bash shell и cmd prompt  - и не спорьте - это не ИМХО - это 100%

Alf, прога называется shell локальный шелл - правила нужны стандартные!!!!

[Alf]

Гром, теперь понял причину недоразумения...
Все с точностью до наоборот: "?" - строго один символ, "*" - любая цепочка, включая пустую.
Если хочешь наоборот - издай указ по королевству, поменяем  
Но стандарт именно таков издревле, ничего не попишешь...

[ysv_]

Кстати, если найдется кто-то желающий представить итеративное решение этой или остальных задач, милости просим. Думаю, сравнение этих двух подходов будет весьма познавательным.

Вот решение с помощью итерации:

bool CompareText(const char*& s, const char*& p)
{
  while (*s!=0 && *p!=0 && *p!='*')
  {
    if (*s!=*p && (*p!='?' || *s==0)) return false;
    ++p;
    ++s;
  }
  if (*p=='*') return true;
  return (*s==0 && *p==0);
}

void SkipAsterisk(const char*&p)
{
  while (*p=='*') ++p;
}

bool FindText(const char*& s, const char*& p)
{
  const char *ss, *pp;
  while (*s!=0)
  {
    ss=s;
    pp=p;
    if (CompareText(ss, pp))
    {
      s=ss;
      p=pp;
      return true;
    }
    ++s;
  }
  return false;
}


bool PattCmp2(const char* s, const char* p)
{
  if (!CompareText(s, p)) return false;
  SkipAsterisk(p);
  while (*s!=0 && *p!=0)
  {
    if (!FindText(s, p)) return false;
    SkipAsterisk(p);
  }
  return (*s==0 && *p==0);
}

[Гром]

Падон перепутал - действительно * любой симовл ? один!!!!

Прашу прастить великадушна !  

[Alf]

ysv_, у меня сравнение любой строки со звездочкой через PattCmp2 выдает отрицательный результат.

[npak]

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

Интересно сравнить разные подходы.

Идея для итеративного подхода -- выписать конечный автомат, который распознаёт строки по заданному шаблону.  Получится, конечно, не классический конечный автомат, так как здесь будут две входных последовательности (шаблон + строка), но здесь это не так важно.

Я прикинул на бумажке -- выходит не очень сложно.  Правда, гложет меня смутное сомнение, что на практике всё может оказаться гораздо сложнее.  Действительно, рекурсия для обработки звёздочки -- красивое и простое решение.

[Alf]

Еще раз благодарю ysv_ за участие в тестировании функции.
Для того, чтобы пустая строка соответствовала шаблону ***... (из произвольного количества звездочек), следует 3-й условный оператор заменить на

Код:

  else if (!*s)
    return ((asterisk == *p++) && ((endofline == *p) || PattCmp(s, p)));

Итак, функция в целом приобретает вид:

Код:

bool PattCmp(const char *s, const char *p)
{
  if (!*s && !*p)
    return true;
  else if (!*p)
    return false;
  else if (!*s)
    return ((asterisk == *p++) && ((endofline == *p) || PattCmp(s, p)));
  else if (asterisk == *p)
  {
    if (endofline == *++p)
      return true;
    else
    {
      bool f;
      do
        f = PattCmp(s++, p);
      while (!f && *s);
      return f;
    }
  }
  else if (question == *p)
    return PattCmp(++s, ++p);
  else
    return (*p == *s) ? PattCmp(++s, ++p) : false;
}

[ysv_]

Подправленный вариант Alf'а:
const char asterisk = '*';
const char question = '?';
const char endofline = '\0';

bool PattCmp(const char *s, const char *p)
{
  if (*s==endofline && *p==endofline) return true;
  else if (*s!=endofline && *p==endofline || *s==endofline && *p!=asterisk)
       return false;
  else if (asterisk == *p)
  {
    if (endofline == *++p) return true;
    else
    {
      bool f;
      do f = PattCmp(s++, p);
      while (!f && *s!=endofline);
      return f;
    }
  }
  else if (question == *p) return PattCmp(++s, ++p);
  else return (*p == *s) ? PattCmp(++s, ++p) : false;
}


Исправленный итеративный вариант:
bool CompareText(const char*& s, const char*& p)
{
  while (*s!=0 && *p!=0 && *p!='*')
  {
    if (*s!=*p && (*p!='?' || *s==0)) return false;
    ++p;
    ++s;
  }
  if (*p=='*') return true;
  return (*s==0 && *p==0);
}

bool FindText(const char*& s, const char*& p)
{
  if (*p==0) return true;
  const char *ss, *pp;
  while (*s!=0)
  {
    ss=s;
    pp=p;
    if (CompareText(ss, pp))
    {
      s=ss;
      p=pp;
      return true;
    }
    ++s;
  }
  return false;
}


bool PattCmp2(const char* s, const char* p)
{
  if (!CompareText(s, p)) return false;
  while (*s!=0 && *p!=0)
  {
    SkipAsterisk(p);
    if (!FindText(s, p)) return false;
  }
  SkipAsterisk(p);
  return (*s==0 && *p==0);
}

Как видно - решение с помощью рекурсии - раза в три компактнее.

[Гром]

Alf, даешь статью по конечным автоматам !
Ты у нас по теории подвязался!!

[Alf]

ysv_, предложенный итеративный вариант по-прежнему отказывается сопоставлять непустую строку с шаблоном, оканчивающимся на '*'.

Что касается предложенного исправления рекурсивной функции, то теперь она выдает соответствие при сопоставлении пустой строки с шаблоном "*?", чт на мой взгляд неправильно.

Относительно сравнения рекурсивного и итеративного подходов - рекурсивное решение оказалось компактнее, как я и ожидал. Более неожиданным для меня оказался факт, что итеративный вариант труднее читать и понимать.

Фактически рекурсивная функция задает не последовательность действий, а набор признаков, по которым можно определить, соответствует строка шаблону или нет. Поэтому она показалась мне по духу ближе к стилю Prolog, чем C, хотя и написана на последнем.

[Alf]

Alf, даешь статью по конечным автоматам !
Ты у нас по теории подвязался!!

Гром, статья - не проблема. Только интересна ли народу будет подобная тема? Далеко не у каждого есть задачи, для которых был бы уместен автоматный подход.

К сожалению, время для статей могу находить лишь эпизодически, поэтому малоинтересная форумчанам статья неизбежно отодвинет по времени выход какой-то другой, возможно, более полезной.

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

Итак, возможные темы для следующих статей:

1. Теория формальных языков, конечные автоматы и т.п.
2. Рекурсия.
3. Базы данных (теория).
4. Базы данных (ADO.NET).
5. SADT, UML и т.п.
6. Нотации IDEF0, IDEF3, IDEF1X и их применение при разработке программ.

Возможно, кто-то добавит интересные для себя темы, я написал первое, что в голову пришло.

P.S. Кстати, а как быть при голосовании, если хочешь проголосовать сразу за несколько вариантов? Допускает это движок сайта, или каждый может выбрать только лишь один?

[npak]

Предчувствия меня не обманули.  

Автомат получился недетерминированным.  Недетерминизм появляется в том случае, когда за звёздочкой в шаблоне идёт символ.  Например '*a'.

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

Alf, я восхищен выбором примера.  с одной стороны, он достаточно содержателен и часто встречается в реальной жизни.  С другой стороны, пример достаточно прост в реализации, мало технических деталей.  Наглядно получилось.

[npak]

Мои 2 копейки -- рекурсивный и итеративный варианты на C.

Код:

const char asterisk = '*';
const char question = '?';

int
end_of_string(const char * str)
{
    return (*str == '\0');
}

int
skip_asterisks( const char ** p_pat )
{
    int result = 0;
    const char * pat = *p_pat;

    while ( *pat == asterisk ) pat ++;
    result = ( pat != *p_pat );
    *p_pat = pat;
    return result;
}

//
// RECURSIVE
//

int
match_pattern_recursive(const char * pat, const char * str)
{
    while ( !end_of_string( pat ) )
    {
        if ( *pat == asterisk )         // *
        {
            int result;

            // Glob all asterisks into one; jump to the next non-asterisk char
            // or end of the string
            skip_asterisks( &pat );

            // Optimization: empty pattern after asterisk matches any string
            if ( end_of_string( pat ) ) return 1;
            
            if ( end_of_string( str ) )
            {
                // Empty string matches only empty pattern
                return ( end_of_string( pat ) );
            }
            // Try to match the rest of pattern anywhere in string.
            while ( !( result = match_pattern_recursive( pat, str ) )
                    && !end_of_string( str ) )
            {
                // Move forward along the string (asterisk eats the string).
                str ++;
            }
            return result;
        }
        else if ( *pat == question )    // ?
        {
            if ( end_of_string( str ) )
            {
                return 0;
            }
            // Matches any char
            str ++; pat ++;
        }
        else                            // Any meaningful char
        {
            if ( end_of_string( str ) || *str != *pat )
            {
                return 0;
            }
            str ++; pat ++;
        }
    }
    // Pattern is empty here.  Note that the last char in the pattern (if any)
    // was not asterisk (see optimization above).  Therfore the only match is
    // an empty string.
    return end_of_string( str );
}

//
// ITERATIVE
//

int
match_pattern_header( const char ** p_pat, const char ** p_str )
{
    const char * pat = *p_pat;
    const char * str = *p_str;

    while ( !end_of_string( pat ) && !end_of_string( str ) )
    {
        // Came across an asterisk.  It means that fixed part matches.  Good
        // verdict.
        if ( *pat == asterisk )
        {
            *p_pat = pat;
            *p_str = str;
            return 1;
        }
        // Non-matching symbols found.  Bad verdict.
        if ( *pat != question && *pat != *str ) return 0;
        // Ok, proceed to the next symbol.
        pat ++; str ++;
    }

    // We can get here if and only if at least one string is over.
    // Good verdict if they are both empty or the next char in pattern is an
    // asterisk.
    if ( ( end_of_string( str ) && ( end_of_string( pat ) ) )
         || *pat == asterisk )
    {
        *p_pat = pat;
        *p_str = str;
        return 1;
    }
    return 0;
}

int
match_pattern_iterative( const char * pat, const char * str )
{
    int match = 1;
    int after_asterisk = 0;
    
    while ( match && !end_of_string( pat ) )
    {
        after_asterisk = skip_asterisks( &pat );
        
        if ( !after_asterisk )
        {
            match = match_pattern_header( &pat, &str );
        }
        else
        {
            // Try to match the next sub-pattern anywhere in the string.
            while ( !( match = match_pattern_header( &pat, &str ) )
                    && !end_of_string( str ) )
            {
                str ++;
            }
        }
    }
    // Here: match == 0 (means we failed to find a match to a certain
    //                   sub-pattern) 
    //       or pattern is over (means we found matching substrings for each
    //                           sub-pattern) 

    // The following could be condensed into
    // return match && ( !end_of_string( str ) || after_asterisk );
    if ( !match )
    {
        // found non-matching sub-pattern
        return 0;
    }
    
    if ( !end_of_string( str ) )
    {
        // Trailing 
        return after_asterisk;
    }
    return 1;
}

[ysv_]

Фактически рекурсивная функция задает не последовательность действий, а набор признаков, по которым можно определить, соответствует строка шаблону или нет. Поэтому она показалась мне по духу ближе к стилю Prolog, чем C, хотя и написана на последнем.

Согласен на все 100%.

Исправление итеративного варманта. Надеюсь последнее.
bool CompareText(const char*& s, const char*& p)
{
  while (*s!=0 && *p!=0 && *p!='*')
  {
    if (*s!=*p && *p!='?') return false;
    ++p;
    ++s;
  }
  if (*p=='*') return true;
  return (*s==0 && *p==0);
}

void SkipAsterisk(const char*&p)
{
  while (*p=='*') ++p;
}

bool FindText(const char*& s, const char*& p)
{
  const char *ss, *pp;
  while (*s!=0)
  {
    ss=s;
    pp=p;
    if (CompareText(ss, pp))
    {
      s=ss;
      p=pp;
      return true;
    }
    ++s;
  }
  return false;
}

bool PattCmp2(const char* s, const char* p)
{
  bool res=CompareText(s, p);
  if (*p!='*') return res;

  SkipAsterisk(p);
  if (*p==0) return true;
  while (*s!=0 && *p!=0)
  {
    if (!FindText(s, p)) return false;
    SkipAsterisk(p);
    if (*p==0) return true;
  }
  return (*s==0 && *p==0);
}

[npak]

3) Раскраска географической карты.
Дана плоская географическая карта. Нужно раскрасить ее таким образом, чтобы никакие два региона, имеющие общую границу, не были окрашены одним цветом (как обычно и красятся карты). Необходимо при этом использовать минимальное количество красок.
Есть теорема (доказанная относительно недавно), что ЛЮБУЮ карту можно покрасить всего четырьмя красками. Проверь ее в деле! (Заимствовано из книги Ч. Уэзерелла "Этюды для программистов").

Результат несколько великоват для постинга, поэтому я положил его по адресу http://www.ispras.ru/~npak/recursion/colormap.c

Программа пытается раскрасить произвольный граф не более чем заданным числом красок.  За минимальность раскраски не поручусь, но есть подозрения, что в большинстве случаев находится именно такая раскраска.  Контрпрмер придумывать лень.

Приведены рекурсивная реализация и итеративная.  Обе построены на одном алгоритме.

0.  Упорядочить все вершины графа, от 1 до n.  Изначально все вершины не раскрашены.

1.  Покрасить вершину 1 в первый цвет, переходим к следующей вершине.

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

[Dimyan]

Alf, лоханулся я немножко с твоими заданиями по рекурсии :oops:
Но вот на проверку то что сделал я:

Код:

/// <summary>
		/// Удаление записи
		/// </summary>
		private void Del_Node(int NodeID)
		{
			OleDbCommand cm = new OleDbCommand("Sel_NodeType", oleDbConnection1);
			cm.CommandType = CommandType.StoredProcedure;
			OleDbParameter prmNodeID = new OleDbParameter("NodeID", OleDbType.Integer, 4);
			cm.Parameters.Add(prmNodeID);
			oleDbConnection1.Open();
			cm.Parameters["NodeID"].Value = NodeID;
			try
			{
				int i =Convert.ToInt32( cm.ExecuteScalar());
				if(i!=0)//Если тема
				{
					DialogResult result;
					result = MessageBox.Show("Вы действительно хотите удалить тему со всеми подтемами и вопросами?",
						"Удаление темы", MessageBoxButtons.YesNo, MessageBoxIcon.Question,
						MessageBoxDefaultButton.Button2);
					if(result == DialogResult.Yes)
					{
						//Ищем вложенные итемы и удаляем их
						Delete_Child(NodeID);

					}
					
				}
				else//если вопрос
				{
					DialogResult result;
					result = MessageBox.Show("Вы действительно хотите удалить вопрос?",
						"Удаление вопроса", MessageBoxButtons.YesNo, MessageBoxIcon.Question,
						MessageBoxDefaultButton.Button2);
					if(result == DialogResult.Yes)
					{
						cm.Parameters.Clear(); 
						cm = new OleDbCommand("Del_NodeName", oleDbConnection1);
						cm.CommandType = CommandType.StoredProcedure;
						
						prmNodeID = new OleDbParameter("NodeID", OleDbType.Integer, 4);
						cm.Parameters.Add(prmNodeID);
						cm.Parameters["NodeID"].Value = NodeID;
						cm.ExecuteNonQuery();												
					}

					//treeContents.SelectedNode.Remove();
					//treeContents.Invalidate();                    
				}
				
			}
			finally
			{
				oleDbConnection1.Close();
			}

			treeContents.SelectedNode.Remove();
			treeContents.Invalidate();

		}
		//*********************************************************************************************//

		private void Delete_Child(int Parent)
		{
			OleDbCommand cm = new OleDbCommand("Sel_Child", oleDbConnection1);
			cm.CommandType = CommandType.StoredProcedure;
			OleDbParameter prmParentID = new OleDbParameter("ParentID", OleDbType.Integer, 4);
			cm.Parameters.Add(prmParentID);
		
			cm.Parameters["ParentID"].Value = Parent;

			
			while(Convert.ToBoolean(cm.ExecuteScalar()))//Есть еще дети
			{
				Delete_Child(Convert.ToInt32( cm.ExecuteScalar()));
			}

			cm.Parameters.Clear(); 
			cm = new OleDbCommand("Del_NodeName", oleDbConnection1);
			cm.CommandType = CommandType.StoredProcedure;
						
			prmParentID = new OleDbParameter("NodeID", OleDbType.Integer, 4);
			cm.Parameters.Add(prmParentID);
			cm.Parameters["NodeID"].Value = Parent;
			cm.ExecuteNonQuery();	
            
		}

Это функция уделения всех потомков узла из базы при удалении его из TreeView из уже известной тебе программы.
Помоему довольно длинно но работает, это все что я смог прибумать

[Finch]

Alf, область, где бы я не рекомендовал использовать рекурсию, это обработка больших динамических массивов. Программа работает крайне нестабильно. Вопрос об увелечении стека, это вопрос времени. Всегда можно найти длину массива, при которой программа будет вылетать. Столкнулся я с этим, когда мне нужно было сортировать сверхбольшие массивы (около миллиона элементов) с сверхбольшими числами (32 байта). Алгоритм который заложен в стандартную библиотеку борланда вылетал на массиве чуть больше тысячи. Пришлось брать битовую сортировку. После этого я понял поговорку. Рекурсией программируют только боги. Потому что только у богов есть компьютеры с неограниченными ресурсами. Статья мне понравилась. А то что было сказано выше, это так камень в огород.
Насчет раскраски стран, я не до конца понял. Возьми Россию. Со сколькими странами она граничит. Я думаю, что больше четырех.

[Alf]

Alf, область, где бы я не рекомендовал использовать рекурсию, это обработка больших динамических массивов.

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

Программа работает крайне нестабильно.

Я нестабильные программы и через итерацию писать умею. Обращайтесь, научу  
Что лишний раз подтверждает тезис об эквивалентности рекурсии и итерации...

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

См. предыдущий пункт.

Столкнулся я с этим, когда мне нужно было сортировать сверхбольшие массивы (около миллиона элементов) с сверхбольшими числами (32 байта). Алгоритм который заложен в стандартную библиотеку борланда вылетал на массиве чуть больше тысячи.

Странно, я об этой фирме был лучшего мнения... Хоть и по большей части заочно, ибо уже несколько лет не работаю с их компиляторами.

Пришлось брать битовую сортировку.

Думаю, что объем оперативной памяти, необходимый для размещения такой структуры (32 Мб), по нынешним меркам все же не настолько велик, чтобы считать такой массив "сверхбольшим" и прибегать к каким-то особо изощренным методам сортировки. Сейчас, наверное, уже и в принципе невозможно купить компьютер с объемом памяти менее 128 Мб, а в таком объеме подобный массив уместится. Разве что эта задача много лет назад решалась, когда еще персоналки поскромнее были.
Если бы объемы сортируемых данных заведомо превышали объем доступной оперативной памяти, тогда имело бы смысл прибегнуть к одному из методов внешней сортировки.
Тем не менее сортировка и поиск, пожалуй, являются одними из наиболее (если не самыми) теоретически и практически проработанными вопросами информатики, взять хотя бы сооответствующий том Кнута размером и весом с хороший кирпич. Так что тут вряд ли имеет смысл изобретать велосипед. Даже если это чрезвычайно элегантный рекурсивный велосипед.

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

У богов и задачи посложнее, чем сортировка массивов, пусть даже супермассивов  

Статья мне понравилась.

Спасибо. Обещаю, что скоро будут еще в развитие этой темы.

...Насчет раскраски стран, я не до конца понял. Возьми Россию. Со сколькими странами она граничит. Я думаю, что больше четырех.

Честно говоря, немного не понял вопроса (или утверждения).
Теорема о четырех красках вовсе не утверждает, что на свете не существует государств с более чем четырьмя соседями  
Она утверждает всего лишь , что любую плоскую географическую карту можно раскрасить таким образом, что никакие две области, имеющие общую границу, не будут иметь один и тот же цвет, и при этом обойтись четырьмя красками (если карта достаточно простая, то возможно и меньшее количество, 4 - это верхний предел). Это доказано теоретически и неоднократно проверено на практике (я и сам когда-то давал эту задачу в качестве упражнения студентам, изучающим Pascal, и большинство справлялось успешно).
Кстати, npak решил эту задачу и выложил ее решение (см. выше). Честно говоря, я его еще не смотрел (сейчас у меня цейтнот, и пришлось вообще забросить эту ветку форума, хотя мне весьма нравится завязавшаяся здесь дискуссия), но обязательно вернусь к ней в ближайшем времени.

[npak]

Finch, да, рекурсия -- не универсальный метод.

У неё есть ограничения.  Наиболее существенное -- возможность переполнения стека.  Это может быть вызвано слишком медленным понижением сложности задачи, при относительно большой начальной сложности.

Например, для быстрой сортировки на каждом шаге рекурсии сложность задачи понижается примерно в два раза (массив, который нужно отсортировать, делится примерно пополам).  В среднем глубина рекурсии при сортировке массива длиной n нужна примерно lg2(n) глубина рекурсии.  Но возможны такие начальные значения в массиве, что на каждом шаге сложность понижается на 1 (например, массив отсортирован в обратном порядке).  Для сортировки такого массива длиной n потребуется глубина рекурсии порядка n.

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

Теперь про раскраску карты.  Надо раскрасить карту так, чтобы соседние страны были раскрашены разными цветами.

[Finch]

Alf писал(а):

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

Я не думаю, что такой изошренный. Алгоритм хорошо описывается в третьем томе Кнута. После алгоритма, который применили в Борланде. Эти два алгоритма считаются одними из самых быстрых. Когда я написал сортировку по битовому алгоритму с применением рекурсии. Он также стабильно вылетал на массиве, чуть больше 1000. И вопрос, как часто ты сортируеш массивы даных с длиной больше миллиона? Это  был мой первый опыт. И после этого я больше этим не занимался. Зато приобрел опыт и дополнительную функцию в мою коллекцию.

npak В том то и дело, что массив был равно распределен.

[npak]

Finch, что значит "вылетал"?  В чём это проявлялось?

У меня нет сейчас под рукой Кнута, а припомнить битовую сортировку не могу  :oops: .  Напомни, пожалуйста, в чём особенность алгоритма?

Какой продукт Борланда ты использовал в своей работе, на какой операционной системе?

[Finch]

npak,  было переполнение стека. Хотя я этого не ожидал. и не предпологал.
Алгоритм по своей идее очень простой. Надо начинать со старших битов.
1. в масиве все числа которые имеют соответствующий бит равный 1 сносятся наверх, которые имеют бит равный 0 сносятся вниз.
2. Получается массив разбит на две части: Первая часть где все числа имеют соответствующий бит 1, Вторая часть где все числа имеют соответствующий бит 0.
3. Выполняется операция 1 для каждой части с понижением значимости бита, до тех пор пока не дойдем до самого младшего бита.
Естественно делается ловушка, если в массиве всего один член.

Количество просмотров всего массива зависит только от количества бит в числе. Недостаток этого алгоритма, только в том, что его надо настраивать на данные (по моему мнению).
Реализовал его я тоже просто. Есть два бегунка. Один идет сверху второй снизу. Когда верхний бегунок находит число у которого соответсвующий бит равен 0 он останавливается. Нижний соответственно для бита равного 1. Когда два бегунка остановились программа производит обмен между ячейками. И запускает бегунки. До тех пор пока бегунки не встретятся.
Все. что описано выше это для сортировки младшие внизу, старщие наверху.
Когда я это писал, то работал в Delphi 4.5 Win98. Сейчас у меня стоят Borland C++ 5.0 Builder, Delphi 4.5,  WinXP. На новые версии не хочу переходить. Мне этого вполне достаточно (привычка это очень плохое дело ).

[npak]

Finch,

 Хороший рекурсивный алгоритм с гарантированной глубиной рекурсии (256 (8*32) в твоём случае).  Можно предложить Alf'у взять в качестве примера для статьи о рекурсии.

[NetRaider]

Тем не менее сортировка и поиск, пожалуй, являются одними из наиболее (если не самыми) теоретически и практически проработанными вопросами информатики, взять хотя бы сооответствующий том Кнута размером и весом с хороший кирпич. Так что тут вряд ли имеет смысл изобретать велосипед.

Категорически не соглашусь: для многих вариантов сортировок разрыв между верхней и нижней границ оценок производительности очень высок, тот же quckSort может давать до O(n^2) сравнений. Можно вспомнить еще различные комбинации сетей сортировок, например оптимальными для параллельной работы, для которых не существует нормального алгоритма построения. В том же 3-ем томе Кнута 50-ти бальных задач(которые являются научными проблемами), в главах о сортировке больше всего. До сих пор неизвестна зависимость минимального кол-ва сравнений от кол-ва элементов. Да и видов сортировки существует горааздо больше, чем думают.  Вообще проблема сложности алгоритмов(и не только сортировки) в информатике стоит очень остро. Так что здесь есть над чем думать...

[Alf]

Категорически не соглашусь: для многих вариантов сортировок разрыв между верхней и нижней границ оценок производительности очень высок, тот же quckSort может давать до O(n^2) сравнений. Можно вспомнить еще различные комбинации сетей сортировок, например оптимальными для параллельной работы, для которых не существует нормального алгоритма построения. В том же 3-ем томе Кнута 50-ти бальных задач(которые являются научными проблемами), в главах о сортировке больше всего.

Давайте все-таки попробуем отделить проблемы, связанные с действительной сложностью задачи, от проблем некорректной реализации. Одно дело - задача, для которой нет алгоритма в принципе (кстати, а как ее в таком случае решать программно?). Совсем другое дело - неподходящая реализация работающего алгоритма, переполняющая стек. Я бы не спешил относить это к научным проблемам.
Тем более что npak предлагает рекурсивный вариант с гарантированно ограниченной глубиной, лишний раз подтверждая, что все гениальное просто. Хотя это нужно уж очень любить рекурсию, чтобы даже массивы сортировать с ее применением. Лично я бы все же воздержался от рекурсии в пользу итерации, да простят мне мои низменные пристрастия.

До сих пор неизвестна зависимость минимального кол-ва сравнений от кол-ва элементов.

Таки неизвестна ни для какого алгоритма? Или речь идет все же об отдельных особо сложных случаях?

Да и видов сортировки существует горааздо больше, чем думают.

В этом и беда. Те виды, над которыми не думают, и вызывают проблемы.

Так что здесь есть над чем думать...

Вот с этим не могу не согласиться.

[NetRaider]

Давайте все-таки попробуем отделить проблемы, связанные с действительной сложностью задачи, от проблем некорректной реализации. Одно дело - задача, для которой нет алгоритма в принципе (кстати, а как ее в таком случае решать программно?). Совсем другое дело - неподходящая реализация работающего алгоритма, переполняющая стек. Я бы не спешил относить это к научным проблемам.
Тем более что npak предлагает рекурсивный вариант с гарантированно ограниченной глубиной, лишний раз подтверждая, что все гениальное просто. Хотя это нужно уж очень любить рекурсию, чтобы даже массивы сортировать с ее применением. Лично я бы все же воздержался от рекурсии в пользу итерации, да простят мне мои низменные пристрастия.

С этим я согласен, просто меня задела фраза о том что сортировка и поиск являются проработанными вопросами. Задел за живое, так сказать...  

До сих пор неизвестна зависимость минимального кол-ва сравнений от кол-ва элементов.

Таки неизвестна ни для какого алгоритма? Или речь идет все же об отдельных особо сложных случаях?
[/quote]
Ты не понял...
Минимальное кол-во сравнений для n элементов неизвестно(без привязки к конкретному алгоритму). Например для сортировки 3 элементов нужно минимум 3 сравнения, для 4 - 5, 5-7, для n больше 8 кол-во сравнений незвестно... А зная эту зависимость можно намного точнее определить производительность различных алгоритмов.

[npak]

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

Алгоритм битовой сортировки предлагает Кнут, а не я  Я лишь озвучил замечание о том, что в этом алгоритме рекурсивная реализация имеет ограниченную глубину рекурсии, вне зависимости от размера массива.  К сожалению, данный алгоритм применим лишь для лексикографического упорядочения битовых массивов ограниченной длины.  В общем случае сортировки он не применим.

Сортировка и поиск -- очень тонкие задачи.  Выбор алгоритма и его реализация сильно зависят от задачи.  Finch предложил пример, на котором стандартные решения не проходят.

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

Интересно, что вы используете для сортировки массивов?

[Alf]

Ты не понял...
Минимальное кол-во сравнений для n элементов неизвестно(без привязки к конкретному алгоритму). Например для сортировки 3 элементов нужно минимум 3 сравнения, для 4 - 5, 5-7, для n больше 8 кол-во сравнений незвестно... А зная эту зависимость можно намного точнее определить производительность различных алгоритмов.

Кнута под рукой нет, попался Вирт. Открываю главу "Сортировка массивов", читаю:

Анализ сортировки простыми включениями. Общее число сравнений C и пересылок M:
Cmin=n-1
Cavg=1/4(n^2+n-2)
Cmax=1/2(n^2+n)-1
... и т.д.

Анализ сортировки простым выбором. Число сравнений ключей C не зависит от начального порядка ключей.
C=1/2(n^2-n)

Или я неверно понял постановку вопроса?

P.S. В случае массива из 3-х элементов вовсе не обязательно нужны 3 сравнения. Если известно, что A>B и B>C, столь ли необходимо сравнивать A и C? Я бы не стал говорить, что 3 - это минимум.

[Alf]

Алгоритм битовой сортировки предлагает Кнут, а не я

Хорошо, пускай будет так: Кнут предлагает, а npak продвигает в массы  

Интересно, что вы используете для сортировки массивов?

Мне даже неловко признаться, что я оказался как-то в стороне от этой проблемы, вроде как отщепенцем себя чувствую  

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

Но мой выбор в сортировке явно не показателен, ибо прибегаю к ней от случая к случаю и для небольших объемов (а большие мне и взять негде, по сути дела).

[NetRaider]

Кнута под рукой нет, попался Вирт. Открываю главу "Сортировка массивов", читаю:

Анализ сортировки простыми включениями. Общее число сравнений C и пересылок M:
Cmin=n-1
Cavg=1/4(n^2+n-2)
Cmax=1/2(n^2+n)-1
... и т.д.

Анализ сортировки простым выбором. Число сравнений ключей C не зависит от начального порядка ключей.
C=1/2(n^2-n)

Это для конкретного алгоритма...

P.S. В случае массива из 3-х элементов вовсе не обязательно нужны 3 сравнения. Если известно, что A>B и B>C, столь ли необходимо сравнивать A и C? Я бы не стал говорить, что 3 - это минимум.

А если в результате сравнения окажется что B<C ?  3 - это гарантируемый минумум сравнений. Естественно что может потребоваться и меньше сравнений. Но минимальный максимум - 3.