Comments / Profile of 1nt3g3r / Habr

Мельничук Иван Владимирович @1nt3g3r

Программист мобильных игр

Profile Publications 11Comments 102Bookmarks 29

1nt3g3r Dec 4 2013 at 03:31

Прочитал пост, не удержался, написал быстренько все на java, с примерными замерами времени (разница System.time.currentTimeMillis() до и после вызова метода сортировки).
Результаты следующие.
«Глупая» сортировка зависает на неопределенное время на размере массива около 3000 элементов. На 2000 показывает время примерно 1600 мс.
«Пузырьковая» ведет себя лучше — около 25 мс на размере 2000 элементов. На 30 000 элементов — 2700 мс, почти три секунды.
«Шейкерная» сортировка — на размере 2000 элементов такие же, даже немного хуже (спишем на статистику) результаты. А вот на 30000 элементов разница в два раза — 1200 мс.
«Гребешковая» сортировка меня удивила. Я ожидал, что будет быстрее, но не на столько же! 2000 элементов — 11 мс. 30 000 элементов — 26 мс. 30 000 000 — 5500 мс.
Для сравнения — Arrays.sort(): 3000 элементов — 14-15 мс, 30000 — 30-40 мс, 30 000 000 — 3400 мс.

Вы заметили, что «гребешковая» сортировка получилась быстрее стандартной джавы? Меня это заинтересовало, и я начал увеличивать размер массива, и сравнивать результаты «гребешка» и Arrays.sort(). Получилось, что до 1 500 000 элементов «гребешок» быстрее, а вот дальше уже стандартная сортировка начинает работать быстрее.

Вот такие вот результаты :) Приятно, что реализация «гребешковой» сортировки тривиальна — можно реально использовать на небольших массивах с реальной пользой.
Кому интересно, привожу «тестовую лабораторию»:

Немного дурно пахнущего кода

package com.webprestige.winter.wallpaper;

import java.util.Random;

public class DesktopStarter {
	
	public static void main(String[] args) {
		int size = 30000000;
		Random r = new Random();
		int[] v = new int[size];
		for (int i = 0; i < size; v[i++] = r.nextInt(10000));
		long time = System.currentTimeMillis();
			coolSort(v);
		long endTime = System.currentTimeMillis();
		System.out.println("Time is " + (endTime - time));
		
//		 for(int i = 0; i < size; i++) {
//		 System.out.print(v[i] + " ");
//		 }
	}

	
private static void stupidSort(int[] v) {
		boolean end = false;
		while (!end) {
			end = true;
			for (int i = 0; i < v.length - 1; i++) {
				if (v[i] > v[i + 1]) {
					int t = v[i];
					v[i] = v[i + 1];
					v[i + 1] = t;
					end = false;
					break;
				}
			}
		}
	}

	private static void bulbSort(int[] v) {
		boolean end = false;
		while (!end) {
			end = true;
			for (int i = 0; i < v.length - 1; i++) {
				if (v[i] > v[i + 1]) {
					int t = v[i];
					v[i] = v[i + 1];
					v[i + 1] = t;
					end = false;
				}
			}
		}
	}
	
	private static void shakeSort(int[] v) {
		boolean end = false;
		while (!end) {
			end = true;
			for (int i = 0; i < v.length - 1; i++) {
				if (v[i] > v[i + 1]) {
					int t = v[i];
					v[i] = v[i + 1];
					v[i + 1] = t;
					end = false;
				}
			}
			
			for (int i = v.length - 1; i > 0; i--) {
				if (v[i] < v[i - 1]) {
					int t = v[i];
					v[i] = v[i - 1];
					v[i - 1] = t;
					end = false;
				}
			}
		}
	}
	
	
	
	

public static void coolSort(int[] v) {
		float loadFactor = 1.247f;
		int step = v.length;
		boolean end = false;
		int t;
		while (!end) {
			end = true;
			step /= loadFactor;
			if (step < 1) {
				step = 1;
			}
			for (int i = 0; i < v.length - 1; i++) {
				if ((i + step) < v.length) {
					if (v[i] > v[i + step]) {
						t = v[i];
						v[i] = v[i + step];
						v[i + step] = t;
						end = false;
					}
				} else {
					end = false;
				}

			}

		}
	}
}