Сортировка пузыря Сортировка выбора Сортировка?

Question

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

Но в моем коде сортировка пузыря последовательно превосходит выбор, поскольку массив становится больше.

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

Это мой код:

import java.util.Scanner; 
import java.util.Random; 

public class SelectionSorting 
{ 
    public static int[] arr; 
    public static long runningSelectionTime, runningBubbleTime; 

    public static void main(String[] args) 
    { 
    Scanner in = new Scanner(System.in); 
    System.out.println("Please enter the number of the items in the array: "); 
    int i = in.nextInt(); 
    System.out.println("Please enter the number of iterations: "); 
    int iters = in.nextInt(); 
    arr = new int[i]; 
    for (int x = 0; x < iters; x++) 
    { 
     for (int n = 0; n < i; n++) 
     { 
     arr[n] = randomness(); 
     } 
     long startSelectionTime = System.nanoTime(); 
     selectionSort(arr); 
     long endSelectionTime = System.nanoTime(); 
     runningSelectionTime += endSelectionTime - startSelectionTime; 
    } 
    System.out.println("Selection Sort: "); 
    System.out.println("Total running time: " + runningSelectionTime + " and the average is " + runningSelectionTime/iters); 

    for (int x = 0; x < iters; x++) 
    { 
     for (int n = 0; n < i; n++) 
     { 
     arr[n] = randomness(); 
     } 
     long startBubbleTime = System.nanoTime(); 
     bubbleSort(arr); 
     long endBubbleTime = System.nanoTime(); 
     runningBubbleTime += endBubbleTime - startBubbleTime; 
    } 
    System.out.println("Bubble Sort: "); 
    System.out.println("Total running time: " + runningBubbleTime + " and the average is " + runningBubbleTime/iters); 
    } 

    public static void selectionSort(int[] array) 
    { 
    for (int i = 0; i < array.length - 1; i++) 
    { 
     int iMin = i; 
     for (int j = i + 1; j < array.length; j++) 
     { 
     if (array[j] < array[iMin]) 
     { 
      iMin = j; 
     } 
     } 
     if (iMin != i) 
     { 
     int temp = array[i]; 
     array[i] = array[iMin]; 
     array[iMin] = temp; 
     } 
    } 
    } 

    public static void bubbleSort(int[] arr) 
    { 
    int unsorted = arr.length; 
    while (unsorted != 0) 
    { 
     int lastSwap = 0; 
     for (int i = 1; i < unsorted; i++) 
     { 
     if (arr[i - 1] > arr[i]) 
     { 
      swap(arr, i, i - 1); 
      lastSwap = i; 
     } 
     } 
     unsorted = lastSwap; 
    } 
    } 

    private static void swap(int[] arr, int a, int b) 
    { 
    int temp = arr[a]; 
    arr[a] = arr[b]; 
    arr[b] = temp; 
    } 

    public static int randomness() 
    { 
    Random rand = new Random(); 
    int random = rand.nextInt(); 
    if (random < 0) 
    { 
     random = random * -1; 
    } 
    do { 
     random = random/10; 
    } while (random > 100); 
    return random; 
    } 

} 

Если вы попытаетесь положить в 500 и 1000, время работы пузырьковой сортировки будет короче, чем выбор сорта.

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

Любые идеи относительно того, почему это так? Я сделал что-то не так? Возможно ли, чтобы сортировка пузырьков превосходила сортировку сортировки (последовательно)?

(Для предотвращения путаницы, я видел вопрос Why is my Java based Bubble Sort Outperforming my Selection sort and my Insertion Sort?, но он не решает ту же проблему.)

Answer 1

Ваш пузырьковая сортировка быстрее, потому что он не работает.

 arr[i] = temp; 

должен быть

 arr[i-1] = temp; 

выход для 10000 * 3

Выбор Сортировка:
Общее время работы: 216077472 и в среднем составляет 72025824
Bubble Сортировка:
Общее время : 402583050 и в среднем 134194350

выход для 500 * 1000

Выбор Сортировка:
Общее время работы: 123621068 и в среднем составляет 123621
Bubble Сортировка:
Общее время работы: 317450183 и в среднем составляет 317450

с помощью использования jdk 7