4. for j:=1 to i do
5. compare-exchange(aj,aj+1);
6. end BUBBLE-SORT
Бұл алгоритмде ішкі цикл итерациясы Q(n) уақытта орындалса және Q(n)
итерация жасалса, «көпіршіктер» әдісімен сұрыптауға кететін уақыт - Q(n
2
).
Бұл алгоритмді параллельділікке айналдыру үлкен қиындық келтіреді.
Сондықтан бұл әдістің екінші бір түрі «тақ-жұп орын ауыстыру» алгоритмін
қарастырайық.
3. «тақ-жұп орын ауыстыру» алгоритмі.
Бұл алгоритмде n элемент n фазада сұрыпталады. Бұл алгоритмнің жұп
және тақ фазалары кезектестіріледі. (a
1
, a
2
, ...,a
n
) – тізбегін сұрыптау керек
болсын. Тақ фаза кезінде тақ индексті элементтер оң жақтағы көрші элементпен
салыстырылып, егер шарт орындалса, олар орындарын алмастырады, яғни (a
1
,
а
2
), (a
3
, a
4
), ..., (a
n-1
,a
n
) жұптары салыстырылып алмастырылады. Сол сияқты жұп
фаза кезінде, жұп индексті элементтер салыстырлып, егер шарт орындалса,
олар орындарын алмастырады, яғни (а
2
, a
3
), (a
4
, a
5
), ..., (a
n-2
,a
n-1
) жұптары
салыстырылып алмастырылады. Сонда тақ-жұп ауыстыру n фазасынан кейін
тізбек сұрыпталады. Әрбір алгоритмнің фазасында Q(n) салыстыру жасалса,
барлығы n фаза болса, бұл алгоримтнің (sequential complexity) - Q(n
2
).
Программа 2.
Достарыңызбен бөлісу: |
