Страницы

среда, 21 ноября 2012 г.

Строки. Индексы и срезы.

К элементам строки можно обращаться но индексу, прямо как в С. Первый символ строки имеет индекс 0. В отличие от языка С, строки в Python изменять нельзя. Назначение значения индексу строки, приведет к ошибке.
>>> s = 'Hello'
>>> s[0]
'H'
>>> s[0] = 'h'
Traceback (most recent call last):
  File "&;lt;pyshell#38>", line 1, in <module>
    s[0] = 'h'
TypeError: 'str' object does not support item assignment
Операция извлечения нескольких индексов, называется срезом. Для создания среза (подстроки) используется два индекса, разделенные двоеточиями.
>>>word = 'HelpA'
>>> word[4]
'A'
>>> word[0:2]
'He'
>>> word[2:4]
'lp'
У среза опущенный первый индекс по умолчанию будет равен нулю, а второй размеру строки.
>>> word[:2]    # The first two characters
'He'
>>> word[2:]    # Everything except the first two characters
'lpA'
Третий индекс в срезе означает шаг.
>>> word = 'HelpA'
>>> word[::2]
'HlA'
При помощи срезом можно очень просто и в тоже время очень эффективно создавать новые строки на базе уже имеющихся.
>>> 'x' + word[1:]
'xelpA'
>>> 'Splat' + word[4]
'SplatA'
>>> word[:2] + word[2:]
'HelpA'
>>> word[:3] + word[3:]
'HelpA'
Вырожденные срезы обрабатываются корректно. Слишком большой индекс, заменяется на размер строки, а если верхняя граница меньше, чем нижняя возвращается пустая строка.
>>> word[1:100]
'elpA'
>>> word[10:]
''
>>> word[2:1]
''
Индексы могут быть отрицательными, в этом случае отсчет начинается с права.
>>> word[-1]     # The last character
'A'
>>> word[-2]     # The last-but-one character
'p'
>>> word[-2:]    # The last two characters
'pA'
>>> word[:-2]    # Everything except the last two characters
'Hel'
>>> word[-0]     # (since -0 equals 0)
'H'
Следует обратить внимание, что -0 это 0, поэтому отсчет не начинается с права. В случаи, если отрицательные индексы выходят за диапазон, срез усекается. Но это не сработает, если индекс будет один, интерпретатор выдаст ошибку.
>>> word[-100:]
'HelpA'
>>> word[-10]    # error
Traceback (most recent call last):
  File "", line 1, in ?
IndexError: string index out of range
Можно легко запомнить как работают срезы, если представить индексы как указатели между символами.
 +---+---+---+---+---+
 | H | e | l | p | A |
 +---+---+---+---+---+
 0   1   2   3   4   5
-5  -4  -3  -2  -1
Небольшой фокус. Если сделать полный срез строки, но с отрицательным шагом, мы получим перевернутую строку.
>>> word
'HelpA'
>>> word[::-1]
'ApleH'
А для того чтобы получить последний элемент в строке, достаточно просто задать индекс -1.
>>> word
'HelpA'
>>> word[-1]
'A'

Строки. Основы.

Первое, что следует понять в Python строки это не изменяемые объекты. Каждый раз когда мы вносим изменения в строку, мы создаем новую. Строки могут быть записаны несколькими способами. Их можно заключить в одинарные или двойные кавычки.
>>> 'spam eggs'
'spam eggs'
>>> 'doesn\'t'
"doesn't"
>>> "doesn't"
"doesn't"
>>> '"Yes," he said.'
'"Yes," he said.'
>>> "\"Yes,\" he said."
'"Yes," he said.'
>>> '"Isn\'t," she said.'
'"Isn\'t," she said.'
Интерпретатор печатает символы, так же как они были набраны, за исключением кавычек и непечатаемых символов, для их отображения используется экранирование, обратная косая черта. Строковые литералы могут занимать несколько строк, для этого следует в конце строки поставить знак "\", указав, что следующая строка это логическое продолжение. Для переноса строки используется непечатаемый символ "\n".
hello = "This is a rather long string containing\n\
several lines of text just as you would do in C.\n\
    Note that whitespace at the beginning of the line is\
 significant."

print hello

This is a rather long string containing
several lines of text just as you would do in C.
    Note that whitespace at the beginning of the line is significant.
Так же строки могут находиться внутри тройных кавычек ''' или """. При таком форматировании строки будут выводиться на экран как есть. Этот подход часто используется для создания документации к модулю или программе.
print """
Usage: thingy [OPTIONS]
     -h                        Display this usage message
     -H hostname               Hostname to connect to
"""

Usage: thingy [OPTIONS]
     -h                        Display this usage message
     -H hostname               Hostname to connect to 
Для того чтобы сделать строковый литерал не изменяемым, необходимо перед ним поставить знак "r" ("raw"). В этом случае интерпретатор не будет обрабатывать непечатаемые символы, такие как "\n". Такой подход удобно использовать при формировании путей к файлам, так как путь может содержать "\n" (перенос строки) или "\t" (табуляция).
>>> path = 'C:\new\tmp'
>>> print path
C:
ew mp

>>> path = r'C:\new\tmp'
>>> print path
C:\new\tmp
>>> 
Строки можно объединять (конкатенировать) при помощи оператора "+" или повторять, оператор "*"
>>> word = 'Help' + 'A'
>>> word
'HelpA'
>>> '<' + word*5 + '>'
'<HelpAHelpAHelpAHelpAHelpA&>'
Если литералы стоят рядом друг с другом, они автоматически объединятся.
>>> 'hello ' 'world' '!' '.'
'hello world!.'

пятница, 22 июня 2012 г.

Списки репозиториев Debian

Списки репозиториев Debian

## STABLE | Стабильный дистрибутив SQUEEZE
# deb ftp://ftp.ru.debian.org/debian/ stable main contrib non-free
# deb-src ftp://ftp.ru.debian.org/debian/ stable main contrib non-free
# deb http://debian.nsu.ru/debian/ stable main contrib non-free
# deb-src http://debian.nsu.ru/debian/ stable main contrib non-free
# deb http://ftp.corbina.net/debian/ stable main contrib non-free
# deb-src http://ftp.corbina.net/debian/ stable main contrib non-free
# deb http://ftp.debian.chuvsu.ru/debian/ stable main contrib non-free
# deb-src http://ftp.debian.chuvsu.ru/debian/ stable main contrib non-free
# deb http://ftp.psn.ru/debian/ stable main contrib non-free
# deb-src http://ftp.psn.ru/debian/ stable main contrib non-free
# deb http://mirror2.corbina.ru/debian/ stable main contrib non-free
# deb-src http://mirror2.corbina.ru/debian/ stable main contrib non-free
# deb http://mirror.svk.su/debian/ stable main contrib non-free
# deb-src http://mirror.svk.su/debian/ stable main contrib non-free
# deb http://mirror.yandex.ru/debian/ stable main contrib non-free
# deb-src http://mirror.yandex.ru/debian/ stable main contrib non-free

## TESTING | Тестируемый дистрибутив
# deb ftp://ftp.ru.debian.org/debian/ testing main contrib non-free
# deb-src ftp://ftp.ru.debian.org/debian/ testing main contrib non-free
# deb http://ftp.ru.debian.org/debian/ testing main contrib non-free
# deb-src http://ftp.ru.debian.org/debian/ testing main contrib non-free
# deb http://debian.nsu.ru/debian/ testing main contrib non-free
# deb-src http://debian.nsu.ru/debian/ testing main contrib non-free
# deb http://ftp.corbina.net/debian/ testing main contrib non-free
# deb-src http://ftp.corbina.net/debian/ testing main contrib non-free
# deb http://ftp.debian.chuvsu.ru/debian/ testing main contrib non-free
# deb-src http://ftp.debian.chuvsu.ru/debian/ testing main contrib non-free
# deb http://ftp.psn.ru/debian/ testing main contrib non-free
# deb-src http://ftp.psn.ru/debian/ testing main contrib non-free
# deb http://mirror2.corbina.ru/debian/ testing main contrib non-free
# deb-src http://mirror2.corbina.ru/debian/ testing main contrib non-free
# deb http://mirror.svk.su/debian/ testing main contrib non-free
# deb-src http://mirror.svk.su/debian/ testing main contrib non-free
# deb http://mirror.yandex.ru/debian/ testing main contrib non-free
# deb-src http://mirror.yandex.ru/debian/ testing main contrib non-free

## UNSTABLE | Нестабильный дистрибутив SID
# deb ftp://ftp.ru.debian.org/debian/ unstable main contrib non-free
# deb-src ftp://ftp.ru.debian.org/debian/ unstable main contrib non-free
# deb http://ftp.ru.debian.org/debian/ unstable main contrib non-free
# deb-src http://ftp.ru.debian.org/debian/ unstable main contrib non-free
# deb http://debian.nsu.ru/debian/ unstable main contrib non-free
# deb-src http://debian.nsu.ru/debian/ unstable main contrib non-free
# deb http://ftp.corbina.net/debian/ unstable main contrib non-free
# deb-src http://ftp.corbina.net/debian/ unstable main contrib non-free
# deb http://ftp.debian.chuvsu.ru/debian/ unstable main contrib non-free
# deb-src http://ftp.debian.chuvsu.ru/debian/ unstable main contrib non-free
# deb http://ftp.psn.ru/debian/ unstable main contrib non-free
# deb-src http://ftp.psn.ru/debian/ unstable main contrib non-free
# deb http://mirror2.corbina.ru/debian/ unstable main contrib non-free
# deb-src http://mirror2.corbina.ru/debian/ unstable main contrib non-free
# deb http://mirror.svk.su/debian/ unstable main contrib non-free
# deb-src http://mirror.svk.su/debian/ unstable main contrib non-free
# deb http://mirror.yandex.ru/debian/ unstable main contrib non-free
# deb-src http://mirror.yandex.ru/debian/ unstable main contrib non-free

## APTtoSID
# deb http://aptosid.com/debian sid main fix.main 

## OFFICIAL SQUEEZE SECURITY | Обновления безопасности SQUEEZE
# deb ftp://ftp.ru.debian.org/debian-security squeeze/updates main non-free contrib
# deb-src ftp://ftp.ru.debian.org/debian-security squeeze/updates main non-free contrib
# deb http://ftp.ru.debian.org/debian-security squeeze/updates main non-free contrib
# deb-src http://ftp.ru.debian.org/debian-security squeeze/updates main non-free contrib
# deb http://debian.nsu.ru/debian-security squeeze/updates main non-free contrib
# deb-src http://debian.nsu.ru/debian-security squeeze/updates main non-free contrib
# deb http://ftp.corbina.net/debian-security squeeze/updates main non-free contrib
# deb-src http://ftp.corbina.net/debian-security squeeze/updates main non-free contrib
# deb http://ftp.debian.chuvsu.ru/debian-security squeeze/updates main non-free contrib
# deb-src http://ftp.debian.chuvsu.ru/debian-security squeeze/updates main non-free contrib
# deb http://ftp.psn.ru/debian-security squeeze/updates main non-free contrib
# deb-src http://ftp.psn.ru/debian-security squeeze/updates main non-free contrib
# deb http://mirror2.corbina.ru/debian-security squeeze/updates main non-free contrib
# deb-src http://mirror2.corbina.ru/debian-security squeeze/updates main non-free contrib
# deb http://mirror.svk.su/debian-security squeeze/updates main non-free contrib
# deb-src http://mirror.svk.su/debian-security squeeze/updates main non-free contrib
# deb http://mirror.yandex.ru/debian-security squeeze/updates main non-free contrib
# deb-src http://mirror.yandex.ru/debian-security squeeze/updates main non-free contrib

## OFFICIAL SQUEEZE BACKPORTS | Новые версии пакетов для SQUEEZE
# deb ftp://ftp.ru.debian.org/debian-backports squeeze-backports main contrib
# deb-src ftp://ftp.ru.debian.org/debian-backports squeeze-backports main contrib
# deb http://ftp.ru.debian.org/debian-backports squeeze-backports main contrib
# deb-src http://ftp.ru.debian.org/debian-backports squeeze-backports main contrib
# deb http://debian.nsu.ru/debian-backports squeeze-backports main contrib
# deb-src http://debian.nsu.ru/debian-backports squeeze-backports main contrib
# deb http://ftp.corbina.net/debian-backports squeeze-backports main contrib
# deb-src http://ftp.corbina.net/debian-backports squeeze-backports main contrib
# deb http://ftp.debian.chuvsu.ru/debian-backports squeeze-backports main contrib
# deb-src http://ftp.debian.chuvsu.ru/debian-backports squeeze-backports main contrib
# deb http://ftp.psn.ru/debian-backports squeeze-backports main contrib
# deb-src http://ftp.psn.ru/debian-backports squeeze-backports main contrib
# deb http://mirror2.corbina.ru/debian-backports squeeze-backports main contrib
# deb-src http://mirror2.corbina.ru/debian-backports squeeze-backports main contrib
# deb http://mirror.svk.su/debian-backports squeeze-backports main contrib
# deb-src http://mirror.svk.su/debian-backports squeeze-backports main contrib
# deb http://mirror.yandex.ru/debian-backports squeeze-backports main contrib
# deb-src http://mirror.yandex.ru/debian-backports squeeze-backports main contrib

## OFFICIAL SQUEEZE PROPOSED
# deb ftp://ftp.ru.debian.org/debian squeeze-proposed-updates main contrib non-free
# deb-src ftp://ftp.ru.debian.org/debian squeeze-proposed-updates main contrib non-free
# deb http://ftp.ru.debian.org/debian squeeze-proposed-updates main contrib non-free
# deb-src http://ftp.ru.debian.org/debian squeeze-proposed-updates main contrib non-free
# deb http://debian.nsu.ru/debian squeeze-proposed-updates main contrib non-free
# deb-src http://debian.nsu.ru/debian squeeze-proposed-updates main contrib non-free
# deb http://ftp.corbina.net/debian squeeze-proposed-updates main contrib non-free
# deb-src http://ftp.corbina.net/debian squeeze-proposed-updates main contrib non-free
# deb http://ftp.debian.chuvsu.ru/debian squeeze-proposed-updates main contrib non-free
# deb-src http://ftp.debian.chuvsu.ru/debian squeeze-proposed-updates main contrib non-free
# deb http://ftp.psn.ru/debian squeeze-proposed-updates main contrib non-free
# deb-src http://ftp.psn.ru/debian squeeze-proposed-updates main contrib non-free
# deb http://mirror2.corbina.ru/debian squeeze-proposed-updates main contrib non-free
# deb-src http://mirror2.corbina.ru/debian squeeze-proposed-updates main contrib non-free
# deb http://mirror.svk.su/debian squeeze-proposed-updates main contrib non-free
# deb-src http://mirror.svk.su/debian squeeze-proposed-updates main contrib non-free
# deb http://mirror.yandex.ru/debian squeeze-proposed-updates main contrib non-free
# deb-src http://mirror.yandex.ru/debian squeeze-proposed-updates main contrib non-free

## OFFICIAL SQUEEZE UPDATES | Обновления пакетов SQUEEZE (бывший VOLATILE)
# deb ftp://ftp.ru.debian.org/debian squeeze-updates main
# deb-src ftp://ftp.ru.debian.org/debian squeeze-updates main
# deb http://ftp.ru.debian.org/debian squeeze-updates main
# deb-src http://ftp.ru.debian.org/debian squeeze-updates main
# deb http://debian.nsu.ru/debian squeeze-updates main
# deb-src http://debian.nsu.ru/debian squeeze-updates main
# deb http://ftp.corbina.net/debian squeeze-updates main
# deb-src http://ftp.corbina.net/debian squeeze-updates main
# deb http://ftp.debian.chuvsu.ru/debian squeeze-updates main
# deb-src http://ftp.debian.chuvsu.ru/debian squeeze-updates main
# deb http://ftp.psn.ru/debian squeeze-updates main
# deb-src http://ftp.psn.ru/debian squeeze-updates main
# deb http://mirror2.corbina.ru/debian squeeze-updates main
# deb-src http://mirror2.corbina.ru/debian squeeze-updates main
# deb http://mirror.svk.su/debian squeeze-updates main
# deb-src http://mirror.svk.su/debian squeeze-updates main
# deb http://mirror.yandex.ru/debian squeeze-updates main
# deb-src http://mirror.yandex.ru/debian squeeze-updates main

## UNOFFICIAL | Неофициальные версии пакетов от мейнтейнеров
# deb http://unofficial.debian-maintainers.org/ squeeze main contrib non-free restricted
# deb http://unofficial.debian-maintainers.org/ squeeze main contrib non-free restricted
# deb http://unofficial.debian-maintainers.org/ sid main contrib non-free restricted
# deb-src http://unofficial.debian-maintainers.org/ sid main contrib non-free restricted
# deb http://ftp.debian-ports.org/debian/ unstable main

## KDE4 | Для SID (для настройки APT посетите http://qt-kde.debian.net)
# deb http://qt-kde.debian.net/debian experimental-snapshots main
# deb-src http://qt-kde.debian.net/debian experimental-snapshots main

## TRINITY | Форк KDE3
# deb http://ppa.quickbuild.pearsoncomputing.net/trinity/trinity/debian squeeze main
# deb-src http://ppa.quickbuild.pearsoncomputing.net/trinity/trinity/debian squeeze main
# deb http://ppa.quickbuild.pearsoncomputing.net/trinity/trinity-builddeps/debian squeeze main
# deb-src http://ppa.quickbuild.pearsoncomputing.net/trinity/trinity-builddeps/debian squeeze main

## XFCE
# deb http://www.debian-desktop.org/pub/linux/debian/xfce46 lenny xfce460
# deb-src http://www.debian-desktop.org/pub/linux/debian/xfce46 lenny xfce460

## ENLIGHTENMENT DR16, DR17
# deb http://packages.enlightenment.org/debian/ squeeze main extras
# deb http://packages.enlightenment.org/debian/ sid main extras
# deb http://debian.alphagemini.org/ unstable main

## ELIVE | ENLIGHTENMENT DR17 + LiveCD
# deb http://repository.elivecd.org lenny drivers efl elive games main multimedia other ports tests
# deb http://repository.elivecd.org elive drivers efl elive games main ports tests

## DEBIAN MULTIMEDIA
# deb http://www.debian-multimedia.org squeeze main non-free
# deb ftp://ftp.debian-multimedia.org squeeze main non-free
# deb http://www.debian-multimedia.org sid main non-free
# deb ftp://ftp.debian-multimedia.org sid main non-free
# deb-src http://www.debian-multimedia.org sid main
# deb-src ftp://ftp.debian-multimedia.org sid main

## OPERA
# deb http://deb.opera.com/opera/ squeeze non-free
# deb http://deb.opera.com/opera-beta/ squeeze non-free
# deb http://deb.opera.com/opera/ sid non-free
# deb http://deb.opera.com/opera-beta/ sid non-free

## JABBIM
# deb http://repo.palatinus.cz/ stable desktop
# deb http://repo.palatinus.cz/ testing desktop
# deb http://repo.palatinus.cz/ unstable desktop

## QUTIM
# deb http://qutim.org/debian/ stable main
# deb http://qutim.org/debian/ testing main
# deb http://qutim.org/debian/ unstable main

## GAJIM
# deb ftp://ftp.gajim.org/debian stable main
# deb-src ftp://ftp.gajim.org/debian stable main
# deb ftp://ftp.gajim.org/debian unstable main
# deb-src ftp://ftp.gajim.org/debian unstable main

## RSSOWL
# deb http://packages.rssowl.org/debian squeeze main

## GOOGLE
# deb http://dl.google.com/linux/deb/ stable non-free main

## YANDEX
# deb http://repo.yandex.ru/debian squeeze main non-free

## RUSSIAN MAN PAGES | Русские справочные страницы
# deb http://manpages.ylsoftware.com/debian/ all main

## Hadret's DEBIAN PPA
# deb http://hadret.rootnode.net/debian/ unstable main
# deb-src http://hadret.rootnode.net/debian/ unstable main
# deb http://hadret.rootnode.net/debian/ experimental main
# deb-src http://hadret.rootnode.net/debian/ experimental main

## Darth Revan's DEBIAN PPA | Темы иконок, Skype, mrim-prpl, Bimoid и др.
# deb http://repo.sudouser.com/debian/extras/ debian main contrib non-free
# deb http://repo.sudouser.com/debian/mrim-prpl/ debian main contrib non-free
# deb http://repo.sudouser.com/debian/bimoid/ debian main contrib non-free

## FRIKELPLATZ | Новейшие версии популярных пакетов
# deb http://frickelplatz.de/debian sid main contrib non-free


Расположение

/etc/apt/sources.list

среда, 13 июня 2012 г.

Гномья сортировка

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком.
Алгоритм концептуально простой, не требует вложенных циклов. Время работы  O(n²). На практике алгоритм может работать так же быстро, как и сортировка вставками.
Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.

Пример:
int* GnomeSort(int* Array, int SizeArray)
{
    int i=1;
    int j=2;
    int tmp;

    while(i<SizeArray)
    {
        if(Array[i]<Array[i-1])
        {
            i=j;
            j+=1;
        }
        else
        {
            tmp=Array[i-1];
            Array[i-1]=Array[i];
            Array[i]=tmp;
            i=i-1;
            if(0==i)
            {
                i=j;
                j=j+1;
            }
        }
    }
    return Array;
}

Wiki: Гномья сортировка

Сортировка вставками

Сортировка вставками — простой алгоритм сортировки. Этот алгоритм уступает по эффективности более сложным алгоритмом, у него есть ряд преимуществ:
  • эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
  • эффективен на наборах данных, которые уже частично отсортированы;
  • это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
  • может сортировать список по мере его получения;
  • использует O(1) временной памяти, включая стек.
Минусом же является высокая сложность алгоритма: O(n²).

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.

Пример:
int* InsertSort(int* Array, int SizeArray)
{
    int i=0;
    int tmp=0;
    int j=0;

    for(i=1; i<SizeArray; i++)
    {
        tmp=Array[i];
        for(j=i-1; j>=0; j--)
        {
            if(tmp<Array[j])
                break;
            Array[j+1]=Array[j];
            Array[j]=tmp;
        }
    }

    return Array;
}

Wiki: Сортировка вставками

Сортировка перемешиванием

Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.
  • Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
  • Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо. Лучший случай для этой сортировки — отсортированный массив О(n), худший — отсортированный в обратном порядке O(n²).

Пример:
int* ShakerSort(int* Array, int SizeArray)
{
    int i=0;
    int tmp=0;
    int left=0;
    int right=SizeArray-1;

    while(left<right)
    {
        for(i=left; i<right; i++)
        {
            if(Array[i]<Array[i+1])
            {
                tmp=Array[i];
                Array[i]=Array[i+1];
                Array[i+1]=tmp;
                tmp=i;
            }
        }
        right=tmp;
        if(left<=right)
        {
            break;
        }
        else
        {
            for(i=right; i<left; i--)
            {
                if(Array[i-1]<Array[i])
                {
                    tmp=Array[i];
                    Array[i]=Array[i-1];
                    Array[i-1]=tmp;
                    tmp=i;
                }
            }
            left=tmp;
        }
    }
    return Array;
}

Wiki: Шейкерная сортировка

Сортировка пузырьком

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива.

Пример:
int* BubbleSort(int* Array, int SizeArray)
{
    int i=0;
    int j=0;
    int tmp=0;

    for(j=1; j<SizeArray-1; j++)
    {
        for(i=0; i<SizeArray-1; i++)
        {
            if(Array[i]<Array[i+1])
            {
                tmp=Array[i];
                Array[i]=Array[i+1];
                Array[i+1]=tmp;
            }
        }
    }

    return Array;
}

Wiki: Сортировка пузырьком