Сортировать LinkedList :)

wvxvw · 27.12.2009, 02:58

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

Код:

typedef Cell {
Cell next;
Dynamic value;
}

И есть цепочка из этих объектов типа:
Cell1.next = Cell2;
Cell2.next = Cell3;
и так до победного конца: CellN.next = null.

Вопрос: как это дело грамотно отсортировать (с использованием колбека типа f(a : Dynamic, b : Dynamic) : Boolean )?
Смотрел разнообразные варианты на Java типа Merged sort - не подходит т.как все реализации предполагают рекурсию. Смотрел ту же реализацию на C++ - не понял, как работает

Попробовал глупо скопировать - но не повезло, чего-то где-то я с ссылками / значениями запутался...
AS3 варианта не нашел...
Большинство вариантов сортировки работают с массивами и их тяжело переделать под LinkedList без громадной потери производительности (т.как нужно все время по листу бегать чтобы найти нужный индекс)...
Так что ShellSort (хотя он вроде в AS3 самый быстрый получается - для массивов) не подходит...
Внятного объяснения InsertionSort не нашел... в википедии статься на с какими-то уж сильно псевдо-примерами - ничего не понятно

iflamberg · 27.12.2009, 03:26

Можно подумать у LinkedList русского названия нет. Связанный список - он и в Африке связанный список.
А покажи реализацию на cpp, может мы ее совместным творчеством? И рекурсию, при желании, тоже можно нормализовать в цикл.
Думаешь, получится что-то более быстрое, цем обычные массивы в результате?

Gaen · 27.12.2009, 03:33

Вот тут хорошо визуализированы и объяснены алгоритмы сортировки http://www.sorting-algorithms.com/

wvxvw · 27.12.2009, 03:37

Связанный список - ОК, я просто чесно не знал, как называется

Реализация на C++:

Код:

#include <stdio.h>

/*
 * Demonstration code for sorting a linked list.
 * 
 * The algorithm used is Mergesort, because that works really well
 * on linked lists, without requiring the O(N) extra space it needs
 * when you do it on arrays.
 * 
 * This code can handle singly and doubly linked lists, and
 * circular and linear lists too. For any serious application,
 * you'll probably want to remove the conditionals on `is_circular'
 * and `is_double' to adapt the code to your own purpose. 
 * 
 */

/*
 * This file is copyright 2001 Simon Tatham.
 * 
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#define FALSE 0
#define TRUE 1

typedef struct element element;
struct element {
    element *next, *prev;
    int i;
};

int cmp(element *a, element *b) {
    return a->i - b->i;
}

/*
 * This is the actual sort function. Notice that it returns the new
 * head of the list. (It has to, because the head will not
 * generally be the same element after the sort.) So unlike sorting
 * an array, where you can do
 * 
 *     sort(myarray);
 * 
 * you now have to do
 * 
 *     list = listsort(mylist);
 */
element *listsort(element *list, int is_circular, int is_double) {
    element *p, *q, *e, *tail, *oldhead;
    int insize, nmerges, psize, qsize, i;

    /*
     * Silly special case: if `list' was passed in as NULL, return
     * NULL immediately.
     */
    if (!list) return NULL;

    insize = 1;

	while (1)
	{
		p = list;
		oldhead = list; /* only used for circular linkage */
		list = NULL;
		tail = NULL;

		nmerges = 0;  /* count number of merges we do in this pass */

		while (p)
		{
			nmerges++;  /* there exists a merge to be done */
			/* step `insize' places along from p */
			q = p;
			psize = 0;
			for (i = 0; i < insize; i++)
			{
				psize++;
				//if (is_circular) q = (q->next == oldhead ? NULL : q->next);
				else q = q->next;
				if (!q) break;
			}

			/* if q hasn't fallen off end, we have two lists to merge */
			qsize = insize;

			/* now we have two lists; merge them */
			while (psize > 0 || (qsize > 0 && q))
			{

				/* decide whether next element of merge comes from p or q */
				if (psize == 0)
				{
					/* p is empty; e must come from q. */
					e = q;
					q = q->next;
					qsize--;
					//if (is_circular && q == oldhead) q = NULL;
				}
				else if (qsize == 0 || !q)
				{
					/* q is empty; e must come from p. */
					e = p;
					p = p->next;
					psize--;
					//if (is_circular && p == oldhead) p = NULL;
				}
				else if (cmp(p, q) <= 0)
				{
					/* First element of p is lower (or same);
					* e must come from p. */
					e = p;
					p = p->next;
					psize--;
					//if (is_circular && p == oldhead) p = NULL;
				}
				else
				{
					/* First element of q is lower; e must come from q. */
					e = q; q = q->next; qsize--;
					//if (is_circular && q == oldhead) q = NULL;
				}

				/* add the next element to the merged list */
				if (tail)
				{
					tail->next = e;
				} 
				else
				{
					list = e;
				}
				//if (is_double)
				//{
					///* Maintain reverse pointers in a doubly linked list. */
					//e->prev = tail;
				//}
				tail = e;
			}

			/* now p has stepped `insize' places along, and q has too */
			p = q;
		}
		if (is_circular)
		{
			tail->next = list;
			if (is_double) list->prev = tail;
		}
		else tail->next = NULL;

		/* If we have done only one merge, we're finished. */
		if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
			return list;

		/* Otherwise repeat, merging lists twice the size */
		insize *= 2;
	}
}

/*
 * Small test rig with three test orders. The list length 13 is
 * chosen because that means some passes will have an extra list at
 * the end and some will not.
 */

int main(void) {
    #define n 13
    element k[n], *head, *p;
    int is_circular, is_double;

    int order[][n] = {
        { 0,1,2,3,4,5,6,7,8,9,10,11,12 },
        { 6,2,8,4,11,1,12,7,3,9,5,0,10 },
        { 12,11,10,9,8,7,6,5,4,3,2,1,0 },
    };
    int i, j;

    for (j = 0; j < n; j++)
        k[j].i = j;

    listsort(NULL, 0, 0);

    for (is_circular = 0; is_circular < 2; is_circular++) {
	for (is_double = 0; is_double < 2; is_double++) {
	    for (i = 0; i < sizeof(order)/sizeof(*order); i++) {
		int *ord = order[i];
		head = &k[ord[0]];
		for (j = 0; j < n; j++) {
		    if (j == n-1)
			k[ord[j]].next = (is_circular ? &k[ord[0]] :
					  NULL);
		    else
			k[ord[j]].next = &k[ord[j+1]];
		    if (is_double) {
			if (j == 0)
			    k[ord[j]].prev = (is_circular ? &k[ord[n-1]] :
					      NULL);
			else
			    k[ord[j]].prev = &k[ord[j-1]];
		    }
		}

		printf("before:");
		p = head;
		do {
		    printf(" %d", p->i);
		    if (is_double) {
			if (p->next && p->next->prev != p)
			    printf(" [REVERSE LINK ERROR!]");
		    }
		    p = p->next;
		} while (is_circular ? (p != head) : (p != NULL));
		printf("\n");
		head = listsort(head, is_circular, is_double);
		printf(" after:");
		p = head;
		do {
		    printf(" %d", p->i);
		    if (is_double) {
			if (p->next && p->next->prev != p)
			    printf(" [REVERSE LINK ERROR!]");
		    }
		    p = p->next;
		} while (is_circular ? (p != head) : (p != NULL));
		printf("\n");
	    }
	}
    }
    return 0;
}

Вот, собственно...
Ну только в ней еще предусмотраны варианты когда первый элемент списка - он же ссылка на следующий элемент последнего + вариант, когда у элементов есть еще и ссылка на предыдущий элемент - но мне эти не нужны (поэтому закомментировал).

Добавлено через 3 минуты

Цитата:

Сообщение от GAIKER

Вот тут хорошо визуализированы и объяснены алгоритмы сортировки http://www.sorting-algorithms.com/

Цитата:

Sorting is a vast topic; this site explores the topic of in-memory generic algorithms for arrays. External sorting, radix sorting, string sorting, and linked list sorting—all wonderful and interesting topics—are deliberately omitted to limit the scope of discussion.

Не, это вообще про другое...

r_r_f_r · 28.12.2009, 00:11

Код AS3:

package {
	import flash.display.Sprite;
 
	public class TestLink extends Sprite
	{
		protected var _linkHead:ListObject;
 
		public function TestLink()
		{
			initList();
			trace ('start list:');
			traceList(_linkHead);
			sortList(_linkHead);
			trace ('sotr list:');
			traceList(_linkHead);
		}
 
		protected function traceList(head:ListObject):void
		{
			var ar:Array = [];
			var list:ListObject = head;
			while (list)
			{
				ar.push(list);
				list = list.next;
			}
			trace (ar);
		}
 
		protected function sortList(head:ListObject):void
		{
			var list:ListObject = head;
			var list2:ListObject;
 
			while (list)
			{
				list2 = list.next;
 
				while (list2)
				{
					if (list < list2)
					{
						var l1next:ListObject = list.next;
						var l1prev:ListObject = list.prev;
 
						var l2next:ListObject = list2.next;
						var l2prev:ListObject = list2.prev;
 
						if (l1next)
						{
							l1next.prev = list2;
						}
						if (l1prev)
						{
							l1prev.next = list2;
						}
 
						if (list2 != l1next)
						{
							list2.next = l1next;
						}
						else
						{
							list2.next = list;
						}
 
						if (list2 != l1prev)
						{
							list2.prev = l1prev;
						}
						else
						{
							list2.prev = list;
						}
 
						if (l2next)
						{
							l2next.prev = list;
						}
						if (l2prev)
						{
							l2prev.next = list;
						}
 
						if (list != l2next)
						{
							list.next = l2next;
						}
						else
						{
							list.next = list2;
						}
 
						if (list != l2prev)
						{
							list.prev = l2prev;
						}
						else
						{
							list.prev = list2;
						}
 
						l1next = list;
						list = list2;
						list2 = l1next; 
					}
					list2 = list2.next;
				}
				list = list.next;
			}
 
			while (_linkHead.prev)
			{
				_linkHead = _linkHead.prev;
			}
		}
 
		protected function initList():void
		{
			_linkHead = new ListObject(Math.random()*20,0);
 
			var list:ListObject = _linkHead;
			var count:uint = 100;
			var i:uint = count;
 
			while (i--)
			{
				list.next = new ListObject(Math.random()*1000,count-i);
				list.next.prev = list;
				list = list.next;
			}
		}
	}
}

и

Код AS3:

package
{
	public class ListObject
	{
		public var prev:ListObject;
		public var next:ListObject;
		public var value:uint = 0;
		public var ind:uint = 0;
 
		public function ListObject(value:uint, ind:uint)
		{
			this.value = value;
			this.ind = ind;
		}
 
		public function toString():String
		{
			return '[' + String(value) + ',' + String(ind) + ']';
		}
 
		public function valueOf():Object
		{
			return value;
		}
	}
}

так?

wvxvw · 28.12.2009, 00:30

Офигенно, спасибо, вроде работает - сейчас попробую прикрутить к своему варианту

А то я уже отчаялся и через "пузырек" сделал...
Чего в кредитах написать?

r_r_f_r · 28.12.2009, 00:37

так это и есть пузырёк

кредиты можно оставить пустым, я не гордый

и это ещё можно оптимизировать по условиям - вся куча if{}else{} проверяет только нахождение двух объектов рядом -> можно как-нить одним-двумя предварительным условием отстреляться.

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

Gaen · 28.12.2009, 00:44

Почему все этот пузырек так любят? Сортировка выбором работает быстрее, и пишется легче

r_r_f_r · 28.12.2009, 00:49

Цитата:

Сообщение от GAIKER

Почему все этот пузырек так любят? Сортировка выбором работает быстрее, и пишется легче

вот, напишите

Код AS3:

		protected function swap(list:ListObject,list2:ListObject):void
		{
			var l1next:ListObject = list.next;
			var l1prev:ListObject = list.prev;
 
			var l2next:ListObject = list2.next;
			var l2prev:ListObject = list2.prev;
 
			if (l1next)
			{
				l1next.prev = list2;
			}
			if (l1prev)
			{
				l1prev.next = list2;
			}
 
			if (list2 != l1next)
			{
				list2.next = l1next;
			}
			else
			{
				list2.next = list;
			}
 
			if (list2 != l1prev)
			{
				list2.prev = l1prev;
			}
			else
			{
				list2.prev = list;
			}
 
			if (l2next)
			{
				l2next.prev = list;
			}
			if (l2prev)
			{
				l2prev.next = list;
			}
 
			if (list != l2next)
			{
				list.next = l2next;
			}
			else
			{
				list.next = list2;
			}
 
			if (list != l2prev)
			{
				list.prev = l2prev;
			}
			else
			{
				list.prev = list2;
			}
		}

wvxvw · 28.12.2009, 01:08

Цитата:

Сообщение от r_r_f_r

так это и есть пузырёк

кредиты можно оставить пустым, я не гордый

и это ещё можно оптимизировать по условиям - вся куча if{}else{} проверяет только нахождение двух объектов рядом -> можно как-нить одним-двумя предварительным условием отстреляться.

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

Ерм... для пузырька не нужен предыдущий элемент вообще-то... пузырек, это:
сравнили пару, если А = Б или А < Б - переходим к следующей - нет - отправляем А в самый конец, и так пока не упремся в Б = null...
Так что это не пузырек, или сильно замаскированый

Цитата:

Сообщение от GAIKER

Почему все этот пузырек так любят? Сортировка выбором работает быстрее, и пишется легче

Ну, чесно, если пишется легче - напишите

я срадостью за вас чего-нть другое взамен напишу - у меня вдохновения на это не хватает