В принципе, алгоритм можно переделать таким образом, что ar1 - array of boolean. Тогда на втором этапе надо делать не Inc, а присвоение True.

При этом - метод теряет достоинство №3 (см. предыдущий топик) но уходит ограничение 2. Кроме того, более мягкие требования к занимаемой памяти масивом ar1.

P.S. Эту идую можно развить и дальше - использовать одно битные значения, тогда каждый элемент массива ar1 будет содержать 8 флагов наличия соответствующих значений. Но в этом случае в 2-3 раза уменьшиться общее быстродействие метода.

Цитата(oleg1973 @ 7.2.2004, 13:56)

December ну я имел ввиду из массива выбрать уникальные числа тоесть если к примеру в массиве А число 2 встречается 100 раз то в массив В мы засунем всего одну 2 а не 100 ну не знаю я как точнее обяснить

Чё надо сделать - я понял, ты перечитай как ты объясняешь свой метод - это даже не по-русски

Цитата

Сортировала по возрастанию (не важно как)

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

Цитата

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

Цитата

С прошлым моим замечанием можно хорошо бороться, если оптимизировать выбор начального элемента, т.е. значение числа v

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

вот, как это может выглядеть на C++:

Код

#include <stdlib.h> #include <stdio.h> #include <time.h> #define SIZE 65536 //получает два отсортированных массива размером size в результате выдает отсортированный массив длины 2*size void Sort(int *source1,int *source2,int *result,int size) {  int c1,c2,c;  int *buffer=new int[2*size];  c1=0;  c2=0;  c=0;  while(true)  {    if(c1<size)    {      if(c2<size)//оба массива еще не закончились, сравниваем их элементы      {        if(source1[c1]<source2[c2])          result[c++]=source1[c1++];        else          result[c++]=source2[c2++];      }      else//второй массив закончился, первый - нет, дописываем его (первый) в result        result[c++]=source1[c1++];    }    else    {      if(c2<size)//первый массив закончился, второй - нет, дописываем его (второй) в result        result[c++]=source2[c2++];      else//у нас все закончилось, уходим...        break;    };  }; }; void main() {  int array1[SIZE];  int array2[SIZE];//два массива, между ними будем гонять информацию, пока она не станет отсортированной  int *source,*result,*bak;  int c;  int size;  source=array1;  result=array2;  srand( (unsigned)time( NULL ) );  for(c=0;c<SIZE;c++)  {    source[c]=rand();    //printf("%d\n",source[c]);  };  printf("------------\n");  size=1;//показывает размер маленьких массивов, на которые делим большой  while(size<SIZE)  {    for(c=0;c<SIZE;c+=2*size)      Sort(source+c,source+c+size,result+c,size);//слияние двух маленьких массивов    size*=2;    bak=result;//меняем местами источник и приемник    result=source;    source=bak;  };  printf("%d\n",source[0]);  for(c=1;c<SIZE;c++)  {    if(source[c]!=source[c-1])//чтобы пропустить одинаковые элементы      printf("%d\n",source[c]);  }; };

тестировал я его на SIZE 16, вроде бы правильно работает
в таком виде он работает только, если SIZE - степень 2, его, конечно, можно как-нибудь приспособить к другим SIZE, но это уже не очень интересная задача, можно просто дополнять массив до нужного количества одним из его элементов: на результат это не повлияет, а время сильно не изменится...

это был я...