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

И вообще, более общий вопрос.
Есть, положим массив из int. Сортировать его или нет - мне побоку, а вот все одинаковые int в нем надо удалить. Как это сделать?

Достаточно будет сказать только название сортировки. А дальше я уж сам разберусь. Благо, сайтов по алгортимам хватает :)

Да, и ыще :) Было бы классно, если бы кто-то бросил линк на С-операции со списками. Я надыбал кой-чего, но может кто-то давно уже что-то такое знает. А?

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

Сортировка - это не удаление элементов, поэтому вопрос поставлен некорректно. Для удаления одинаковых элементов лучше сначала массив отсортировать, а дальше дело техники. А какую сортировку использовать, в принципе, неважно, хотя из соображения эффективности лучше взять быструю сортировку, бинарную (корпоративную) сортировку или сортировку методом Шелла.
Есть и другие способы, например, использование битового массива для хранения признака, присутствует ли элемент в массиве (1 или 2 бита на каждый элемент - надо это обдумать хорошенько). При этом требуется всего один-два прохода, но много памяти. Например, если диапазон чисел от 0 до 2^20, потребуется 2^17 или 2^18 байт.
Если массив не очень большой и/или время выполнения не сильно ограничено, я думаю, первый способ будет наиболее эффективным.
Кстати, эта тема обсуждалась в книге "Жемчужины программирования" издательства "Питер", серия "Библиотека программиста", автора не помню. Может, там ещё какой алгоритм есть.

Artem
Сортировка - это не удаление элементов, поэтому вопрос поставлен некорректно

Вообще то нет. Вопрос верный. Сортировка -- это операция упорядочевания.

Удаление элементов -- это так же операция упорядочевания.

P.S
на выходных закончу свой алгоритм.. Так что жди :))

сортируешь массив arr[0..size-1] по возрастанию или убыванию, потом делаешь цикл:

  i:=0;
  while i<(size-1) do
    if arr[i]=arr[i+1] then delete(i) else inc(i);

з.ы. писАл по ходу, должно работать...

Max
Это уже было :)) В теме по перл :)

Edmond
не знаю, не читал ;-)
я вот когда начинал, лет 15 назад, придумал алгоритм сортировки, а потом узнал, что он называется "пузырьковым" :)))
вот так вот бывает...

Max

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

Max
вот так вот бывает...

Ну не только у тебя, я например ООП разработал.. за пол года о его прочтении :)))

volodya
Это отнюдь не самый быстрый алгоритм
Согласен, но сомневаюсь, что можно сделать быстрее.
В связке qucksort + цикл все работает очень быстро.
Узкое место тут - delete(i), если при этом делать релок памяти то действительно будет медленно, если сначала отмаркировать записи подлежащие удалению, будет быстро.
А если заточить под SSE2, то вместо if arr=arr[i+1], можно сравнивать arr[i] сразу с 4-мя последующими элементами.

[i]Буду ждать Димонова решения...
Интересно было бы посмотреть...

[З.Ы. quicksort всмысле...]

Max

Код примера будет компилироваться под 14 операционных систем и приблизительно еще две архитектуры процов, отличных от Intel - к примеру, sparc.
Ясно, что никакие SSE2 мне тут не катят :(

Я еще просил инфу по связанным спискам. Т.е. спискам вида

val|ptr_to_next_node->val|ptr_to_next_node->val|0;

Поскольку никто ни чем для меня не разродился, я тут налабал маленько. Не скажу, что функции САМЫЕ эффективные, поэтому, если кто хочет пнуть - силь ву пле :)

typedef struct valnodeEx {
	int intvalue;	   /* first int to play with*/
	int intvalue2;        /* second one */
	struct valnodeEx *next;    /* next in linked list */
} ValNodeEx, *ValNodePtrEx;

/********************
 * my own implementation of some functions to play with ValNodeEx
 ********************
 */

ValNodePtrEx ValNodeAddIntsEx(ValNodePtrEx vnp, int val1, int val2)
{
	ValNodePtrEx newnode = NULL;

	if(!vnp->next && !vnp->intvalue && !vnp->intvalue2)
	{
		vnp->intvalue = val1;
		vnp->intvalue2 = val2;
	}
	else
	{
		if((newnode = (ValNodePtrEx) malloc(sizeof(ValNodeEx))))
		{
			while(vnp->next)
				vnp = vnp->next;

			newnode->intvalue	= val1;
			newnode->intvalue2	= val2;
			newnode->next		= 0;
			vnp->next			= newnode;
			return newnode;
		}
	}
	return newnode;
}

ValNodePtrEx ValNodeCreateHeadEx(void)
{
	ValNodePtrEx head = NULL;
	
	if((head = (ValNodePtrEx) malloc(sizeof(ValNodeEx))))
	{
		memset (head,0,sizeof(ValNodeEx));
		return head;
	}

	return head;
}

void ValNodeFreeAllEx(ValNodePtrEx head)
{
	ValNodePtrEx next = NULL;
	while(head)
	{
		next = head->next;
		free(head);
		head = next;
	}
}

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

По поводу односвязанных списков и удаления избыточности.
Единственное, что пришло мне в голову. Точнее, почти единственное.

Что мы можем сделать.
Вариант 1:

for(начало списка; последний элемент?; взять элемент)
{
   взять этот элемент и сравнить его со следующим;
   if( элементы идентичны согласно заданному критерию)
   {
     убрать элемент к чертям и перестроить список;
   }
   и так до конца массива!;
   и с каждым элементом!;
}

Не скажу, что я в восторге от этой идеи. Другая, альтернативная. Список применяется тогда, когда ты не знаешь, сколько данных у тебя будет. Так вот - я не знаю :) Но работать с односвязанным списком очень неудобно, т.к. я могу двигаться только от начала к концу. Двусвязанный список уже лучше, но требует больших расходов памяти, что тоже не есть хорошо.
Я вот и думаю, может прочесать односвязанный список, создать массив из указателей на next node (и только из них - для моего случая - в три раза меньше памяти), и смотреть уже по указателям - тогда можно применить частный случай быстрой сортировки - т.е. разбить напополам и смотреть.

Я вот и думаю, может прочесать односвязанный список, создать массив из указателей на next node

ПРАВИЛЬНО.

Делаешь массив, а потом просто берёшь любой алгоритм, например радиксную сортировку, или быструю, и ПЕРЕМЕЩАЕШЬ УКАЗАТЕЛИ В МАССИВЕ.

А потом, просто делаешь рендеринг указателей в списках, с теми что в массиве.

Edmond

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

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

Да нет же!!!!
Просто доступ к элементу осуществляется через адрес.
Ну да, это медленнее, а что ж ты хотел?

Впрочем, если у тебя элемент -- только один, то конечно можно было сразу их только и помещать,..