Код сортировки пузырьком (bubble sort), реализованный мною на Джаве, сортирует массив, сортированный наоборот, быстрее, чем массив со случайными числами. При этом перемещений данных на первом массиве (сортированном наоборот) такое же, как и количество итераций (т.е. их дофига), а во-втором случае (случайные цифры) их раза в два МЕНЬШЕ. Но сортируется массив со случайными числами в две раза МЕДЛЕННЕЕ. Я уже все мозги продумал -- не понимаю, что такое!
Вот код, если кому-то вдруг захочется помочь:
import java.util.*;
public class Sortus {
public static void main(String[] args)
{
Random randomizer = new Random();
int size = 10000;
int [] randomArray = new int[size];
int [] reverseSortedArray = new int [size];
long startTime, endTime, totalTime;
for (int i = 0; i < randomArray.length; i++)
randomArray[i] = randomizer.nextInt(size);
for (int i = 0, k = reverseSortedArray.length; i < reverseSortedArray.length - 1; i++, k--)
reverseSortedArray[i] = k;
startTime = System.currentTimeMillis();
//sort reverse sorted array
bubbleSort(reverseSortedArray);
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println("Time elapsed: " + totalTime);
//sort randomized
startTime = System.currentTimeMillis();
bubbleSort(randomArray);
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println("Time elapsed: " + totalTime);
}
public static void bubbleSort(int [] toSort)
{
int temp, movesMade = 0, iterations = 0;
for (int k = toSort.length - 1; k > 1; k--)
{
for (int i = 1; i < k; i++)
{
iterations++;
if (toSort[i - 1] > toSort[i])
{
temp = toSort[i - 1];
toSort[i - 1] = toSort[i];
toSort[i] = temp;
movesMade++;
}
}
}
System.out.println("\nIterations: " + iterations + " Moves made: " + movesMade);
}
}
