Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
Сортировка методом выбора на языке Си
В этой статье рассмотрим один из методов сортировки, который называется — метод выбора. Будет приведен алгоритм и его реализация на языке Си.
На первом проходе цикла выбирается минимальный элемент из текущей последовательности и меняется местами с первым элементом последовательности. На следующей итерации цикла поиск минимального элемента осуществляется со второй позиции, после меняется местами найденный минимальный элемент со вторым в списке. Такую процедуру выполняем до конца массива, пока он весь не будет отсортирован.
При сортировке методом выбора среднее число сравнений пропорционально 0,5N², а число перестановок за всё время сортировки пропорционально числу N/2 (N — число элементов в последовательности).
Приведем реализацию алгоритма на языке программирования Си.
Источник: vscode.ru
Сортировка массива пузырьком | Pascal
9 алгоритмов сортировки на VBA
Если вы хотите начать писать макросы на VBA (да и на любом другом языке), то помимо знания самого языка программирования хорошем подспорьем в работе будет знание и умение писать алгоритмы. Как и в любом другом деле для этого потребуется практика, много практики. В этой статье мы разберем алгоритмы сортировки, знание их спрашивают практически на любом собеседование на должность программиста, да и студентов часто мучают ими. Изучите их, это хороший опыт и практика для начинающих!
О чем пойдет речь
В статье разберем 9 видов сортировок, рассмотрим суть этих алгоритмов. Скорости, сложность алгоритмов и практическое их применение оставим за скобками. Задача статьи показать, что одну и туже задачу можно решать различными способами, показать практическое применение языка VBA и помочь начинающим в его освоении.
Скачать файлик можно по кнопке выше. Поехали!
Подготовительный этап
Перед тем как начинать писать алгоритмы немного подготовимся. Создадим общую константу n для хранения размера массивов. Вставим на лист диаграмму, чтобы отслеживать как все работает. В коде объявим объект нашей диаграммы, на которой будем просматривать ход процесса сортировки. Чтобы не дублировать код в каждом алгоритме сортировки мы будем использовать процедуру инициализации Init().
Option Explicit Const n As Long = 25 Dim Chrt As ChartObject ‘************************************************************** ‘ Sub : Init ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Инициализация ‘************************************************************** Sub Init() Set Chrt = ActiveSheet.ChartObjects(1) End Sub
Чтобы наша диаграмма с результатом не подвисала и обновлялась напишем такую функцию.
‘************************************************************** ‘ Sub : ChartRefresh ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Обновление диаграммы ‘************************************************************** Sub ChartRefresh() Chrt.Activate Application.Calculate DoEvents End Sub
В качестве массивов будем использовать диапазон ячеек A1:Y1. Напишем еще одну коротенькую процедуру для перемешивания этого массива, точнее заполнения его числами от 1 до 25 в случайном порядке.
‘************************************************************** ‘ Sub : RandomArray ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Перемешивание массива ‘************************************************************** Sub RandomArray() Dim coll As New Collection Dim rndVal As Long Randomize Do While coll.count < n rndVal = CLng((n — 1) * Rnd) + 1 On Error Resume Next coll.Add rndVal, CStr(rndVal) If Err.Number = 0 Then Cells(1, coll.count) = rndVal Err.Clear Loop End Sub
Теперь все готово, давайте писать алгоритмы сортировки.
Сортировка пузырьком
Пузырьковая сортировка (или сортировка простыми обменами) пожалуй самый неэффективный алгоритм сортировки и в тоже время пожалуй самый известный.
Суть алгоритма в прохождении в цикле по всем элементами массива и в попарном сравнении текущего элемента со следующим. Если текущий элемент массива больше (для сортировки по возрастанию и меньше для сортировки по убыванию) чем следующий, то эти два элемента меняются друг с другом местами. Ход алгоритма смотрите на следующей диаграмме.
Вот код сортировки данным алгоритмом на VBA. Еще стоит обратить внимание на переменную Flag она служит индикатором того, что массив досрочно отсортирован и можно заранее выйти из цикла и сократить вычислительные ресурсы.
‘************************************************************** ‘ Sub : BubbleSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Сортировка простыми обменами, сортировка пузырьком ‘************************************************************** Sub BubbleSort() Dim i As Long Dim j As Long Dim Flag As Boolean Init For i = 1 To n — 1 Flag = False For j = 1 To n — i If Cells(1, j) > Cells(1, j + 1) Then Swap Cells(1, j), Cells(1, j + 1): Flag = True Next If Not Flag Then Exit For Next End Sub
Далее описана процедура Swap для перестановки ячеек местами. После перестановки ячеек вызывается процедура ChartRefresh обновления диаграммы.
‘************************************************************** ‘ Sub : Swap ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Перестановка ячеек ‘************************************************************** Sub Swap(A As Range, B As Range) Dim C As String C = A A = B B = C ChartRefresh End Sub
Сортировка перемешиванием
Этот алгоритм является разновидностью пузырьковой сортировки. Также этот алгоритм называют Шейкерной сортировкой или двунаправленной.
Основное отличие от обычной сортировки пузырьком в том, что массив сначала просматривается слева направо и максимальный элемент перемещается вправа, а после мы проходим по массиву справа налево (от последнего отсортированного элемента) и наименьший элемент перемещается влево. Вот на графике отчетливо это видно.
Алгоритм немного больше, но по сложности аналогичный, вот его код на VBA.
Sub ShakerSort() Dim left As Long Dim right As Long Dim count As Long Dim i As Long Init left = 1 right = n count = 0 Do While left < right For i = left To right — 1 count = count + 1 If Cells(1, i) >Cells(1, i + 1) Then Swap Cells(1, i), Cells(1, i + 1) Next right = right — 1 For i = right To left + 1 Step -1 count = count + 1 If Cells(1, i — 1) > Cells(1, i) Then Swap Cells(1, i — 1), Cells(1, i) Next left = left + 1 Loop End Sub
Сортировка выбором
Тоже достаточно простой алгоритм сортировки. Суть его заключается в поиске минимального значения (максимального для сортировки по убыванию) и обмене найденного значения с первым неотсортированным значением. Т.е. нашли первое минимальное значение, поменяли его с первым элементом, нашли второе минимальное — поменяли со вторым элементом. График получается следующий:
‘************************************************************** ‘ Sub : SelectionSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Сортировка выбором ‘************************************************************** Sub SelectionSort() Dim i As Long Dim j As Long Dim iMin As Long Init For i = 1 To n iMin = i For j = i To n If Cells(1, j) < Cells(1, iMin) Then iMin = j Next If iMin <>i Then Swap Cells(1, i), Cells(1, iMin) Next End Sub
Объединение сортировки пузырьком и сортировки выбором
Можно ускорить алгоритм сортировки пузырьком объединив его с алгоритмом сортировки выбором. Для этого нужно определять минимальный элемент во внутреннем цикле и после каждого прохода по списку обменивать найденный минимальный элемент с первым неотсортированным слева. Таким образом, мы сокращаем в 2 раза число перестановок, но при этом увеличиваем в 2 раза число сравнений.
Код отличается только 2 строчками:
‘************************************************************** ‘ Sub : BubbleSortWhithSelection ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Объединение сортировки пузырьком и сортировки выбором ‘************************************************************** Sub BubbleSortWhithSelection() Dim i As Long Dim j As Long Dim iMin As Long Init For i = 1 To n — 1 iMin = i For j = i To n — i If Cells(1, j) > Cells(1, j + 1) Then Swap Cells(1, j), Cells(1, j + 1) If Cells(1, j) < Cells(1, iMin) Then iMin = j Next If iMin <>i Then Swap Cells(1, i), Cells(1, iMin) Next End Sub
Сортировка вставками
Вот определение сортировки с википедии
Это алгоритм, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
Другими словами мы во внешнем цикле проходим по всем элементам массива, а во внутреннем цикле сравниваем правый элемент с уже отсортированными элементами слева и перемещаем его при необходимости. Вот как это выглядит визуально:
Код тоже думаю окажется для вас достаточно простым.
‘************************************************************** ‘ Sub : InsertionSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Сортировка вставками ‘************************************************************** Sub InsertionSort() Dim i As Long Dim j As Long Init For i = 2 To n j = i Do While j > 1 If Cells(1, j) > Cells(1, j — 1) Then Exit Do Swap Cells(1, j), Cells(1, j — 1) j = j — 1 Loop Next End Sub
Гномья сортировка
Визуально отличия от сортировки вставками нет, однако в код совершенно другой так как нет никаких вложенных циклов. Алгоритм в цикле проходит по всем элементам, сравнивая текущий элемент с предыдущим. Если элементы стоят верно переходит к следующему, если нет, меняет их местами и переходит к предыдущему элементу.
‘************************************************************** ‘ Sub : GnomeSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Гномья сортировка ‘************************************************************** Sub GnomeSort() Dim i As Long Dim j As Long Init i = 2 j = 2 Do While i < n + 1 If Cells(1, i — 1) < Cells(1, i) Then i = j j = j + 1 Else Swap Cells(1, i — 1), Cells(1, i) i = i — 1 If i = 1 Then i = j j = j + 1 End If End If Loop End Sub
Сортировка слиянием
Простые алгоритмы сортировки мы разобрали, теперь давайте рассмотрим более сложные виды сортировок. Хотя главное понять суть алгоритма и его реализация уже не будет казаться сложной.
Суть алгоритма сортировки слиянием состоит в том, чтобы разбить исходный массив на более мелкие массивы, отсортировать каждый по отдельности, а после объединить результаты.
Для этого первоначальный массив разбивается на 2 части пополам (ну или почти пополам если количество нечетное), каждая половинка разбивается еще пополам и так до тех пор, пока мы не получим массивы состоящие из 1 элемента. После прохождения процедуры разбивки на части, слияние каждой части и ее сортировка. Например, массив содержит числа 5 2 1 3 4.
Разбиваем его на две части: 5,2,1 и 3,4 . Первую часть 5,2,1 разбиваем еще на две части 5,2 и 1. Далее 5,2 еще на две части 5 и 2. А теперь идем обратно, сортируем и сливаем массивы. Получается 2,5 и 1, объединим дальше — 1,2,5 , последняя итерация отсортирует исходный массив 1 2 3 4 5. При слиянии учитывается тот факт, что массивы уже отсортированы по отдельности, поэтому объединение проходит быстрее.
Вот визуализация работы алгоритма:
Код состоит из двух частей. Первая MergeSort — рекурсивная функция разделения массивов, т.е. эта функция запускает саму себя. Это происходит до тех пор, пока размер массива больше 1, иначе запускается функция MergeSort для каждой из частей.
После того как массивы разобьются запускается функция Merge(left, right), которая сортирует и объединяет массив обратно.
‘************************************************************** ‘ Function : MergeSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Рекурсивная функция сортировки слиянием ‘************************************************************** Function MergeSort(rng As Range) Dim left As Range Dim right As Range Dim result As Range Dim i As Long Dim middle As Long If rng.Cells.count = 1 Then Set MergeSort = rng Exit Function Else middle = CLng(rng.Cells.count / 2) ‘ Разделяем диапазон на 2 части Set left = Range(rng.Columns(1), rng.Columns(middle)) Set right = Range(rng.Columns(middle + 1), rng.Columns(rng.Columns.count)) ‘ Рекурсивно проходим этой же функцией по каждой части left = MergeSort(left) right = MergeSort(right) ‘ Объединяем части обратно в единое целое MergeSort = Merge(left, right) End If End Function
В качестве сортировки и объединения можно использовать различные алгоритмы, например такой. Если кто-то предложит более изящное решение — пишите в комментариях.
‘************************************************************** ‘ Function : Merge ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Функция сортирует и объединяет диапазон ‘************************************************************** Function Merge(left As Range, right As Range) As Range Dim i As Long Dim count As Long Dim result Dim sizeLeft As Long Dim sizeRight As Long Dim FirstRng As Range Set FirstRng = left.Cells(1, 1) sizeLeft = left.count sizeRight = right.count ReDim result(1 To sizeLeft + sizeRight) i = 1 Do While sizeLeft > 0 And sizeRight > 0 If left.Columns(1) 1 Then Set left = left.Offset(, 1).Resize(, left.Columns.count — 1) sizeLeft = sizeLeft — 1 Else result(i) = right.Columns(1) If sizeRight > 1 Then Set right = right.Offset(, 1).Resize(, right.Columns.count — 1) sizeRight = sizeRight — 1 End If i = i + 1 Loop Do While sizeLeft > 0 result(i) = left.Columns(1) If sizeLeft > 1 Then Set left = left.Offset(, 1).Resize(, left.Columns.count — 1) sizeLeft = sizeLeft — 1 i = i + 1 Loop Do While sizeRight > 0 result(i) = right.Columns(1) If sizeRight > 1 Then Set right = right.Offset(, 1).Resize(, right.Columns.count — 1) sizeRight = sizeRight — 1 i = i + 1 Loop For i = 1 To UBound(result) FirstRng.Offset(, i — 1) = result(i) ChartRefresh Next Set Merge = FirstRng.Resize(, UBound(result)) End Function
Так как функция у нас рекурсивная, то первый ее запуск необходимо сделать из отдельной процедуры, вот так:
‘************************************************************** ‘ Sub : StartMergeSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Запуск сортировки слиянием ‘************************************************************** Sub StartMergeSort() Init MergeSort Range(Cells(1, 1), Cells(1, n)) End Sub
Быстрая сортировка
Алгоритм быстрой сортировки — один из самых быстрых и эффективных и часто используется в практике. При этом он достаточно простой.
Суть алгоритма в следующем:
- Выбрать из массива опорный элемент. Например, взять элемент в середине массива (в целом это может быть любой из элементов).
- Сравнить остальные элементы массива с выбранным опорным элементов и разбить массив на 2 части:
- элементы, которые меньше или равны опорному элементу;
- элементы, которые больше опорного.
- Далее пункты 1 и 2 повторяются рекурсивно для каждой части массива, до тех пор пока размер части состоит из более чем 1 элемента.
На визуализации к сожалению что-то разглядеть сложно. Алгоритм достаточно быстро отрабатывает:
Вот код данного алгоритма на VBA.
‘************************************************************** ‘ Sub : QuickSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Рекурсивная функция для быстрой сортировки ‘************************************************************** Sub QuickSort(rng As Range, lo, hi) Dim p As Long If lo < hi Then p = Partition(rng, lo, hi) Call QuickSort(rng, lo, p) Call QuickSort(rng, p + 1, hi) End If End Sub
‘************************************************************** ‘ Function : Partition ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Выбор опорного элемента для быстрой сортировки ‘************************************************************** Function Partition(rng As Range, lo, hi) Dim i As Long Dim j As Long Dim pivot i = lo j = hi pivot = (rng.Cells(1, lo) + rng.Cells(1, hi)) / 2 Do Do While rng.Cells(1, i) < pivot i = i + 1 Loop Do While rng.Cells(1, j) >pivot j = j — 1 Loop If i >= j Then Partition = j Exit Function End If Swap rng.Cells(1, i), rng.Cells(1, j) Loop End Function
Запуск рекурсивной функции быстрой сортировки запустим из отдельного метода.
‘************************************************************** ‘ Sub : StartQuickSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Запуск быстрой сортировки ‘************************************************************** Sub StartQuickSort() Init QuickSort Range(Cells(1, 1), Cells(1, n)), 1, n End Sub
Пирамидальная сортировка
Пирамидальная сортировка или как еще ее называют «Сортировка кучей» использует в своем алгоритме двоичное дерево.
Это такое дерево, для которого выполнены следующие условия:
- Значение в любой вершине не меньше, чем значения её потомков.
- Длина веток дерева не отличается друг от друга более чем на 1 слой.
- Последний слой заполняется слева направо без «дырок».
Вот пример дерева, которое можно найти на википедии:
Это дерево можно представить в виде следующего массива, где для любого элемента A[i] потомками являются элементы A[2i] и A[2i+1].
Т.е. для каждого элемента кучи справедливы следующие условия: A[i] >= A[2i] и A[i] >= A[2i+1].
Алгоритм пирамидальной сортировки состоит из следующих шагов:
- Построение массива в виде двоичного дерева.
- Исключение корня дерева (максимального значения массива) из массива и перенос его в конец последовательности.
- После исключения корня дерево перестраивается и его корень опять отсекается и переносится в конец.
- Так происходит до тех пор, пока вся последовательность не отсортируется.
Вот визуальное отображение выполнения этого алгоритма:
Ниже код пирамидальной сортировки на VBA. Который формирует двоичную кучу и корень этой кучи переносит в конец последовательности. Так происходит n раз.
‘************************************************************** ‘ Sub : HeapSort ‘ Author : Zheltov Alexey ‘ Date : 24.12.2020 ‘ Purpose : Пирамидальная сортировка ‘************************************************************** Sub HeapSort() Dim i As Long Dim j As Long Init For i = 1 To n For j = CInt((n + 1) / 2) — CInt(i / 2) To 1 Step -1 If 2 * j + 1 Cells(1, 2 * j + 1) Then If Cells(1, j) < Cells(1, 2 * j) Then Swap Cells(1, j), Cells(1, 2 * j) End If Else If Cells(1, j) < Cells(1, 2 * j + 1) Then Swap Cells(1, j), Cells(1, 2 * j + 1) End If End If Else If 2 * j
Источник: micro-solution.ru
Сортировка массивов
В продолжении темы работы с массивами поговорим о типичной задаче – их сортировке. Для ее выполнения в PHP существует множество функций, их подробное описание можно посмотреть на php.net, рассмотрим некоторые примеры.
Сортировка массива по ключу
ksort() и krsort() – сортирует массив по ключу.
$array = array( 3 => ‘яблоко’, 1 => ‘апельсин’, 5 => ‘виноград’ ); // По возрастанию: ksort($array); print_r($array); // По убыванию: krsort($array); print_r($array);
Результат:
Array ( [1] => апельсин [3] => яблоко [5] => виноград ) Array ( [5] => виноград [3] => яблоко [1] => апельсин )
Сортировка массива по значению
Функции sort() и rsort() сортирует массив по значению, при этом не сохраняя ключи.
$array = array( 3 => ‘яблоко’, 1 => ‘апельсин’, 5 => ‘виноград’ ); // По возрастанию: sort($array); print_r($array); // По убыванию: rsort($array); print_r($array);
Результат:
Array ( [0] => апельсин [1] => виноград [2] => яблоко ) Array ( [0] => яблоко [1] => виноград [2] => апельсин )
Чтобы сохранить ключи применяется функции asort() и arsort() .
$array = array( 3 => ‘яблоко’, 1 => ‘апельсин’, 5 => ‘виноград’ ); // По возрастанию: asort($array); print_r($array); // По убыванию: arsort($array); print_r($array);
Результат:
Array ( [1] => апельсин [5] => виноград [3] => яблоко ) Array ( [3] => яблоко [5] => виноград [1] => апельсин )
Естественная сортировка
Выше приведенные функции по умолчанию используют алгоритм Quicksort (быстрая сортировка). Чтобы изменить алгоритм нужно вторым аргументом указать флаг:
| SORT_REGULAR | Обычное сравнение элементов (без изменения типов) |
| SORT_NUMERIC | Числовое сравнение элементов |
| SORT_STRING | Строковое сравнение элементов |
| SORT_LOCALE_STRING | Сравнивает элементы как строки с учетом текущей локали. |
| SORT_NATURAL | Также как natsort() |
| SORT_FLAG_CASE | Может быть объединен с SORT_STRING или SORT_NATURAL для сортировки строк без учета регистра. |
Привычную для человека сортировку делают функции natsort() , natcasesort() или флаг SORT_NATURAL .
natcasesort() сортирует массив без учета регистра символов.
Разницу можно увидеть в примере:
$array = array(-1, 0, 10, ‘текст’, ‘a’, ‘b’); // Quicksort: sort($array); print_r($array); // Natural order: natsort($array); print_r($array);
Результат:
Array ( [0] => -1 [1] => a [2] => b [3] => 0 [4] => текст [5] => 10 ) Array ( [0] => -1 [1] => 0 [2] => 10 [4] => a [5] => b [3] => текст )
У natsort() нет возможности изменить направление сортировки, поэтому можно применить функцию array_reverse() .
natsort($array); $array = array_reverse($array); print_r($array);
Результат:
Array ( [0] => текст [1] => b [2] => a [3] => 10 [4] => 0 [5] => -1 )
Сортировка многомерных массивов
array_multisort() сортирует многомерные массивы по значению, также может отсортировать сразу несколько массивов.
$array = array( array(20, 222, 2, 22), array(10, 111, 1, 11), ); array_multisort($array); print_r($array);
Результат:
Array ( [0] => Array( [0] => 10 [1] => 111 [2] => 1 [3] => 11 ) [1] => Array( [0] => 20 [1] => 222 [2] => 2 [3] => 22 ) )
Чтобы изменить направление сортировки вторым аргументом функции указывается SORT_ASC или SORT_DESC .
array_multisort($array, SORT_DESC); print_r($array);
Сортировка многомерного массива по значению одного ключа
Есть несколько вариантов, первый – uasort() , сортирует массив, используя пользовательскую функцию для сравнения элементов и сохранением ключей.
В примере сортировка идет по ключу « count ».
$array = array( array( ‘sku’ => ‘645908-463’, ‘count’ => ‘1’ ), array( ‘sku’ => ‘64590644’, ‘count’ => ’20’ ), array( ‘sku’ => ‘7543’, ‘count’ => ‘2’ ) ); // По возрастанию: function cmp_function($a, $b) < return ($a[‘count’] >$b[‘count’]); > uasort($array, ‘cmp_function’); print_r($array); // По убыванию: function cmp_function_desc($a, $b) < return ($a[‘count’] < $b[‘count’]); >uasort($array, ‘cmp_function_desc’); print_r($array);
Результат:
Array ( [0] => Array( [sku] => 645908-463 [count] => 1 ) [2] => Array( [sku] => 7543 [count] => 2 ) [1] => Array( [sku] => 64590644 [count] => 20 ) ) Array ( [1] => Array( [sku] => 64590644 [count] => 20 ) [2] => Array( [sku] => 7543 [count] => 2 ) [0] => Array( [sku] => 645908-463 [count] => 1 ) )
Второй вариант на основе функции array_multisort() :
function array_multisort_value() < $args = func_get_args(); $data = array_shift($args); foreach ($args as $n =>$field) < if (is_string($field)) < $tmp = array(); foreach ($data as $key =>$row) < $tmp[$key] = $row[$field]; >$args[$n] = $tmp; > > $args[] = call_user_func_array(‘array_multisort’, $args); return array_pop($args); > $array = array( array( ‘sku’ => ‘645908-463’, ‘count’ => ‘1’ ), array( ‘sku’ => ‘64590644’, ‘count’ => ’20’ ), array( ‘sku’ => ‘7543’, ‘count’ => ‘2’ ) ); $array = array_multisort_value($array, ‘count’, SORT_DESC); print_r($array);
Перемешать массив
Функция shuffle() перемешивает массив в случайном порядке, не сохроняя ключи.
$array = array( 1 => ‘яблоко’, 2 => ‘апельсин’, 3 => ‘виноград’ ); shuffle($array); print_r($array); shuffle($array); print_r($array);
Результат:
Array ( [0] => виноград [1] => яблоко [2] => апельсин ) Array ( [0] => виноград [1] => апельсин [2] => яблоко )
Источник: snipp.ru