Сортировка, Сортировка по индексам... Опции

[Vardes]

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

[klem4]

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

(каждый элемента массива индексов содержит собственный номер, т.е. a[1] = 1, a[2] = 2...a[n] = n);

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

Сообщение отредактировано: klem4 - 25.03.2006 19:24

[Vardes]

Допустим:

2 7 1 4 6 15 18 9 112 0 массив чисел
1 2 3 4 5 6 7 8 9 10 массив индексов

Если взять последний эл-т в массиве чисел и начинать его перестанавливать, то первый шаг у нас будет таким,если я не ошибаюсь:
1 2 3 4 5 6 7 8 10 9, а как же нам запомнить то,что мы 112 и 0 поменяли местами, вот самый главный вопрос,в который я никак не вникнуть

[hardcase]

Мы меням местами не сами значения а ИНДЕСЫ, представь, что ИНДЕКС - это нечто вроде УКАЗАТЕЛЯ в кучу - мы ведь при перестановке меняем местами только указатели а не обмениваем содержимое памяти. В данном случа нам не интересно, как расположены числа в основном массиве - нас интересует расположение ИНДЕКСОВ - ведь мы сортируем какраз этот массив (выбирая информацию для сравнения из массива чисел).

[Vardes]

Ну это мне понятно,что мы меняем местами индексы, а не сами эл-ты массива. Вопрос всё же в том,что массив индексов зависит от массива чисел,и как же проходит реализация последущего сравнения эл-ов в массиве чисел,если там мы изменения никаких не делаем.Или же каждому значению эл-та из массива индексов соответствует значение эл-та из массива чисел.Вроде вот этого :
a: 2 7 1 3 5 2 0
b: 1 2 3 4 5 6 7

a[b[1]]:=2
a[b[2]]:=7
.....
.....

[hardcase]

Да, сравнивать нужно таким образом:

Код

values[indexes[ind_a]] < values[indexes[ind_b]]

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

Т.е. смотри - мы сортируем массив ИНДЕКСОВ, но критерием сравнения являются не сами целочисленные значения индексов, а числа, которые лежат в массиве чисел по этим индексам. Поэтому нам не важно, как расположены числа.

Сообщение отредактировано: hardcase - 26.03.2006 2:35

[Vardes]

Если я всё же вас правильно понимаю, то мы просто берём начальный массив, делаем его копию и работаем уже с его копией. Так или всё же до меня так плохо доходит !?

[hardcase]

Вероятно до тебя плохо доходит.
Ничета мы на копируем.
Идея работы с индексами аналогична идеи работы с указателями, только если в случае с указателям мы должны разыменовать указатель, чтоб добраться до самого значения; то с индексами мы должы всего лишь обратиться к указанному элементу массива.

[Vardes]

Всё, вроде теперь догнал. Ещё и с кодом разобрался. Вот программка, которая сортирует 10 чисел. Возможно, модераторы смогут это выложить в FAQ, а то, что-то совсем на сайте нет ничего про сортировку по ИНДЕКСАМ

Всем спасибо за помощь

Код

type index = array[1..10]  of integer;
Var i,j,k :integer;
b:index;
a:array[1..10] of integer;
begin
for i:=1 to 10 do read(a[i]);
  for i:=1 to 10 do
  b[i]:=i;
    for i:=2 to 10 do
     for j:=10 downto i do
     if a[b[j-1]]>a[b[j]] then
begin
     k:=b[j-1];
     b[j-1]:=b[j];
     b[j]:=k;
end;
for i:=1 to 10 do write(a[b[i]]);
  end.

Сообщение отредактировано: Vardes - 26.03.2006 15:33