Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Метод линейной вставки





 

При сортировке исходного вектора A методом линейной вставки последовательно просматриваются элементы вектора A и формируется упорядоченный вектор B. До начала сортировки считается, что длина упорядоченного вектора равно 0. Как только длина упорядоченного вектора станет равной длине исходного вектора, сортировка закончена.

Первый элемент вектора A помещается в первую позицию вектора B. Длина вектора становится равной 1.

Второй элемент вектора A сравнивается со всеми элементами вектора B. Если он больше всех элементов вектора В, то помещаем его в конец вектора и при этом длина вектора В увеличивается на единицу. Если в векторе В найдется элемент, меньший сравниваемого, то фиксируем позицию этого элемента, и все элементы вектора В, начиная с этой позиции, перемещаем на одну позицию вправо, начиная с последнего. На освободившееся место помещаем сравниваемый элемент. Длину вектора В увеличиваем на единицу.

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

 

Просмотр Исходный вектор А Полученный вектор В
1-ый 2 4 8 5 6 1 2
2-ой 2 4 8 5 6 1 2 4
3-ий 2 4 8 5 6 1 2 4 8
4-ый 2 4 8 5 6 1 2 4 8 2 4 5 8
5-ый 2 4 8 5 6 1 2 4 5 8 2 4 5 6 8
6-ой 2 4 8 5 6 1 2 4 5 6 8 2 4 5 6 8 2 4 5 6 8 2 4 5 6 8 2 4 5 6 8 2 4 5 6 8 1 2 4 5 6 8

B[1]:=A[1];

k:=1;

For i:=2 to n do

Begin

j:=1;

While (j<=k) and (a[i]>b[j]) do

j:=j+1;

If j=k+1 then

Begin

b[j]:=a[i];

k:=k+1;

End

Else

Begin

For l:=k+1 downto j+1 do

b[l]:=b[l-1];

b[j]:=a[i];

k:=k+1;

end;

end;

 

Сравнение методов по основным характеристикам

для вектора размерности n

Метод сортировки Минимальное и максимальное число сравнение Количество перемещений или обменов
Линейный выбор , n перемещений
Линейный выбор с обменом , n обменов
Линейны выбор с подсчетом , n перемещений и подсчетов
Парный обмен n, обменов
Метод стандартного обмена n, обменов
Метод просеивания n, обменов
Метод линейной вставки n, перемещений

 


Date: 2015-10-19; view: 243; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию