Скорость разных методов сортировки

[v01d0s]

Я только начинаю изучать программирование.

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

Решил проверить, просто ради интереса.

<script type="text/javascript">		

		function bench(f) {
			var arr = [2,5,1,4,3,6,8,0,4,32,3,5,7,9,43,2,11];
			d = new Date();
			for (i = 0; i < 1000; i++) {
				f(arr);
			}
			return new Date() - d;
		}

		function bench2(f) {
			var arr = [2,5,1,4,3,6,8,0,4,32,3,5,7,9,43,2,11];
			d = new Date();
			for (i = 0; i < 1000; i++) {
				f(arr, 0, arr.length - 1);
			}
			return new Date() - d;
		}

		function compare(a, {
			return a - b;
		}

		function defaultSort(arr) {
			arr.sort(compare);
		}

		function bubbleSort(arr) {

			for (var i = 0; i < arr.length -1; i++ ) {
				for (var j = 0; j < arr.length - i - 1; j++ ) {
					if (arr[j] > arr[j+1]) {
						arr[j] = arr[j] + arr[j+1];
						arr[j+1] = arr[j] - arr[j+1];
						arr[j] = arr[j] - arr[j+1]; 
					}

				}
			}

		}

		function quickSort(arr,min,max) {
			var i = min,
				j = max,
				mid = arr[i];

			while ( i <= j) {
				while(arr[i] < mid) i++;
				while(arr[j] > mid) j--;
				if (i <= j) {
					c = arr[i];
					arr[i] = arr[j];
					arr[j] = c;
					i++;
					j--;
				}
			}

			if (min < j) {quickSort(arr,min,j)}
			if (max > i) {quickSort(arr,i,max)}

		}

		alert(bench2(quickSort));
		alert(bench(defaultSort));
		alert(bench(bubbleSort));




	</script>

Теперь вопрос: почему "сортировка пузырьком" выполняется по скорости примерно одинаково с "быстрой сортировкой"?

Кому не сложно прошу объяснить.

[lexxcode]

Слишком маленький массив, чтобы увидеть существенную разницу. Задай массив хотя бы на 10000 элементов

[Radiocity]

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

Да, считается. Однако, это не актуально из-за современных мощностей.

Самыми медленными операциями являются умножение, деление, возведение в степень, корень из числа..

Операции сложения, вычитания, присваивания, простые логические операции - самые быстрые.

Edited June 3, 2012 by Radiocity

[nerv]

Да, считается. Однако, это не актуально из-за современных мощностей.

неужели?)

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

Пузырек я бы использовал максимум до 500 элементов.

Дальше будет ай-яй-яй.

Впрочем, непонятно зачем что-то выдумывать, если в js есть функция sort()

Лирическое отступление.

Одно время интересовался алгоритмами сортировки. Пытался придумать свой. Наверное неделю на это потратил. В результате получилось 2-а алгоритма разных по объему кода. Первый (малый объем кода) назвал его LiteSort (не знаю почему). Результаты тестов не сохранились, но вроде бы он показал результаты лучше, чем любая разновидность пузырька, ShakerSort и т.п. простые алгоритмы. Второй - SortLimpDoubleStep в разы быстрее пузырькой сортировки. На объемах до 10 000 (если мне не изменяет память) мог соперничать с быстрой сортировкой. Впоследстии оказалось, что данный алгоритм очень похож на сортировку Шелла. Знал бы это раньше, мож и не стал бы доделывать)

Кстати, еще существует быстрая сортировка без рекурсии. Насколько помню, массивы по 60 000 (стоки + числа) гоняла за ~ 0,3 сек.

Edited June 3, 2012 by nerv

[v01d0s]

Все ясно.

Всем спасибо =)