НАВИГАЦИЯ
Главная
Учебник
Файлы
Новости
Примеры
Ссылки
Сообщения
Форум
От создателя







Сортировка

Цель сортировки -упорядочивание для облегчения поиска. Существуют несколько методов сортировки. Сортировать можно типы (структуры) и массивы.

Виды сортировки:

1) Сортировка обменом - метод, при котором все соседние элементы массива попарно сравниваются между собой и меняются местами в том случае, если, например, предшествующий элемент больше последующего. В результате этого максимальный элемент смещается вправо и занимает крайнее место. Если не будет сделано ни одной престановки, то массив упорядочен. Код сортировки состоит из двух вложенных циклов с конечным ходом, меньшим на 1. Пусть k - количество элементов, тогда обменов будет (k-1)2 раз.

Пример программного кода на сортировку обменом (массив состоит из 6 элементов):

Dim arr(5)

SeedRnd MilliSecs()
;заполнение массива случайными числами
For i=0 To 5
arr(i)=Rand(0,99)
Write arr(i)+" "
Next

Print " "

;сортировка обменом
For i1=0 To 4
For i=0 To 4
If arr(i)>arr(i+1) Then
arr(i)=arr(i)+arr(i+1)
arr(i+1)=arr(i)-arr(i+1)
arr(i)=arr(i)-arr(i+1)
End If
Next
Next

;вывод отсортированного массива
For i=0 To 5
Write arr(i)+" "
Next

WaitKey()
End

Например, в массиве 4 элемента( размер массива 3): 5 1 4 3
при i1=0, i=0: 1 5 4 3
при i1=0, i=1: 1 4 5 3
при i1=0, i=2: 1 4 3 5
при i1=0, i=3: 1 4 3 5
при i1=1, i=0: 1 4 3 5
при i1=1, i=1: 1 3 4 5
при i1=1, i=2: 1 3 4 5
при i1=1, i=3: 1 3 4 5
при i1=2, i=0: 1 3 4 5
при i1=2, i=1: 1 3 4 5
при i1=2, i=2: 1 3 4 5
при i1=2, i=3: 1 3 4 5
при i1=3, i=0: 1 3 4 5
при i1=3, i=1: 1 3 4 5
при i1=3, i=2: 1 3 4 5
при i1=3, i=3: 1 3 4 5
Сразу можно выявить минус этого метода: если массив отсортирован, действие всё-равно будет продолжаться.

2) Сортировка выбором - в неупорядоченном массиве выбирается максимальный или минимальный элемент и меняется местами с первым элементом, затем исключается из дальнейшей обработки. Главное его приемущество - он быстрее метода обменом, так как всего сортировок будет выполненно k раз.

Пример программного кода на сортировку выбором (массив состоит из 5 элементов):

Dim arr(4)
SeedRnd MilliSecs()
;заполнение массива случайными числами
For i=0 To 4
arr(i)=Rand(0,99)
Write arr(i)+" "
Next

Print " "

;сортировка выбором
For i1=0 To 4
min=arr(i1)
mp=i1

;поиск минимального элемента
For i=i1 To 4
If min>arr(i) Then
min=arr(i)
mp=i
End If
Next

z=arr(i1)
arr(i1)=arr(mp)
arr(mp)=z
Write arr(i1)+" "
Next

WaitKey()
End
X