Удаление элементов -- это так же операция упорядочевания.
Не могу с этим согласиться, но это, в принципе, неважно.
По поводу удаления одинаковых элементов из отсортированного массива. Удалять каждый раз по одному элементу накладно, если массив большой, а повторяющихся элементов много. Есть другой способ, попытаюсь объяснить его на примере. Пусть есть массив: 0 1 1 2 3 4 4 4 5 6 6. После нахождения единиц сдвигаем так: 0 2 3 ? ? 4 4 4 5 6 6. Символ "?" означает "пустую" ячейку. После обнаружения четвёрок делаем следующее: 0 2 3 5 ? ? ? ? ? 6 6. И, дойдя до конца - 0 2 3 5 6. Таким образом, в итоге мы перемещаем байт не более, чем размер массива.

А если при формировании массива (или списка) проверять есть такой элемент в нем или нет? и добавлять новые только по мере надобности?
(В математике это называвется множества)

2 volodya:
Народ, подскажите мне, тупому, какая такая сортировка есть, чтобы она мне в массиве (или в списке при связанном хранении, неважно) грохнула все одинаковые int.

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

А на более общий вопрос ответ гораздо более сложен. Он зависит от характера входных данных: диапазона входных значений, количества различных входных значений, общего размера входных данных.

В случае, когда диапазон входных значений невелик (например, при сортировке байтов или 16-битных слов), эффективнее всего radix sort (в данном случае, это то, о чём говорил Artem в первой реплике).

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

Для остальных случаев разумно применить хэш-таблицу.

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

Да, насчёт указателей: если размер сортируемых элементов вызывает серьёзные накладные разсходы на пересылку, следует сортировать массив указателей на них. Когда размер элемента равен размеру указателя, это, разумеется, смысла не имеет.

Artem

Хм... Оригинально! Но геморно реализовать!

DaemoniacaL

Стоит подумать тщательнее. Поразмыслю над этим в понедельник!

bsl_zcs

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

struct node
{
   int int1;
   int int2;
   struct next *node;

}

в синтаксисе ошибки, ну да хрен с ними. Вывод об идентичности элементов делается просто - если int1/int2 одного узла равны int1/int2 другого. Если я встречаю такой элемент - я должен его удалить и перелинковать список (т.е. переписать поинтер предыдущего узла).

В этом случае, я полагаю, нужно использовать твою поразрядную (т.е. radix) сортировку.

http://algolist.manual.ru/sort/radix_sort.php
там как раз пример со списками - код там же. Только теперь надо вставить в тот код пример с удалением избыточности из такого списка. А для этого надо детально разобраться с этим делом! Было бы здорово если бы ты мне на пальцах расписал, куда там и что вставлять. А вообще, на RSDN хорошая статья по этому делу есть - я ее прочту.


Вообще, ребята, спасибо. Мне очень приятно, что на наш форум забредают люди с хорошо выраженными способностями к алгоритмизации, т.к. знания сами по себе достаточным условием для звания "программист" не являются. Это тривиально и зависит от количества прочитанных книжек. Вот способность к алгоритмизации - вещь серьезная. Будучи биохимиком :), у меня такие вещи вызывают уважение.

Я чего-то с головой дружить перестал. Какая ж тут на хрен сортировка, если в каждом узле у меня два элемента!! На фига тут сортировать и как сортировать. Нет! Лучше не допускать такие элементы в список и все.
Что до radix сортировки, то из спортивного интереса, смотрите:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct slist_
{ 
  long val;
  struct slist_ *next; 
} slist;

// функция сортировки возвращает указатель на начало отсортированного списка 
slist *radix_list(slist *l, int t) {
  //  t - разрядность (максимальная длина числа) 
  int i, j, d, m=1;
  slist *temp, *out, *head[10], *tail[10];
  out=l;

  for (j=1; j<=t; j++) { 
    for (i=0; i<=9; i++)
      head[i] = (tail[i]=NULL);

    /*первый проход - заполняем head*/
    while ( l != NULL ){
      /*получить первую справа цифру текущего узла*/
      d = ((int)(l->val/m))%(int)10;     
      temp = tail[d];
      if ( head[d]==NULL ) head[d] = l;
      else temp->next = l;
      temp = tail[d] = l;
      l = l->next;
      temp->next = NULL;
    }
    for (i=0; i<=9; i++)
      if ( head[i] != NULL ) break;
    l = head[i];
    temp = tail[i];
    /*второй проход - сборка списка*/
    for (d=i+1; d<=9; d++) {
      if ( head[d] != NULL) { 
        temp->next = head[d];
        temp = tail[d];
      }
    }
    m*=10;
  }
  return (out);
}

void AppendNode(slist **headRef, int num) 
{
	slist *current = *headRef;
	slist *newNode;
	
	newNode = malloc(sizeof(slist));
	newNode->val = num;
	newNode->next = NULL;
	if (!current) 
	{
		*headRef = newNode;
	}
	else 
	{
		while (current->next) 
		{
			current = current->next;
		}
		current->next = newNode;
	}
}


void main(void)
{
	slist *l = NULL;
	int i = 0;
	
	srand(time(NULL));
	
	while(i<20) 
	{
		AppendNode(&l, (int)rand()%1000);
		i++;
	}
	radix_list(l, 4);
}

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

Хм... Оригинально! Но геморно реализовать!
Не так уж и геморно. Если кому интересно - вот исходничек:

//на входе уже отсортированный массив
void DeleteSame(T* m,DWORD &Size)
{
 int DiffEnd=0,SameEnd=0,a;
 for (a=0;a<Size-1;a++)
  if (m[a]==m[a+1]) {
   if (DiffEnd!=SameEnd)
    memmove(m+DiffEnd,m+SameEnd,(a-SameEnd)*sizeof(*m));
   DiffEnd+=a-SameEnd;
   for (a++;a<Size-1 && m[a]==m[a+1];a++);
   SameEnd=a+1;
  }
 if (DiffEnd!=SameEnd) {
  memmove(m+DiffEnd,m+SameEnd,(Size-SameEnd)*sizeof(*m));
  Size-=SameEnd-DiffEnd;
 }
}

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

Сравнивать можно так:

int Compare(node* l,node* r)
{
 return l->int1 != r->int1 ? l->int1 - r->int1 : l->int2 -r->int2;
}

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

Вариант с сортировкой вставками. Никаких списков, никаких предварительных сортировок, никаких удалений, никакого дополнительного расхода памяти.

Имеешь большой массив, в котором лежат исходные данные. Повторяющиеся и неотсортированные. Проходишь его по порядку с начала и до конца. В том же массиве в начале начинаешь складывать уже отсортированный массив уникальных элементов. Их по смыслу будет меньше или равно чем уже проверенных исходных, поэтому места хватит. На каждый элемент ищешь его бинарным поиском в отсортированной части. Если нашел - это дупы, выкидываешь его и берёшь следующий. А если не нашел - то с того места, где остановился бинарный поиск, сдвигаешь всё отсортированное на один элемент вперёд, и на освободившееся место записываешь текущий элемент.
И так до конца.

Фича в том, что сортировка, совмещённая с проверкой, позволит сортировать только уникальные элементы. Посему - чем больше избыточность, тем эффективнее это будет работать. Поиск по отсортированному бинарный, следовательно, быстрый.

Вставку можно слегка улучшить путём размещения отсортированного массива не в начале проверенной области, а в её середине, и сдвига элементов при вставке либо вниз либо вверх, в зависимости от того, где меньше. Как упрётся в границу - сдвигать целиком на середину. Успокою: скорее всего, это не понадобится. :)

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

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

bsl_zcs


Имеешь большой массив, в котором лежат исходные данные. Повторяющиеся и неотсортированные. Проходишь его по порядку с начала и до конца. В том же массиве в начале начинаешь складывать уже отсортированный массив уникальных элементов. Их по смыслу будет меньше или равно чем уже проверенных исходных, поэтому места хватит. На каждый элемент ищешь его бинарным поиском в отсортированной части. Если нашел - это дупы, выкидываешь его и берёшь следующий. А если не нашел - то с того места, где остановился бинарный поиск, сдвигаешь всё отсортированное на один элемент вперёд, и на освободившееся место записываешь текущий элемент.
И так до конца.


Смысл ясен. Оки-доки.

Artem

Спасибо, классно. Я разобрался :)

Только одно но, ребята. Оба ваши решения для МАССИВОВ!!!
Вот, к примеру, твоя, bsl_zcs, сортировка вставками должна двигаться по массиву НАЗАД! А по односвязанному списку ХРЕН ТАМ назад подвигаешься. А мне нужен именно односвязанный список, т.к. чем приводить такой список к массиву, сортировать массив, а потом возвращать все в круги своя - лучше последовательный поиск!
А вообще - спасибо еще раз!

А теперь объясни зачем тебе список?

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

bsl_zcs

Объясняю. Есть некая зубодробительная структура, в которой я не знаю сколько элементов лежит (т.е. структур поменьше). Структурки эти связаны одна с другой через односвязный список (примерно такой же). Т.е. я не могу заводить массив (вернее могу, но это тупо, т.к. придется заводить его достаточно большого размера заранее, чтобы не возиться с realloc). Кроме того, придется заводить не просто массив, а массив из структур. Ничего страшного, в общем-то, но алгоритм сортировки усложнится :)
Слушай, что мне, никто ничего по списку сказать не может?

Вот еще два алгоритма по спискам:

//Функция возвращает указатель на отсортированный список.
..
typedef struct OBJ1{
  int K;
  struct OBJ1*NEXT;
}OBJECT1;
..
OBJECT1*Sort(OBJECT1*head){//Function starts here
  OBJECT1 *newh,*max,*prev,*pmax,*cur;
  newh=NULL;
  while(head){
    max=prev=head;
    cur=head->NEXT;
    while(cur){
      if(cur->K>max->K){max=cur;pmax=prev;}
      prev=cur;cur=cur->NEXT;
    }
    if(max==head)head=head->NEXT;
    else pmax->NEXT=max->NEXT;
    max->NEXT=newh;newh=max;
  }
  return newh;
}------=_20030826132558_22220
Content-Type: text/plain; name="7.txt"
Content-Disposition: attachment; filename="7.txt"

Пример 7.
//Функция возвращает указатель на отсортированный список.
..
typedef struct OBJ1{
  int K;
  struct OBJ1*NEXT;
}OBJECT1;
..
OBJECT1*Sort(OBJECT1*head){//Function starts here
  OBJECT1 *newh,*cur,*sel;
  newh=NULL;
  while(head){
    sel=head;
    head=head->NEXT;
    if(newh==NULL||sel->K<newh->K){
      sel->NEXT=newh;newh=sel;
    }else{
      cur=newh;
      while(cur->NEXT&&cur->NEXT->K<sel->K)cur=cur->NEXT;
      sel->NEXT=cur->NEXT;
      cur->NEXT=sel;
    }
  }
  return newh;
}

Тебе связь в список вообще для чего нужна? Сортировка, то есть последовательность, же тебе некритична... Если только для того, чтобы уникальность обеспечить, то откажись от неё и всё...

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

bsl_zcs

Предложи другую структуру.

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

Во-во! Самое то! Произвольной вставки и удаления. Нашел я такой узел - перелинковал список и все! А в массиве? Методом Артема и сортировать его сначала?

void AppendNode(slist **headRef, int num, int num2) 
{
	slist *current = *headRef;
	slist *newNode;
	
	if (!current) 
	{
		newNode = malloc(sizeof(slist));
		newNode->val = num;
		newNode->val2 = num2;
		newNode->next = NULL;
		*headRef = newNode;
	}
	else 
	{
		while (current->next) 
		{
			if(current->val == num && current->val2 == num2)
			{
				return;  //вот эта самая шутка и не даст нам получить избыточность
			}
			current = current->next;
		}
		newNode = malloc(sizeof(slist));
		newNode->val = num;
		newNode->val2 = num2;
		newNode->next = NULL;
		current->next = newNode;
	}
}

Решил. Все.
Если кому интерестно больше - http://algolist.manual.ru/forum/viewtopic.php?p=3179#3179

volodya
Т.е. я не могу заводить массив (вернее могу, но это тупо, т.к. придется заводить его достаточно большого размера заранее, чтобы не возиться с realloc).
А что там с ним возиться? Не так уж и сложно. А выделять malloc'ом память под каждый элемент разорительно (там же ещё несколько байт служебной информации) и медленно.

Кроме того, придется заводить не просто массив, а массив из структур. Ничего страшного, в общем-то, но алгоритм сортировки усложнится :)
Нисколько не усложнится, изменится только функция сравнения.

Во-во! Самое то! Произвольной вставки и удаления. Нашел я такой узел - перелинковал список и все! А в массиве? Методом Артема и сортировать его сначала?
Если главное - простота реализации и удобство использования, можно постоянно поддерживать массив отсортированным и без повторяющихся элементов: при добавлении нового элемента бинарным поиском находим нужное местоположение (или обнаруживаем, что добавляемый элемент уже есть) и вставляем новый элемент туда.

А может, задача может быть решена с использованием контейнеров STL?