Сравнение сортировок обменами



    Сферические алгоритмы в вакууме — это прекрасно. Однако давайте спустимся с небес на грешную землю и посмотрим как вся эта теоретическая красота покажет себя на практике.

    Разбор очередного класса сортировок будет завершаться тестами для сортировок класса. Сегодня мы прогоним (не в смысле вышвырнем вон, а в смысле обкатаем на тестах) сортировки обменами. Сортировки других классов будем прогонять потом.

    В сегодняшнем забеге участвуют:

    Слабейшая группа


    Эти алгоритмы ни на что не претендуют ввиду удручающей временной сложности. Тестируем их чисто «для справки».

    Придурковатая сортировка
    Вялая сортировка
    Тупая сортиртировка

    Скорее даже интересно не насколько они хороши, а насколько плохи в деле, и кто из них хуже всех.

    Основная группа


    Тут собрались обменные сортировочки а-ля O(n2). Гномья сортировка (и её оптимизация) + всевозможные вариации пузырьковой сортировки.

    Гномья сортировка
    Гномья сортировка (оптимизированная)
    Пузырьковая сортировка
    Коктейльная сортировка
    Чётно-нечётная сортировка

    Это самая интересная часть сегодняшних замеров. Именно среди представителей основной группы ожидается наиболее упорная борьба.

    Сильнейшая группа


    Одной из разновидностей пузырька — сортировке расчёской — удалось преодолеть барьер O(n2) и выйти по времени на заслуживающие уважение O(n log n). Так что в нашем соревновании у быстрой сортировки есть достойный соперник. Кроме того, испытаем недавно изобретённую k-sort, являющуюся разновидностью quick sort.

    Сортировка расчёской
    Быстрая сортировка
    K-сортировка

    Сильнейших, кстати, сравним не только друг с другом. Им на некоторых наборах данных основная группа составит серьёзную конкуренцию.

    Исходный код


    Сортировки обменами на Python
    def stooge_rec(data, i = 0, j = None):
    	if j is None:
    		j = len(data) - 1
    	if data[j] < data[i]:
    		data[i], data[j] = data[j], data[i]
    	if j - i > 1:
    		t = (j - i + 1) // 3
    		stooge_rec(data, i, j - t)
    		stooge_rec(data, i + t, j)
    		stooge_rec(data, i, j - t)
    	return data
    				
    def stooge(data):
    	return stooge_rec(data, 0, len(data) - 1)
    
    def slow_rec(data, i, j):
    	if i >= j:
    		return data
    	m = (i + j) // 2
    	slow_rec(data, i, m)
    	slow_rec(data, m + 1, j)
    	if data[m] > data[j]:
    		data[m], data[j] = data[j], data[m]
    	slow_rec(data, i, j - 1)
    	return data
    	
    def slow(data):
    	return slow_rec(data, 0, len(data) - 1)		
    	
    	
    def stupid(data):
    	i, size = 1, len(data)
    	while i < size:
    		if data[i - 1] > data[i]:
    			data[i - 1], data[i] = data[i], data[i - 1]
    			i = 1
    		else:
    			i += 1
    	return data
    
    def gnome(data):
    	i, size = 1, len(data)
    	while i < size:
    		if data[i - 1] <= data[i]:
    			i += 1
    		else:
    			data[i - 1], data[i] = data[i], data[i - 1]	
    			if i > 1:
    				i -= 1
    	return data
    	
    def gnome_opt(data):
    	i, j, size = 1, 2, len(data)
    	while i < size:
    		if data[i - 1] <= data[i]:
    			i, j = j, j + 1
    		else:
    			data[i - 1], data[i] = data[i], data[i - 1]
    			i -= 1
    			if i == 0:
    				i, j = j, j + 1
    	return data
    
    def bubble(data):
    	changed = True
    	while changed:
    		changed = False
    		for i in range(len(data) - 1):
    			if data[i] > data[i+1]:
    				data[i], data[i+1] = data[i+1], data[i]
    				changed = True
    	return data
    	
    def shaker(data):	
    	up = range(len(data) - 1)		
    	while True:
    		for indices in (up, reversed(up)):
    			swapped = False
    			for i in indices:
    				if data[i] > data[i+1]:  
    					data[i], data[i+1] =  data[i+1], data[i]
    					swapped = True
    			if not swapped:
    				return data
    	
    def odd_even(data):
    	n = len(data)
    	isSorted = 0
    	while isSorted == 0:
    		isSorted = 1
    		for i in range(1, n - 1, 2):
    			if data[i] > data[i + 1]:
    				data[i], data[i + 1] = data[i + 1], data[i]
    				isSorted = 0
    				 
    		for i in range(0, n - 1, 2):
    			if data[i] > data[i + 1]:
    				data[i], data[i + 1] = data[i + 1], data[i]
    				isSorted = 0
    	return data
    	
    def comb(data):
    	gap = len(data)
    	swaps = True
    	while gap > 1 or swaps:
    		gap = max(1, int(gap / 1.25))  # minimum gap is 1
    		swaps = False
    		for i in range(len(data) - gap):
    			j = i + gap
    			if data[i] > data[j]:
    				data[i], data[j] = data[j], data[i]
    				swaps = True
    	return data
    
    def quick(data):
    	less = []
    	pivotList = []
    	more = []
    	if len(data) <= 1:
    		return data
    	else:
    		pivot = data[0]
    		for i in data:
    			if i < pivot:
    				less.append(i)
    			elif i > pivot:
    				more.append(i)
    			else:
    				pivotList.append(i)
    		less = quick(less)
    		more = quick(more)
    		return less + pivotList + more
    			
    def k(data):
    	return k_rec(data, 0, len(data) - 1)
    	
    def k_rec(data, left, right):
    	key = data[left]
    	i = left
    	j = right + 1
    	k = left + 1
    	p = left + 1
    	temp = False
    	while j - i >= 2:
    		if key <= data[p]:
    			if p != j and j != right + 1:
    				data[j] = data[p]
    			elif j == right + 1:
    				temp = data[p]
    			j -= 1
    			p = j
    		else:
    			data[i] = data[p]
    			i += 1
    			k += 1
    			p = k
    	data[i] = key
    	if temp:
    		data[i + 1] = temp
    	if left < i - 1:
    		k_rec(data, left, i - 1)
    	if right > i + 1:		
    		k_rec(data, i + 1, right)
    	return data

    Сортировки обменами на PHP
    	//Придурковатая	
    	function StoogeSort(&$arr, $i, $j) {
    		if($arr[$j] < $arr[$i]) list($arr[$j], $arr[$i]) = array($arr[$i], $arr[$j]);
    		if(($j - $i) > 1) {
    			$t = ($j - $i + 1) / 3;
    			StoogeSort($arr, $i, $j - $t);
    			StoogeSort($arr, $i + $t, $j);
    			StoogeSort($arr, $i, $j - $t);
    		}
    		return $arr;
    	}
    	
    	//Вялая
    	function SlowSort(&$arr, $i, $j) {
    		if($i >= $j) return $arr;
    		$m = ($i + $j) / 2;
    		SlowSort($arr, $i, $m);
    		SlowSort($arr, $m + 1, $j);
    		if($arr[$m] > $arr[$j]) list($arr[$m], $arr[$j]) = array($arr[$j], $arr[$m]);
    		SlowSort($arr, $i, $j - 1);
    		return $arr;
    	}
    	
    	//Туповатая
    	function StupidSort($arr) {
    		$i = 1; $size = count($arr);
    		while($i < $size) {
    			if($arr[$i - 1] <= $arr[$i]){
    				++$i;
    			} else {
    				list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]);
    				$i = 1;
    			}
    		}
    		return $arr;
    	}
    	
    	//Гном
    	function GnomeSort($arr) {
    		$i = 1; $size = count($arr);
    		while($i < $size) {
    			if($arr[$i - 1] <= $arr[$i]){
    				++$i;
    			} else {
    				list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]);
    				if($i > 1) --$i;
    			}
    		}
    		return $arr;
    	}
    	
    	//Гном (оптимизированный)
    	function GnomeSort_opt($arr) {
    		$i = 1; $j = 2; $size = count($arr);
    		while($i < $size) {
    			if($arr[$i - 1] <= $arr[$i]){
    				$i = $j;
    				++$j;
    			} else {
    				list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]);
    				if(--$i == 0){
    					$i = $j;
    					$j++;
    				}
    			}
    		}
    		return $arr;
    	}
    	
    	//Пузырьки
    	function BubbleSort($arr) {
    		$c = count($arr) - 1;
    		do {
    			$swapped = false;
    			for ($i = 0; $i < $c; ++$i) {
    				if ($arr[$i] > $arr[$i + 1]) {
    					list($arr[$i + 1], $arr[$i]) = array($arr[$i], $arr[$i + 1]);
    					$swapped = true;
    				}
    			}
    		} while($swapped);
    		return $arr;
    	}
    	
    	//Шейкер
    	function ShakerSort($arr){
    		do{
    			$swapped = false;
    			for($i = 0; $i < count($arr); $i++){
    				if(isset($arr[$i + 1])) {
    					if($arr[$i] > $arr[$i+1]) {
    						list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]);
    						$swapped = true;
    					}
    				}			
    			} 
    			if ($swapped == false) break; 
    			$swapped = false;
    			for($i = count($arr) - 1; $i >= 0; $i--){
    				if(isset($arr[$i - 1])){
    					if($arr[$i] < $arr[$i - 1]) {
    						list($arr[$i], $arr[$i - 1]) = array($arr[$i - 1], $arr[$i]);
    						$swapped = true;
    					}
    				}
    			}
    		} while($swapped); 
    		return $arr;
    	}
    	
    	//Чёт-нечет
    	function OddEvenSort($arr){
    		$n = count($arr); 
    		$sorted = false;
    		while(!$sorted) {
    			$sorted = true;
    			for($i = 1; $i < $n - 2; $i += 2) {
    				if($arr[$i] > $arr[$i + 1]) {
    					list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]);
    					$sorted = false;
    				}				
    			}
    			for($i = 0; $i < $n - 1; $i += 2) {
    				if($arr[$i] > $arr[$i + 1]) {
    					list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]);
    					$sorted = false;
    				}				
    			}			
    		}		
    	}
    	
    	//Расчёска
    	function CombSort($arr){
    		$gap = count($arr);
    		$swap = true;
    		while($gap > 1 || $swap){
    			if($gap > 1) $gap /= 1.25;
    			$swap = false;
    			$i = 0;
    			while($i + $gap < count($arr)){
    				if($arr[$i] > $arr[$i + $gap]){
    					list($arr[$i], $arr[$i + $gap]) = array($arr[$i + $gap], $arr[$i]);
    					$swap = true;
    				}
    				++$i;
    			}
    		}
    		return $arr;
    	} 
    
    	//Быстрая
    	function QuickSort($arr) {
    		$loe = $gt = array();
    		if(count($arr) < 2) {
    			return $arr;
    		}
    		$pivot_key = key($arr);
    		$pivot = array_shift($arr);
    		foreach($arr as $val){
    			if($val <= $pivot){
    				$loe[] = $val;
    			}elseif ($val > $pivot){
    				$gt[] = $val;
    			}
    		}
    		return array_merge(QuickSort($loe), array($pivot_key => $pivot), QuickSort($gt));
    	}
    	
    	//k-сортировка
    	function K_Sort($arr) {
    		K_Sort_rec($arr, 0, count($arr) - 1);
    		return $arr;
    	}
    	
    	function K_Sort_rec(&$arr, $left, $right) {
    		$key = $arr[$left];
    		$i = $left;
    		$j = $right + 1;
    		$k = $p = $left + 1;
    		$temp = false;
    		while($j - $i >= 2) {
    			if($key <= $arr[$p]) {
    				if(($p != $j) && ($j != ($right + 1))) {
    					$arr[$j] = $arr[$p];
    				} elseif($j == ($right + 1)) {
    					$temp = $arr[$p];
    				}
    				--$j;
    				$p = $j;
    			} else {
    				$arr[$i] = $arr[$p];
    				++$i;
    				++$k;
    				$p = $k;
    			}
    		}
    		$arr[$i] = $key;
    		if($temp) $arr[$i + 1] = $temp;
    		if($left < ($i - 1)) K_Sort_rec($arr, $left, $i - 1);
    		if($right > ($i + 1)) K_Sort_rec($arr, $i + 1, $right);
    	}

    Время


    Время везде измеряется в секундах с точностью до микросекунд.

    Если алгоритму скармливается сразу пачка массивов (из десяти, ста или даже миллиона штук), то указано общее время.

    Железо — мой верный старенький ноутбук, знававший лучшие времена. Так что, вполне возможно, у Вас всё будет работать гораздо быстрее.

    Худшие из худших


    Сразу разберёмся с аутсайдерами. Для них приготовлены массивы на 40 / 50 / 60 элементов, содержащие случайные числа от 0 до 9.
    type=random, unique=False, min=0, max=9, count=1
    size
    40 50 60
    Python PHP Python PHP Python PHP
    0.004 0.001 0.005 0.003 0.007 0.004
    0.007 0.009 0.018 0.009 0.018 0.023
    0.02 8.26647 0.053 20.8722 0.12901 45.9786

    Туповатая сортировка на порядок быстрее чем придурковатая, а придурковатая на порядок быстрее чем вялая. Больше тут нечего смотреть.

    Середнячки


    Чтобы проверить середнячков, сгенерированы пачки из ста массивов по 100 элементов каждом (уникальные числа от 100 до 999), а также пачки из десяти массивов по 1000 элементов в каждом (уникальные числа от 1000 до 9999).

    Подготовлены рандомные массивы, почти отсортированные массивы и реверсно упорядоченные массивы.

    Середнячки: Рандом


    type=random, unique=True
    size(от min до max) × count
    100(от 100 до 999) × 100 1000(от 1000 до 9999) × 10
    Python PHP Python PHP
    0.14101 0.18901 1.59109 1.7251
    0.20601 0.22301 2.33013 2.09712
    0.15301 0.22901 1.6711 2.23613
    0.21601 0.26402 2.55515 2.73116
    0.16701 0.33402 1.7251 3.13218

    Примерно одинаковые результаты у всех. Реализации на Питоне работают чуть быстрее чем на PHP.

    Середнячки: Почти отсортировано


    type=almost, unique=True
    size(от min до max) × count
    100(от 100 до 999) × 100 1000(от 1000 до 9999) × 10
    Python PHP Python PHP
    0.009 0.005 0.009 0.005
    0.009 0.014 0.01 0.014
    0.01 0.01 0.011 0.008
    0.011 0.008 0.013 0.008
    0.011 0.017 0.013 0.017

    Тоже одинаковые результаты у всех, плюс-минус. Из интересного: частичная упорядоченность данных в десятки раз улучшает показатели всех алгоритмов.

    Середнячки: Реверс


    type=reverse, unique=True
    size(от min до max) × count
    100(от 100 до 999) × 100 1000(от 1000 до 9999) × 10
    Python PHP Python PHP
    0.26801 0.35902 3.10018 3.4292
    0.39602 0.45303 4.49726 4.19524
    0.22701 0.38402 2.48114 3.64421
    0.30202 0.42603 3.34419 4.17524
    0.30402 0.64404 3.36519 6.22036

    Тут интересный вывод — обратная упорядоченность не так уж сильно влияет на скорость, которая упала всего в 2 раза по сравнению с рандомом.

    Середнячки: Бинарник


    type=random, unique=False, min=0, max=1
    size × count
    100 × 100 1000 × 10
    Python PHP Python PHP
    0.073 0.094 0.81105 0.86905
    0.10401 0.11301 1.16307 1.06606
    0.08801 0.12901 0.86405 1.18207
    0.11501 0.15001 1.30107 1.41608
    0.11401 0.25801 1.31908 2.46314

    Из более-менее интересного: если вместо чисел от 100 до 9999 сортировать нули и единицы, то показатели скорости вырастут не сильно.

    Чемпионы


    Тут основная интрига в том, смогут ли сортировка расчёской и k-сортировка потеснить быструю с пьедестала?

    Чемпионы: Рандом


    Чтобы это выяснить, сформируем пакеты рандомных массивов: 10 штук по 10 тысяч элементов и 10 штук по 100 тысяч элементов. Хотел алгоритмам на вход дать и миллионники, но ноутбук не потянул. То оперативной памяти не хватает, то глубина рекурсии слишком велика.
    type=random, unique=False, count=10
    size(от min до max)
    10000(от 10000 до 99999) 100000(от 100000 до 999999)
    Python PHP Python PHP
    0.80205 0.63104 10.4506 8.24647
    0.47703 1.64009 6.65138 26.5435
    0.90005 2.18613 15.8089 29.4867

    K-сортировка на Питоне работает медленнее, а на PHP быстрее чем quick sort.
    Сортировка расчёской по сравнению с быстрой выглядит солидно, хотя и уступает ей на всех тестах (и на этих и последующих) при любых наборах данных.

    Однако есть у расчёски и важное неоспоримое преимущество. У неё нет рекурсии и поэтому в отличие от своих коллег она успешно обработывает массивы, состоящие из миллионов элементов.

    Особые случаи


    Хотя чемпионы скоростнее середнячков в сотни раз, на некоторых специфических наборах данных сортировки попроще показывают, что и они не лыком шиты.

    Особые случаи: Почти отсортировано


    Попробуем почти отсортированные массивы, только возьмём большего размера, чем те, что тестировали для середнячков.

    Пакет из 10 массивов по 10 тысяч и пакет из 10 массивов по 100 тысяч элементов.
    type=almost, unique=False
    size(от min до max) × count
    10000(от 10000 до 99999) × 10 100000(от 100000 до 999999) × 10
    Python PHP Python PHP
    0.43202 0.058 0.81705 0.58003
    0.084 0.062 0.85805 0.54003
    0.11601 0.12401 1.41908 1.36008
    0.14001 0.11901 1.83411 1.41708
    0.13801 0.23101 1.6491 2.56915
    ? 122.088 ? ?
    0.71504 1.58909 9.78356 19.4731

    Быстрая сортировка тут вообще не присутствует — не хватило оперативной памяти. При этом рандомные массивы на 10/100 тысяч элементов quicksort обрабатывает на ура. k-sort столкнулась с аналогичными проблемами, потянула только 10-титысячники на PHP. Большие почти отсортированные массивы — это вырожденный случай для быстрой сортировки и её модификаций. Из-за такого расположения элементов рекурсия делит массив на части практически для каждый пары рядом стоящих элементов, что приводит к максимально возможному количеству вызовов рекурсии.

    Кстати, аналогичная ситуация и с крупными реверсно упорядоченными массивам. Возникает та же проблема что и с почти упорядоченными — алгортитму приходится для каждой пары рядом стоящих элементов вызывать самого себя.

    Сортировка расчёской хоть и работает в полтора-два раза медленнее чем quick или k (в общем случае), но при этом не имеет вышеозначенных переполнений памяти. Нет рекурсии — нет проблемы.

    Ну и отметим, что все середнячки дружно обогнали чемпионов на крупных почти отсортированных массивах. Тут сработал принцип: «Тише едешь — дальше будешь».

    Особые случаи: Миллион алых роз малых массивов


    Малые массивы — стихия середнячков. Если нужно обрабатывать огромное количество небольших наборов чисел, то можно получить выигрыш по времени взяв «примитивную» пузырьковую или гномью сортировку. А быструю сортировку и иже с ней использовать для более масштабных задач.
    type=random, unique=True
    size(от min до max) × count
    5(от 10 до 99) × 1000000 10(от 10 до 99) × 1000000
    Python PHP Python PHP
    11.77267 17.888 24.29039 33.6659
    12.51872 18.165 29.33268 35.202
    15.44188 17.861 30.06672 36.7911
    14.18681 19.7831 31.65981 39.3533
    13.63978 24.3374 28.41662 52.864
    14.21881 21.1452 25.80548 32.5419
    14.58683 28.5016 24.85942 50.3139
    18.53806 30.7238 29.6647 58.2493


    С обмеными сортировками всё понятно. Теперь приступим к действительно интересному — сортировкам вставками.

    Ссылки


    Excel-приложение AlgoLab, с помощью которого можно в пошаговом режиме просмотреть визуализацию этих (и не только этих) сортировок.

    На Гугл-диске выложены также все массивы в виде JSON.

    Вики/WikiПридурковатая/Stooge, Slow, Гномья/Gnome, Пузырьковая/Bubble, Шейкер/Shaker, Чёт-нечет/Odd-Even, Расчёска/Comb, Быстрая/Quick

    Статьи серии


    Поделиться публикацией

    Похожие публикации

    Комментарии 14
      +2

      За такую реализацию быстрой сортировки нужно руки отрывать по самые ягодицы. Передайте и не позорьтесь. Уберите постоянное создание списков и сделайте нормальный выбор пивота.

        –1
        Скорее всего, Вы правы и вариант далёк от совершенства с практической точки зрения.

        Честно говоря, я избегаю писать свои версии всех этих многочисленных сортировок, предпочитаю на просторах Интернета находить работающие версии, написанные, по всей видимости, куда большими специалистами чем я. Конечный выбор той или иной реализации обуславливается синтаксисом, наиболее иллюстрирующим основную суть алгоритма. Остальное, ИМХО, вторично в данной ситуации.

        А вообще мне очень нравится вот эта версия:

        def quick_haskell(data):
            return (quick_haskell([y for y in data[1:] if y <  data[0]]) + 
                    data[:1] + 
                    quick_haskell([y for y in data[1:] if y >= data[0]])) if len(data) > 1 else data

        Но она не вписывается в стиль статьи в духе «о сортировках максимально доступными словами».
          +1

          Только у вас "быстрая" сортировка вместо обменов копирует данные в разные массивы, рекурсивно обрабатывает их и соединяет обратно.
          Именно поэтому не хватило памяти.

        +1
        Почему-то ни в приквеле, ни в этой статье не рассматривается сортировка Шелла.
          0
          Сортировка Шелла принадлежит к классу сортировок вставками, к изучению которого приступаем в следующей статье.
          +1
          Простите за вопрос, зачем нужные все эти кастомные реализации сортировок, если в языках уже есть стандартные? А если нет — есть куча готовых библиотек?
            0
            Очень дельный вопрос.

            Скажем так — данная серия статей ориентирована на тех, кто интересуется теорией алгоритмов.
            +1
            почему были выбраны такие медленные ЯП? и оба интерпретируемые
            что скажете насчет тестов с LuaJIT, JVM, LLVM и .NET?
            и что с компилируемыми ЯП?

            думаю, если потестировать такие сортировки на JIT и с компилируемыми языками, то результаты будут более репрезентативные и весьма интереснее
              0
              Отличная идея.

              Чтобы воплотить её в жизнь, осталось мне только в достаточной мере освоить какой-нибудь компилируемый язык программирования.
                +1
                Для начала можно попробовать использовать PyPy вместо CPython.
                  0
                  А вот это уже ближе к моим реалиям. Статьи про сортировки вставками также через несколько недель будут завершаться финальным всеобщим тестированием, надо будет действительно это сделать на PyPy. Спасибо, что дали наводку.
                  +1
                  Прошлая статья понравилась и всегда из любопытства поглядываю на сравнения даже хорошо известных вещей. Зашёл и увидел треш и угар: хоть картинки и выглядят подобранными, но когда доходишь до таблиц, половина из них нифига не понятна, какие-то клоуны, пираты, машинки и биты, мотать на легенду нет никакого желания. Про секунды на урезанном мобильном проце, который может дать провалы на ровном месте, да ещё и в PHP и питоне, на взятых от балды реализациях… вы серьёзно? Почему нельзя измерить скорость в количестве сравнений/обменов, ведь это основной показатель?
                    0
                    Я поразмышляю над Вашими замечаниями и постараюсь в будущих статьях, где будут сравниваться другие классы сортировок, учесть критику.

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

                    Возможно, раз тестирование у меня такое корявое, я вообще откажусь от этого формата и статьи все будут сугубо теоретическими. В общем, чуть позже определюсь с этим.
                      +1
                      Кому интересны алгоритмы, если нет сравнений, показывающих в чём их сила? Ведь смысл статей о сортировках, а не конкретно о QuickSort, в том, что бы показать, что не всё так однозначно. А ещё можно и придумать очень наглядные представления:
                      Видео по сортировкам

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое