nlothik (nlothik) wrote,
nlothik
nlothik

Сортировка пузырьком

Блин, я уже матом хочу ругаться.

Код сортировки пузырьком (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);

}

}
Subscribe

  • Баклажаны

    Оказывается, бывают белые баклажаны. Более того, англичане впервые столкнулись именно с ними, поэтому баклажаны в английском языке называются…

  • Глазам своим не верю

    “In a press conference yesterday with reporters, White House climate adviser Gina McCarthy said the administration would seek to implement a…

  • Про метрическую систему

    Кодекс США от 1975 года, глава 15, параграф 205b: Декларация о политике Соединённых Штатов: (1) определить метрическую систему измерения как…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments