Упражнения на Java: алгоритм сортировки по Stooge

Алгоритм сортировки Java: упражнение 18 с решением

Напишите Java-программу для сортировки массива заданных неотрицательных целых чисел с помощью алгоритма сортировки Stooge.

Сортировка по Стогу - это алгоритм рекурсивной сортировки с временной сложностью O ( n log 3 / log 1.5) = O ( n 2.7095 ...). Время выполнения алгоритма, таким образом, медленнее по сравнению с эффективными алгоритмами сортировки, такими как сортировка слиянием, и даже медленнее, чем сортировка Bubble.

Пример решения:

Java-код:

import java.util.Arrays;
 public class Stooge {
    public static void main(String[] args) {
      System.out.println("Original Array:");
        int[] nums = {7, -5, 3, 2, 1, 0, 45};
        System.out.println(Arrays.toString(nums));
        stoogeSort(nums);
        System.out.println("Sorted Array:");
        System.out.println(Arrays.toString(nums));
    }
 
    public static void stoogeSort(int[] L) {
        stoogeSort(L, 0, L.length - 1);
    }
 
    public static void stoogeSort(int[] L, int i, int j) {
        if (L[j] < L[i]) {
            int tmp = L[i];
            L[i] = L[j];
            L[j] = tmp;
        }
        if (j - i > 1) {
            int t = (j - i + 1) / 3;
            stoogeSort(L, i, j - t);
            stoogeSort(L, i + t, j);
            stoogeSort(L, i, j - t);
        }
    }
}

Пример вывода:

 Оригинальный массив:
[7, -5, 3, 2, 1, 0, 45]
Сортированный массив:
[-5, 0, 1, 2, 3, 7, 45]

Блок - схема:

Редактор кода Java:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите Java-программу для сортировки массива заданных целых чисел Алгоритм сортировки по Стогу.
Далее: Напишите Java-программу для сортировки массива заданных целых чисел с помощью алгоритма сортировки по группам.