Форум Flasher.ru - Сортировка массивов

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Сортировка массивов (http://www.flasher.ru/forum/showthread.php?t=135055)

xpymbl4

14.01.2010 20:08

Сортировка массивов

Ишется алгоритм для ручной сортировки массивов.
Что имеется:

Код AS3:

var a1:Array = [12, 3, 1, 2, 2]; /*массив числовых данных типа int 

неопределенной длины, с разными/одинаковыми, неупорядоченными значениями*/

var a2:Array = ['a', 'b', 'c', 'd', 'e'] /*массив каких-либо объектов,

в данном случае для удобства и наглядности они представлены в виде

строковых данных, причем a1.length == a2.length;*/;

Необходимо получить массивы:

Код AS3:

a1 = [1, 2, 2, 3, 12]; /* массив отсортирован по возрастанию*/

a2 = ['c', 'd', 'e', 'b', 'a']; /*данные упорядочены таким образом,

что как и изначально, элемент массива a2 с индексом i

соответствует элементу массива a1 с индексом i*/

Как бы Вы это реализовали правильно и красиво?

udaaff

14.01.2010 20:15

Объединить числа из первого массива с соответствующими объектами из второго в одном объекте { index: 12, value: 'a' }, и сортировать по полю index.

wvxvw

14.01.2010 20:24

я бы добавил колбек в sort() первого массива и в нем бы сортировал второй... ну, скажем для коротких массивов это может быть не актуально, но для длинных - это ж нужно будет добавить целый массив фейк объектов которые нужны только для сортировки...

Код AS3:

//              1,    2,   2,   3,   12

var a1:Array = [12,   3,   1,   2,   2];

//              c,    e,   a,   d,   b

var a2:Array = ["a", "b", "c", "d", "e"];

 

function numSort(a:int, b:int):int

{

        var index:int;

        var s:String;

        if (a > b)

        {

                index = a1.indexOf(a);

                s = a2.splice(index, 1)[0];

                a2.push(s);

                return 1;

        }

        else if (a < b)

        {

                return -1;

        }

        return 0;

}

a1.sort(numSort);

trace(a2, a1);

Вроде так, не? :)

EDIT:
Ой не... так не получится... сейчас посмотрел, там пары в каком-то странном порядке передаются и массив сам во время сортировки не меняется... вобщем, сорри, тогда только совй сот писать :)

Ixanezis

14.01.2010 23:16

Используйте любой стандартный алгоритм сортировки.
К примеру есть у вас QuickSort
(Если не знаете, это такой быстрый алгоритм для сортировки (Сложность N*log N))
Взял на С++ что писал когда-то:

Код:

Quick(int b, int e)

{

        int i=b, j=e;

        int X = ar[(b+e) / 2]; // Здесь надо выбрать любой элемент массива.

        while (i<=j) {

                while (ar[i] < X) i++;

                while (ar[j] > X) j--;

                if (i<=j) {

                        int tmp = ar[i];

                        ar[i] = ar[j];

                        ar[j] = tmp;



                        i++;

                        j--;

                }

        }

        if (i<e) Quick(i, e);

        if (b<j) Quick(b, j);

}

Этот алгоритм отсортирует массив ar, начиная с индекса b до e включительно
То есть вызывать функцию надо так:
Quick(0, a1.length-1); // Если взять ваш пример

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

Код:

Quick(int b, int e)

{

        int i=b, j=e;

        int X = ar[(b+e) / 2]; // Здесь надо выбрать любой элемент массива.

        while (i<=j) {

                while (ar[i] < X) i++;

                while (ar[j] > X) j--;

                if (i<=j) {

                        int tmp = ar[i];

                        ar[i] = ar[j];

                        ar[j] = tmp;



                        Type tmp1 = ar1[i];

                        ar1[i] = ar1[j];

                        ar1[j] = tmp1;



                        i++;

                        j--;

                }

        }

        if (i<e) Quick(i, e);

        if (b<j) Quick(b, j);

}

Crenth

15.01.2010 09:27

скачайте книгу "СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
Bell Laboratories
Муррей-Хилл, Нью-Джерси
ДЖОН Э. ХОПКРОФТ ТЧОЯЛЧС
Корнеллский университет
Итака, Нью-Йорк
ДЖЕФФРИ Д. УЛЬМАН
Станфордский университет
Стамфорд, Калифорния

Она в русском переводе. Страница 228 - есть 100 методов сортировки с готовым кодом
Будет очень красиво :)

mayakwd

15.01.2010 10:45

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

alexcon314

15.01.2010 11:36

Ну да, почему бы не реализовать вручную тот же пузырек? Просто двигать вместе с элементами а1 соответствующие элементы а2.

Код:

var a1:Array = [12, 3, 1, 2, 2];

/*массив числовых данных типа int 

неопределенной длины, с разными/одинаковыми, неупорядоченными значениями*/

var a2:Array = ['a', 'b', 'c', 'd', 'e'];

/*массив каких-либо объектов,

в данном случае для удобства и наглядности они представлены в виде

строковых данных, причем a1.length == a2.length;*/



function sort(a1, a2) {

        var i:Number = 0;

        var j:Number = 0;

        var x:Number = 0;

        var s:String = '';

        var size = a1.length;

        for (i = 0; i < size; i++) {

                for (j = size - 1; j > i; j--) {

                        if (a1[j - 1] > a1[j]) {

                                x = a1[j - 1];

                                s = a2[j - 1];

                                a1[j - 1] = a1[j];

                                a2[j - 1] = a2[j];

                                a1[j] = x;

                                a2[j] = s;

                        }

                }

        }

}

trace(a1);trace(a2);

sort(a1, a2);

trace(a1);trace(a2);

Ixanezis

15.01.2010 12:40

Вот и я про тоже.. Только если элементов много, то он не прокатит..

xpymbl4

15.01.2010 13:30

Спасибо.
Пузырек вполне подходит и работает на ура. :)
Только я вместо

Код AS3:

var s:String = '';

пишу:

Код AS3:

var s:Object;

gloomyBrain

15.01.2010 20:00

А чем плох Array.sortOn()? Или Vector.sort(myFunction)? В случае с вектором (FP 10 only) по идее будет даже быстрее, чем с Array... В обоих случаях имеется ввиду Object с полями index и value, как писал udaaff

wvxvw

15.01.2010 20:20

В том, что если изначально есть 2 массива, то создавать третий - не тру путь :) Как бы перерасход памяти и т.п.

udaaff

15.01.2010 20:42

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

wvxvw

15.01.2010 21:34

Если изначально - то да, а если впоследствии, то, сами посудите, у вас было 2 массива, а вы только для сортировки создали лишний массив с N временных объектов, которые тут же выбросите после использования. Как бы ок, GC поработает + на их создание уйдет еще какое-то время... но это идеологически не подходит (если дано, что есть именно 2 массива, и никак нельзя, чтобы это был один) :)

udaaff

15.01.2010 21:46

Ну, в общем, согласен. Идеологически не катит :)

Bgg	31.03.2010 17:04

А есть возможность отсортировать только определенные объекты в массиве?

Код AS3:

obj_1.id = 60;

obj_1.toSort = false;

 

obj_2.id = 55;

obj_2.toSort = true;

 

obj_3.id = 54;

obj_3.toSort = true;

//сортировка аля sortOn("id", Array.NUMERIC && "toSort" = true);

[obj_1, obj_3, obj_2]//результат

Пока пришло на ум только создание двух массивов, но это какой то костыль.

Часовой пояс GMT +4, время: 00:46.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.