Реализация сортировки Timsort

@okeywki · Регистрация: 07.06.2018

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

У меня есть массив размерности 33 , нужно отсортировать его с помощью сортировки Timsort.

@ViktorFX · 30.11.2018, 18:37

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

есть массив размерности 33

Давайте пример вашего массива, а то знаете ли, у меня есть сомнения..

@okeywki · 30.11.2018, 18:48 **[ТС]**

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

Давайте пример вашего массива, а то знаете ли, у меня есть сомнения..

Не правильно указал размерность.Размерность массива 32

Java
1
2
3
4
5
6
7
public static void createArr(){
        int[] array=new int[32];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) Math.round((Math.random() * 32) - 16);
            System.out.println(array[i]);
        }
    }

@TotalUSE · 30.11.2018, 19:45

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Arrays;
 
public class Okeywki {
    private final int[] array = new int[32];
 
    public static void main(String[] args) {
        Okeywki okeywki = new Okeywki();
        okeywki.createArr();
        okeywki.sort();
        okeywki.sout();
 
    }
 
 
    public void createArr() {
        for (int i = 0; i < this.array.length; i++) {
            this.array[i] = (int) Math.round((Math.random() * 32) - 16);
        }
    }
 
    public void sort() {
        Arrays.sort(this.array);
    }
 
    public void sout() {
        for (int i = 0; i < this.array.length; i++) {
            System.out.println(this.array[i]);
        }
    }
}

@okeywki · 30.11.2018, 19:47 **[ТС]**

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Arrays;
public class Okeywki {
* * private final int[] array = new int[32];
public static void main(String[] args) {
* * * * Okeywki okeywki = new Okeywki();
* * * * okeywki.createArr();
* * * * okeywki.sort();
* * * * okeywki.sout();
}
public void createArr() {
* * * * for (int i = 0; i < this.array.length; i++) {
* * * * * * this.array[i] = (int) Math.round((Math.random() * 32) - 16);
* * * * }
* * }
public void sort() {
* * * * Arrays.sort(this.array);
* * }
public void sout() {
* * * * for (int i = 0; i < this.array.length; i++) {
* * * * * * System.out.println(this.array[i]);
* * * * }
* * }
}

Разве это Timsort?

@TotalUSE · 30.11.2018, 19:50

второй вариант метод пузырько наверно он тебе и нужен

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package ru.job4j.forum;
 
import java.util.Arrays;
 
public class Okeywki {
    private final int[] array = new int[32];
 
    public static void main(String[] args) {
        Okeywki okeywki = new Okeywki();
        okeywki.createArr();
        okeywki.sort();
        okeywki.sout();
 
    }
 
 
    public void createArr() {
        for (int i = 0; i < this.array.length; i++) {
            this.array[i] = (int) Math.round((Math.random() * 32) - 16);
        }
    }
 
    public void sort() {
        Integer temp;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                if (array[i] <= array[j]) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
 
    public void sout() {
        for (int i = 0; i < this.array.length; i++) {
            System.out.println(this.array[i]);
        }
    }
}

вот тебе метод с ретурном

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class BubbleSort {
    public int[] sort(int[] array) {
        Integer temp;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                if (array[i] <= array[j]) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

Добавлено через 1 минуту
тайм сорт если память не изменяет это метод пузырьком как последний мой пример

@iSmokeJC · 30.11.2018, 19:51

Реализация Timsort на Джаве

@TotalUSE · 30.11.2018, 22:36

ты должен продемонстрировать ценцею своё логическое мышление

Добавлено через 1 минуту

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

Реализация Timsort на Джаве

ага там ещё и компорейбл поналепили, смысл его использовать в массиве из цифр ?)

Добавлено через 2 часа 42 минуты
Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом[en].
Шаг 1. Входной массив разделяется на подмассивы фиксированной длины, вычисляемой определённым образом.
Шаг 2. Каждый подмассив сортируется сортировкой вставками, сортировкой пузырьком или любой другой устойчивой сортировкой.
Шаг 3. Отсортированные подмассивы объединяются в один массив с помощью модифицированной сортировки слиянием.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
public class Okeywki {
    private final int[] array = new int[32];
    private int[][] sortedMAss;
    private int[] arrayREuLT = new int[0];
    private int index = 0;
    private int index1 = 0;
 
    public static void main(String[] args) {
        Okeywki okeywki = new Okeywki();
        okeywki.init();
        okeywki.sout();
    }
 
    //сгенерируем массив
    Okeywki() {
        for (int i = 0; i < this.array.length; i++) {
            this.array[i] = (int) Math.round((Math.random() * 32) - 16);
            System.out.print(array[i] + ", ");
        }
    }
 
    /**
     * Шаг 2. Каждый подмассив сортируется сортировкой вставками, сортировкой пузырьком или любой другой устойчивой сортировкой.
     *
     * @param mass
     */
    public void sort(int[][] mass) {
        //получим первоу отсортированную строчку
        this.arrayREuLT = this.sortBabl(this.sortedMAss[0]);
        for (int i = 1; i < mass.length; i++) {
            addResult(this.sortBabl(mass[i]));
        }
    }
 
    /**
     * Шаг 1. Входной массив разделяется на подмассивы фиксированной длины, вычисляемой определённым образом.
     */
    private void init() {
        int k = this.array.length / 4;
        this.sortedMAss = new int[4][k];
        for (int i = 0; i < sortedMAss.length; i++) {
            sortedMAss[i] = parseMass(k);
        }
 
        sort(this.sortedMAss);
    }
 
    //метод возвращает подмассивы
    private int[] parseMass(int k) {
        int[] rsl = new int[k];
        for (int j = 0; j < k; j++) {
            rsl[j] = array[index++];
        }
        return rsl;
    }
 
    /**
     * @param arr
     * @return
     */
    private int[] sortBabl(int[] arr) {
        Integer temp;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i] <= arr[j]) {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
 
    /**
     * Шаг 3. Отсортированные подмассивы объединяются в один массив с помощью модифицированной сортировки слиянием.
     *
     * @param mass
     */
    private void addResult(int[] mass) {
        int[] temp = new int[this.arrayREuLT.length + mass.length];
        int n = 0;
        int i = 0;
        int j = 0;
        while (n < temp.length) {
            if (j < mass.length && i < arrayREuLT.length) {
                if (mass[j] < arrayREuLT[i]) {
                    temp[n++] = mass[j++];
                } else if (mass[j] > arrayREuLT[i]) {
                    temp[n++] = arrayREuLT[i++];
                } else if (mass[j] == arrayREuLT[i]) {
                    temp[n++] = mass[j++];
                    temp[n++] = arrayREuLT[i++];
                }
            } else if (j >= mass.length) {
                temp[n++] = arrayREuLT[i++];
            } else {
                temp[n++] = mass[j++];
            }
        }
        this.arrayREuLT = temp;
    }
 
 
    public void sout() {
        for (int i = 0; i < this.arrayREuLT.length; i++) {
            System.out.println(this.arrayREuLT[i]);
        }
    }
}

Добавлено через 1 минуту
ну как то так это вяглядет
результат:

Кликните здесь для просмотра всего текста

0, -12, 14, 4, -10, -9, -5, -6, 14, -4, -10, 2, -1, -9, 16, -11, -1, -9, 6, -1, -4, -3, 13, 2, 2, 7, 0, -2, 14, -13, -15, -5, -15
-13
-12
-11
-10
-10
-9
-9
-9
-6
-5
-5
-4
-4
-3
-2
-1
-1
-1
0
0
2
2
2
4
6
7
13
14
14
14
16

@okeywki · 01.12.2018, 21:10 **[ТС]**

TotalUSE, Спасибо большое, выручили

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@okeywki 0 / 0 / 0 Регистрация: 07.06.2018 Сообщений: 53

	Реализация сортировки Timsort 30.11.2018, 17:58. Показов 4480. Ответов 8 Метки нет (Все метки) У меня есть массив размерности 33 , нужно отсортировать его с помощью сортировки Timsort. 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	30.11.2018, 19:51
	Реализация Timsort на Джаве 0

@okeywki 0 / 0 / 0 Регистрация: 07.06.2018 Сообщений: 53
	01.12.2018, 21:10 [ТС]
	TotalUSE, Спасибо большое, выручили 0

Реализация сортировки Timsort

Решение