Алгоритмы внутренней сортировки

@JanCover · Регистрация: 12.11.2015

Студворк — интернет-сервис помощи студентам

Приветствую братцы, прошу вас о помощи в одном не сложном дельце, помогите люди добрые с программой, а именно написанием, коль вам не сложно будет. Очень надо, не могу понять как сделать данное задание. =(

ЗАДАНИЕ:
1. Написать программу, реализующую сортировку массива заданным способом
(согласно варианту).
2. Сравнить число сравнений (С) и обменов (М) для числовых массивов, содержа-
щих различное число элементов (20, 500, 1000, 3000, 5000, 10000), выбираемых слу-
чайным образом. Оценить время сортировки.
3. Исследовать влияние начальной упорядоченности массива (отсортированный,
отсортированный в обратном порядке, отсортирован случайным образом).
4. Все полученные данные ввести в таблицу 1. Сравнить эффективности сорти-
ровки массивов разной размерности и упорядоченности. Сделать выводы.

Вариант 9: Сортировка Шелла (ℎ i-1 = 3ℎi + 1: 1,4,13,40,121, … )

Язык программирование в принципе не важен, главное результат =)

@RedPatrick · 09.03.2016, 13:50

JanCover, Вот Вам класс:

Java

public class Sorter {
 
    //сортировка пузырьком
    public void bubbleSort(int[] arr) {
        int swaps = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
        System.out.println("Sorting by Bubble Methods:");
        for (int anArr : arr) {
            System.out.print(anArr + " ");
        }
        System.out.println("\nSwaps by this methods: " + swaps);
    }
 
    //сортировка методом Шелла
    public void shellSort(int[] arr) {
        int swaps = 0;
        int dim1 = 9;
        int dim2 = 6;
        int dim3 = 3;
        //first iteration
        for (int i = 0; i < arr.length - dim1; i++) {
            for (int j = i + dim1; j < arr.length; j += dim1) {
                if (j < arr.length) if (arr[i] > arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
        //second iteration
        for (int i = 0; i < arr.length - dim2; i++) {
            for (int j = i + dim2; j < arr.length; j += dim2) {
                if (j < arr.length) if (arr[i] > arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
        //third iteration
        for (int i = 0; i < arr.length - dim3; i++) {
            for (int j = i + dim3; j < arr.length; j += dim3) {
                if (j < arr.length) if (arr[i] > arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
        //final iteration
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
 
 
        System.out.println("Sorting by Shell Methods:");
        for (int anArr : arr) {
            System.out.print(anArr + " ");
        }
        System.out.println("\nSwaps by this methods: " + swaps);
    }
 
    public void hoareSort(int[] arr) {
        int swaps = 0;
        swaps = iterateHoare(arr, 0, arr.length-1);
 
        System.out.println("Sorting by Hoare Methods:");
        for (int anArr : arr) {
            System.out.print(anArr + " ");
        }
        System.out.println("\nSwaps by this methods: " + swaps);
    }
 
    //быстрая сортировка (метод Хоара)
    public int iterateHoare(int[] arr, int first, int last) {
        int swaps = 0;
        int i = first, j = last;
        int base = arr[(first + last + 1) / 2];
        while (i < j) {
            while (arr[i] < base) i++;
            while (arr[j] > base) j--;
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
                swaps++;
            }
        }
        if (first < j)
            swaps += iterateHoare (arr, first, j);
        if (i < last)
            swaps += iterateHoare (arr, i, last);
        return swaps;
    }
    
 
 
}

В каждом методе Вам интересна переменная swaps, которая показывает количество перестановок
Ну и в главном классе что-то вроде

Java

        Sorter sorter = new Sorter();
        //создаете массивы нужной длины, заполняете значениями
        int[] array20;
        int[] array50;
        ...
 
        // теперь вызываете все методы класса для каждого массива и анализируете swaps
        //обратите внимание, каждый раз массив будет отсортирован, после каждой сортировки создаете его заново
        sorter.bubbleSort(array20);
        sorter.shellSort(array20);
        ...
        ...
        ...
        sorter.hoareSort(array1000);

Добавлено через 1 минуту
Прочитал внимательнее, очевидно, нужен только метод Шелла - sorter.shellSort();

Добавлено через 3 минуты
Ну и здесь рассказали, как рассчитывать время выполнения программы

@JanCover · 10.03.2016, 13:09 **[ТС]**

Спасибо большое за помощь

Добавлено через 22 часа 27 минут
вопрос, а если мне нужна сортировка с конца в начало и сортировка случайным образом, что нужно поменять здесь ??

Pablito · 10.03.2016, 13:11

Не по теме:

Сообщение от JanCover

сортировка случайным образом

=-O

@JanCover · 10.03.2016, 15:27 **[ТС]**

Ну так в задании написано, я тоже не понял о чём это =/

@HOBATOP · 10.03.2016, 15:55

Сообщение от JanCover

в задании написано

в задании написано:

Сообщение от JanCover

Исследовать влияние начальной упорядоченности массива (отсортированный,
отсортированный в обратном порядке, отсортирован случайным образом).

и речь идёт о начальном массиве: если он [начальный массив] упорядочен, упорядочен по-убыванию или не упорядочен (отсортирован - было бы умнее написать "заполнен") хаотически. Вам нужно отследить сколько времени займёт обработка этих исходных массивов и сделать выводы.

@JanCover · 10.03.2016, 16:00 **[ТС]**

аааа, дошло, спасибо =)

@BRcr · 10.03.2016, 22:22

Комментарий модератора

JanCover, не дублируйте темы, будьте так добры.

@JanCover · 14.03.2016, 11:16 **[ТС]**

А что нужно поменять в этом коде, что бы сортировка проходила с конца в начало ??
То есть наоборот =)

@JanCover · 15.03.2016, 11:44 **[ТС]**

Java

public class Sorter {
  
    //сортировка методом Шелла
    public void shellSort(int[] arr) {
        int swaps = 0;
        int dim1 = 9;
        int dim2 = 6;
        int dim3 = 3;
        //first iteration
        for (int i = 0; i < arr.length - dim1; i++) {
            for (int j = i + dim1; j < arr.length; j += dim1) {
                if (j < arr.length) if (arr[i] > arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
        //second iteration
        for (int i = 0; i < arr.length - dim2; i++) {
            for (int j = i + dim2; j < arr.length; j += dim2) {
                if (j < arr.length) if (arr[i] > arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
        //third iteration
        for (int i = 0; i < arr.length - dim3; i++) {
            for (int j = i + dim3; j < arr.length; j += dim3) {
                if (j < arr.length) if (arr[i] > arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
        //final iteration
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    int x = arr[i];
                    arr[i] = arr[j];
                    arr[j] = x;
                    swaps++;
                }
            }
        }
 
 
        System.out.println("Sorting by Shell Methods:");
        for (int anArr : arr) {
            System.out.print(anArr + " ");
        }
        System.out.println("\nSwaps by this methods: " + swaps);
    }
 
    public void hoareSort(int[] arr) {
        int swaps = 0;
        swaps = iterateHoare(arr, 0, arr.length-1);
 
        System.out.println("Sorting by Hoare Methods:");
        for (int anArr : arr) {
            System.out.print(anArr + " ");
        }
        System.out.println("\nSwaps by this methods: " + swaps);
    }
  
 
}

Как сделать эту сортировку в обратном порядке, что бы из сортировало не от меньшего к большему, а от большего к меньшему ?

@RedPatrick · 15.03.2016, 13:35

JanCover, хм, особо не вникая - в arr[i] < arr[j] значки больше на меньше везде заменить получится?

@JanCover 0 / 0 / 0 Регистрация: 12.11.2015 Сообщений: 56
		1
	Алгоритмы внутренней сортировки 09.03.2016, 13:23. Показов 775. Ответов 10 Метки нет (Все метки) Приветствую братцы, прошу вас о помощи в одном не сложном дельце, помогите люди добрые с программой, а именно написанием, коль вам не сложно будет. Очень надо, не могу понять как сделать данное задание. =( ЗАДАНИЕ: 1. Написать программу, реализующую сортировку массива заданным способом (согласно варианту). 2. Сравнить число сравнений (С) и обменов (М) для числовых массивов, содержа- щих различное число элементов (20, 500, 1000, 3000, 5000, 10000), выбираемых слу- чайным образом. Оценить время сортировки. 3. Исследовать влияние начальной упорядоченности массива (отсортированный, отсортированный в обратном порядке, отсортирован случайным образом). 4. Все полученные данные ввести в таблицу 1. Сравнить эффективности сорти- ровки массивов разной размерности и упорядоченности. Сделать выводы. Вариант 9: Сортировка Шелла (ℎ i-1 = 3ℎi + 1: 1,4,13,40,121, … ) Язык программирование в принципе не важен, главное результат =) Миниатюры 0

@JanCover 0 / 0 / 0 Регистрация: 12.11.2015 Сообщений: 56
	10.03.2016, 13:09 [ТС]	3
	Спасибо большое за помощь Добавлено через 22 часа 27 минут вопрос, а если мне нужна сортировка с конца в начало и сортировка случайным образом, что нужно поменять здесь ?? 0

Pablito
	10.03.2016, 13:11 #4
	Не по теме: Сообщение от JanCover сортировка случайным образом =-O 0

@JanCover 0 / 0 / 0 Регистрация: 12.11.2015 Сообщений: 56
	10.03.2016, 15:27 [ТС]	5
	Ну так в задании написано, я тоже не понял о чём это =/ 0

@HOBATOP 323 / 310 / 206 Регистрация: 14.09.2015 Сообщений: 827
	10.03.2016, 15:55	6
	Сообщение от JanCover в задании написано в задании написано: Сообщение от JanCover Исследовать влияние начальной упорядоченности массива (отсортированный, отсортированный в обратном порядке, отсортирован случайным образом). и речь идёт о начальном массиве: если он [начальный массив] упорядочен, упорядочен по-убыванию или не упорядочен (отсортирован - было бы умнее написать "заполнен") хаотически. Вам нужно отследить сколько времени займёт обработка этих исходных массивов и сделать выводы. 0

@JanCover 0 / 0 / 0 Регистрация: 12.11.2015 Сообщений: 56
	10.03.2016, 16:00 [ТС]	7
	аааа, дошло, спасибо =) 0

@JanCover 0 / 0 / 0 Регистрация: 12.11.2015 Сообщений: 56
	14.03.2016, 11:16 [ТС]	9
	А что нужно поменять в этом коде, что бы сортировка проходила с конца в начало ?? То есть наоборот =) 0

@RedPatrick 143 / 115 / 61 Регистрация: 13.01.2016 Сообщений: 305
	15.03.2016, 13:35	11
	JanCover, хм, особо не вникая - в arr[i] < arr[j] значки больше на меньше везде заменить получится? 0

Опции темы