QuickSort Tester Отладка

У меня есть следующий код для 4 видов метода разбиения для quickSort. Прямо сейчас, если я запускаю код производительности различных разделов являютсяQuickSort Tester Отладка

производительность partition0 является 1877,
partition2 является 781,
partition3 674,
partition4 составляет около 595.

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

я заметил, единственное различие между partition0 и Partition1 является то, что условие времени цикла в: один имеет < =, а другой имеет <. Но когда я сменил первый < = на <, производительность не изменилась. 2. что есть {} while (некоторое условие). Это то же самое, что и обычный цикл while?
я заметил, единственное различие между partition0 и partition1 является то, что состояние while Loop в: один имеет <=, а другой имеет <. Но когда я изменил первый <= на <, производительность не изменилась.
Что такое do{ } while(some condition). Это то же самое, что и обычный цикл while?

import java.util.Arrays; 
import java.util.Random; 

public class QuickSortTester { 
static private Random rand = new Random(0); 

public static void main(String[] args) { 

    int arraySize = 1000; 

    Integer[] list; 

    long start, end; 

    list = generateSortedIntegerArray(arraySize); 
    // list = generateRandomIntegerArray(arraySize); 
    System.out.printf("\n%15d", arraySize); 

    start = System.nanoTime(); 
    sort(list, 0); 
    end = System.nanoTime(); 
    System.out.printf("\t%15d", (end - start)/1000); 
    if (!isSorted(list)) 
     System.out.printf("Not sorted - problems!"); 

    System.out.println(); 

    list = generateSortedIntegerArray(arraySize); 
    // list = generateRandomIntegerArray(arraySize); 
    System.out.printf("\n%15d", arraySize); 

    start = System.nanoTime(); 
    sort(list, 1); 
    end = System.nanoTime(); 
    System.out.printf("\t%15d", (end - start)/1000); 
    if (!isSorted(list)) 
     System.out.printf("Not sorted - problems!"); 

    System.out.println(); 
    list = generateSortedIntegerArray(arraySize); 
    // list = generateRandomIntegerArray(arraySize); 
    System.out.printf("\n%15d", arraySize); 

    start = System.nanoTime(); 
    sort(list, 2); 
    end = System.nanoTime(); 
    System.out.printf("\t%15d", (end - start)/1000); 
    if (!isSorted(list)) 
     System.out.printf("Not sorted - problems!"); 

    System.out.println(); 
    list = generateSortedIntegerArray(arraySize); 
    //list = generateRandomIntegerArray(arraySize); 
    System.out.printf("\n%15d", arraySize); 

    start = System.nanoTime(); 
    sort(list, 3); 
    end = System.nanoTime(); 
    System.out.printf("\t%15d", (end - start)/1000); 
    if (!isSorted(list)) 
     System.out.printf("Not sorted - problems!"); 

} 


public static <E extends Comparable<E>> boolean isSorted(E[] list) { 
    for (int i = 1; i < list.length; i++) { 
     if (list[i - 1].compareTo(list[i]) > 0) { 
      return false; 
     } 
    } 
    return true; 
} 


public static Integer[] generateRandomIntegerArray(int size) { 
    Integer list[] = new Integer[size]; 

    for (int i = 0; i < list.length; i++) 
     // list[i] = rand.nextInt(10); //range from zero to number - 1 
     list[i] = rand.nextInt(); // unlimited range 
    return list; 
} 

public static Integer[] generateSortedIntegerArray(int size) { 
    Integer list[] = generateRandomIntegerArray(size); 
    Arrays.sort(list); 
    return list; 
} 

public static <E extends Comparable<E>> void sort(E[] list, int version) { 
    quickSort(list, 0, list.length - 1, version); 
} 

private static <E extends Comparable<E>> void quickSort(E[] list, int first, int last, int version) { 
    if (last > first) { 
     int pivotIndex; 
     if (version == 0) 
      pivotIndex = partition0(list, first, last); 
     else if (version == 1) 
      pivotIndex = partition1(list, first, last); 
     else if (version == 2) 
      pivotIndex = partition2(list, first, last); 
     else 
      pivotIndex = partition3(list, first, last); 
     quickSort(list, first, pivotIndex - 1, version); 
     quickSort(list, pivotIndex + 1, last, version); 
    } 
} 

private static <E extends Comparable<E>> int partition0(E[] list, int first, int last) { 
    int pivotIndex = (first + last)/2; 
    E pivot = list[pivotIndex]; // Choose the first element as the pivot 
    swap(list, last, pivotIndex); 
    pivotIndex = last; 
    last--; 
    while (last >= first) { 
     // Search forward from left 
     while (first <= last && list[first].compareTo(pivot) < 0) //problem 
      first++; 
     // Search backward from right 
     while (first <= last && list[last].compareTo(pivot) >= 0) 
      last--; 

     // Swap two elements in the list 
     if (last > first) { 
      swap(list, first, last); 
      first++; 
      last--; 
     } 
    } 
    swap(list, pivotIndex, first); 

    return first; 
} 

private static <E extends Comparable<E>> int partition1(E[] list, int first, int last) { 
    int pivotIndex = (first + last)/2; 
    E pivot = list[pivotIndex]; // Choose the first element as the pivot 
    swap(list, last, pivotIndex); 
    pivotIndex = last; 
    last--; 
    while (last >= first) { 
     // Search forward from left 
     while (first <= last && list[first].compareTo(pivot) < 0) 
      first++; 
     // Search backward from right 
     while (first <= last && list[last].compareTo(pivot) >= 0) 
      last--; 

     // Swap two elements in the list 
     if (last > first) { 
      swap(list, first, last); 
      first++; 
      last--; 
     } 
    } 
    swap(list, pivotIndex, first); 

    return first; 
} 

private static <E extends Comparable<E>> int partition2(E[] list, int first, int last) { 

    int pivotIndex = (first + last)/2; 

    E pivot = list[pivotIndex]; // Choose the first element as the pivot 
    swap(list, last, pivotIndex); 
    pivotIndex = last; 
    last--; 

    while (last > first) { 
     // Search forward from left 
     while (first <= last && list[first].compareTo(pivot) < 0) 
      first++; 
     // Search backward from right 
     while (first <= last && list[last].compareTo(pivot) > 0) 
      last--; 

     // Swap two elements in the list 
     if (last > first) { 
      swap(list, first, last); 
      first++; 
      last--; 
     } 
    } 
    swap(list, pivotIndex, first); 

    return first; 
} 

private static <E extends Comparable<E>> int partition3(E[] list, int first, int last) { 
    int pivotIndex = (first + last)/2; 
    E pivot = list[pivotIndex]; // Choose the first element as the pivot 
    swap(list, last, pivotIndex); 
    pivotIndex = last; 
    last--; 
    do { 
     // Search forward from left 
     while (first < last && list[first].compareTo(pivot) <= 0) 
      first++; 
     // Search backward from right 
     while (first <= last && list[last].compareTo(pivot) > 0) 
      last--; 

     // Swap two elements in the list 
     if (last >= first) { 
      swap(list, first, last); 
      first++; 
      last--; 
     } 
    } while (last > first); 

    swap(list, pivotIndex, first); 

    return first; 
} 

private static <E> void swap(E[] list, int index1, int index2) { 
    E tmp = list[index1]; 
    list[index1] = list[index2]; 
    list[index2] = tmp; 
} 

}

источник

2015-10-22 Hanming Zeng

Я не 100% уверен, но я считаю, что это потому, что последний и первый используется для проверки, если индекс слева и справа встретились. Если это так, обмен не произойдет, и если первый и последний ane равны, когда он попадет в оператор if, который не заменит swap.
do-while loop это как цикл while, разница в том, что он будет выполняться всегда 1 раз, независимо от того, является ли утверждение истинным или ложным. Затем он будет выполнять блок как обычный цикл while или нет, в зависимости от логического условия, которое вы установили для него.

Больше информации о сделай время цикла: http://www.tutorialspoint.com/java/java_loop_control.htm

В коде:

do { 
     // Search forward from left 
     while (first < last && list[first].compareTo(pivot) <= 0) 
      first++; 
     // Search backward from right 
     while (first <= last && list[last].compareTo(pivot) > 0) 
      last--; 

     // Swap two elements in the list 
     if (last >= first) { 
      swap(list, first, last); 
      first++; 
      last--; 
     } 
    } while (last > first);

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

источник

2015-10-22 20:53:29

QuickSort Tester Отладка

ответ

Смежные вопросы