Translate

неділя, 17 березня 2013 р.

Проектування функції сортування чисел методом "бульбашки" з використанням технології Blueprint


При сортуванні методом "бульбашки" числа в масиві міняются місцями, якщо дві сусідні величини розташовані не по зростанню. В цьому методі відбуваєтся перегляд масиву поки всі можливі пари елементів не будуть переглянуті і можливо переставлені.

Алгоритм сортування в псевдокоді:

  1. K = кількість елементів масиву - 1
  2. ЦИКЛ-ПОКИ K >= 1
    1. Перемістити найбільше ціле в останні елемент масиву
    2. Зменшити К на 1
  3. КІНЕЦЬ-ЦИКЛУ 
Деталізація кроку 2.1 :
  1. J = 1
  2. ЦИКЛ-ПОКИ J <= K
    1. Порівняти чергову пару і переставити при потребі
    2. Збільшити J на 1
  3.  КІНЕЦЬ-ЦИКЛУ
Деталізація кроку 2.1 :
  1.  ЯКЩО елемент масиву (J) > елемент масиву (J + 1)
    1. Тимч = елемент масиву (J)
    2. Елемент масиву (J) = елемент масиву (J + 1)
    3. Елемент масиву (J + 1) = Тимч
  2.  КІНЕЦЬ-ЯКЩО
Запис функції з використанням технології Blueprint :

<?xml version="1.0" encoding="utf-8"?>
<?xml-stylesheet type="text/xsl" href=".blueprint/model.xslt"?>
<!DOCTYPE model SYSTEM ".blueprint/model.dtd">
<model name="Buble sorting">
    <description>Buble soritng of the array in increasing sequence</description>
    <classes>
        <class name="Sorter">
            <parameterized-types>
                <parameterized-type name="Type" class="Comparator" type="Comparator" />
            </parameterized-types>
            <attributes>
                <types>
                    <array of-type="Type" name="Array" />
                </types>
            </attributes>
            <operations>
                <method name="sort" visibility="public">
                    <description>Buble sort of the array</description>
                    <parameters>
                        <parameter name="array" type="Array"></parameter>
                    </parameters>
                    <data>
                        <variable name="k" primitive="integer" />
                        <variable name="j" primitive="integer" />
                        <variable name="temp" type="Type" />
                    </data>
                    <algorithm>
                        <doing>set k to size of array</doing>
                        <while condition="k >= 1">
                            <step>
                                <action>move greater value in the tail of array</action>
                                <detailing>
                                    <doing>set j to 1</doing>
                                    <while condition="j &lt;= k">
                                        <step>
                                            <action>compare next pair and replace when necessary</action>
                                            <detailing>
                                                <if condition="array[j] &gt; array[j+1]">
                                                    <then>
                                                        <doing>set temp to array[j]</doing>
                                                        <doing>set array[j] to array[j+1]</doing>
                                                        <doing>set array[j+1] to temp</doing>
                                                    </then>
                                                </if>
                                            </detailing>                                       
                                        </step>
                                        <increase variable="j" />
                                    </while>
                                </detailing>
                            </step>
                            <decrease variable="k" />
                        </while>
                    </algorithm>
                </method>
            </operations>
        </class>
    </classes>       
</model>

Вигляд документу в бровзері :