Last active
June 28, 2016 19:52
-
-
Save josinSbazin/3d011d790b0ae28a4162a8fa842fb087 to your computer and use it in GitHub Desktop.
Проверка скорости алгоритмов сортировки (Если у вас ошибка StackOverflowError (в quick sort) смотрите 149 строчку)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package TEST; | |
import java.io.BufferedReader; | |
import java.io.InputStreamReader; | |
import java.util.*; | |
public class qSort { | |
static Random rand = new Random(); | |
public static void main(String[] args) { | |
BufferedReader r = new BufferedReader(new InputStreamReader(System.in)); | |
int n = 1; | |
while (true) { | |
System.out.println("Введите число - размер массива:"); | |
try { | |
n = Integer.parseInt(r.readLine()); | |
if (n<=0) throw new ArrayIndexOutOfBoundsException("out!"); | |
break; | |
} | |
catch (NumberFormatException e) { | |
System.out.println("Ошибка! Введенные данные не являются числом."); | |
} | |
catch (ArrayIndexOutOfBoundsException e) { | |
System.out.println("Ошибка. Введенное число должно быть больше нуля."); | |
} | |
catch (Exception e) { | |
System.out.println("Неизвестная ошибка!"); | |
System.exit(-1); | |
} | |
} | |
int[] array = new int[n]; | |
for (int i = 0; i < array.length; i++) { | |
array[i] = rand.nextInt()-5000; | |
} | |
int[] array1; | |
array1 = array.clone(); | |
int[] array2; | |
array2 = array.clone(); | |
int[] array3; | |
array3 = array.clone(); | |
System.out.println("Список массива до сортировки:"); | |
for (int i = 0; i < array2.length - 1; i++) { | |
System.out.print(array2[i] + ", "); | |
} | |
System.out.println(array2[array2.length - 1]); | |
//Украшательства :) | |
System.out.print("Сортируем "); | |
//for (int i = 0; i < 5; i++) { | |
//try { | |
// Thread.sleep(300); | |
//} | |
//catch (Exception e) { | |
// System.out.println(e); | |
// } | |
// System.out.print(". "); | |
// } | |
System.out.println("\n"); | |
long start = System.nanoTime(); | |
quickSort(array, 0, array.length - 1); | |
long end = System.nanoTime(); | |
long start1 = System.nanoTime(); | |
bubbleSort(array1, 0, array1.length - 1); | |
long end1 = System.nanoTime(); | |
long start2 = System.nanoTime(); | |
quickSortOptimize(array2, 0, array.length - 1); | |
long end2 = System.nanoTime(); | |
long start3 = System.nanoTime(); | |
combSort(array3, 0, array3.length - 1); | |
long end3 = System.nanoTime(); | |
System.out.println("Список массива после быстрой сортировки:"); | |
for (int i = 0; i < array.length - 1; i++) { | |
System.out.print(array[i] + ", "); | |
} | |
System.out.println(array[array.length - 1]); | |
System.out.println(""); | |
System.out.println("Список массива после сортировки пузырьком:"); | |
for (int i = 0; i < array1.length - 1; i++) { | |
System.out.print(array1[i] + ", "); | |
} | |
System.out.println(array1[array1.length - 1]); | |
System.out.println(""); | |
System.out.println("Список массива после оптимизированной сортировки:"); | |
for (int i = 0; i < array2.length - 1; i++) { | |
System.out.print(array2[i] + ", "); | |
} | |
System.out.println(array2[array2.length - 1]); | |
System.out.println(""); | |
System.out.println("Список массива после сортировки расческой:"); | |
for (int i = 0; i < array3.length - 1; i++) { | |
System.out.print(array3[i] + ", "); | |
} | |
System.out.println(array3[array3.length - 1]); | |
System.out.println(""); | |
HashMap <String, Long> map = new HashMap<String, Long>(); | |
long time = end - start; | |
long time1 = end1 - start1; | |
long time2 = end2 - start2; | |
long time3 = end3 - start3; | |
map.put("ВРЕМЯ БЫСТРОЙ СОРТИРОВКИ: ",time); | |
map.put("ВРЕМЯ ПУЗЫРЬКОВОЙ СОРТИРОВКИ: ",time1); | |
map.put("ВРЕМЯ ОПТИМИЗИРОВАННОЙ СОРТИРОВКИ: ",time2); | |
map.put("ВРЕМЯ СОРТИРОВКИ РАСЧЕСКОЙ: ",time3); | |
List<Map.Entry<String, Long>> entries = new ArrayList<Map.Entry<String, Long>>(map.entrySet()); | |
Collections.sort(entries, new Comparator<Map.Entry<String, Long>>() { | |
@Override | |
public int compare(Map.Entry<String, Long> e1, Map.Entry<String, Long> e2) { | |
long v1 = e1.getValue(); | |
long v2 = e2.getValue(); | |
return (v1 > v2) ? 1 : (v1 == v2) ? 0 : -1; | |
} | |
}); | |
for (Map.Entry<String, Long> e : entries) { | |
System.out.println(e.getKey()+e.getValue()+" наносекунд!"); | |
} | |
} | |
//БЫСТРАЯ СОРТИРОВКА | |
public static void quickSort(int[] array, int l, int r) { | |
// Индекс элемента массива начала сортировки: | |
int i = l; | |
// Индекс элемента массива конца сортировки: | |
int j = r; | |
// Вычисление "среднего" элемента для сравнения: | |
int x = array[l + (r - l) / 2]; //Здесь причина ошибки StackOverflowError, используйте этот вариант | |
// int x = array[(l+r)/2]; | |
// int x = array[l + rand.nextInt(r - l + 1)]; //Этот вариант медленнее в ~ 1.74 раза верхнего | |
// Крутим цикл, пока i<=j, если иначе, то элементы массива уже рассортированы относительно элемента x: | |
while (i <= j) { | |
// Идем по массиву от начала (i) до "середины" (x) и ищем элемент, который меньше середины. | |
// Как только нашли - приостанавливаемся и получаем индек i большего элемента чем x. | |
// Его нужно перенести правее середины. | |
while (array[i] < x) { | |
i++; | |
} | |
// Аналогично предыдущему шагу идем от конца (j) до "середины". Ищем индекс нужного элемента. | |
while (array[j] > x) { | |
j--; | |
} | |
// Если i<=j, т.е. если наш индекс не зашел на другую сторону (в противном случае сортировка | |
// относительно "середины" (x) окончена. | |
if (i <= j) { | |
int temp = array[i]; | |
array[i] = array[j]; | |
array[j] = temp; | |
i++; | |
j--; | |
} | |
// ОТОБРАЖЕНИЕ ИТЕРАЦИЙ: | |
// for (int t : array) System.out.print(t+", "); | |
// System.out.println(""); | |
} | |
// Если j не дошел до начала (l) сортируемого участка, то сортируем рекурсивно тем же методом участок левее j: | |
if (l < j) { | |
quickSort(array, l, j); | |
} | |
// Если i не дошел до конца (r) сортируемого участка, то сортируем рекурсивно тем же методом участок правее i: | |
if (i < r) { | |
quickSort(array, i, r); | |
} | |
// Если оба оператора - false - массив отсортирован! | |
} | |
// ПУЗЫРЬКОВАЯ СОРТИРОВКА | |
public static void bubbleSort(int[] array, int start, int end) { | |
int er; | |
while (true) { | |
er = 0; | |
for (int j = start; j < end; j++) { | |
if (array[j] > array[j + 1]) { | |
int temp = array[j + 1]; | |
array[j + 1] = array[j]; | |
array[j] = temp; | |
//если есть элементы не попорядку, то прибавляем единицу к er | |
er++; | |
} | |
} | |
if (er == 0) break; //если нет неотсортированных элементов, то прирываем сортировку | |
end--; | |
} | |
} | |
//"КОМБИНИРОВАННАЯ СОРТИРОВКА С БЫСТРАЯ+ПУЗЫРЕК | |
public static void quickSortOptimize(int[] array, int l, int r) { | |
// Индекс элемента массива начала сортировки: | |
int i = l; | |
// Индекс элемента массива конца сортировки: | |
int j = r; | |
// Вычисление "среднего" элемента для сравнения: | |
int x = array[l + (r - l) / 2]; //Здесь причина ошибки StackOverflowError, используйте этот вариант | |
// int x = array[(l+r)/2]; | |
// int x = array[l + rand.nextInt(r - l + 1)]; //Этот вариант медленнее в ~ 1.74 раза верхнего | |
// Крутим цикл, пока i<=j, если иначе, то элементы массива уже рассортированы относительно элемента x: | |
while (i <= j) { | |
// Идем по массиву от начала (i) до "середины" (x) и ищем элемент, который меньше середины. | |
// Как только нашли - приостанавливаемся и получаем индек i большего элемента чем x. | |
// Его нужно перенести правее середины. | |
while (array[i] < x) { | |
i++; | |
} | |
// Аналогично предыдущему шагу идем от конца (j) до "середины". Ищем индекс нужного элемента. | |
while (array[j] > x) { | |
j--; | |
} | |
// Если i<=j, т.е. если наш индекс не зашел на другую сторону (в противном случае сортировка | |
// относительно "середины" (x) окончена. | |
if (i <= j) { | |
int temp = array[i]; | |
array[i] = array[j]; | |
array[j] = temp; | |
i++; | |
j--; | |
} | |
// ОТОБРАЖЕНИЕ ИТЕРАЦИЙ: | |
// for (int t : array) System.out.print(t+", "); | |
// System.out.println(""); | |
} | |
if (l < j && (j-l)<=7) { | |
bubbleSort(array, l, j); | |
j=l; | |
} | |
// Если j не дошел до начала (l) сортируемого участка, то сортируем рекурсивно тем же методом участок левее j: | |
else if (l < j) { | |
quickSort(array, l, j); | |
} | |
// Если i не дошел до конца (r) сортируемого участка, то сортируем рекурсивно тем же методом участок правее i: | |
if (i < r && (r-i)<=7) { | |
bubbleSort(array, i, r); | |
i=r; | |
} | |
else if (i < r) { | |
quickSort(array, i, r); | |
} | |
// Если оба оператора - false - массив отсортирован! | |
} | |
//СОРТИРОВКА РАСЧЕСКОЙ | |
public static void combSort(int[] array, int start, int end) { | |
int j; | |
int er=0; | |
double step = end/1.247; | |
while (true) { | |
j=start+(int)step-1; | |
j=j<=0?1:j; | |
// if (j==start) break; | |
int i = start; | |
for (; j <= end; i++) { | |
if (array[i]>array[j]) { | |
int t = array[i]; | |
array[i] = array[j]; | |
array [j] = t; | |
er++; | |
} | |
j++; | |
} | |
if (er==0&&j==i+1) break; | |
er=0; | |
step/=1.247; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment