-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSortListInsertionApp.java
More file actions
169 lines (151 loc) · 7.72 KB
/
SortListInsertionApp.java
File metadata and controls
169 lines (151 loc) · 7.72 KB
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
import java.util.Date;
// listInsertionSort.java
// Применение сортированного списка для сортировки массива
// Запуск программы: C>java ListInsertionSortApp
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
class SortedLink
{
public long dData; // Данные
public SortedLink next; // Следующий элемент списка
// -------------------------------------------------------------Конструктор
public SortedLink(long dd)
{ dData = dd; }
}
class SortedList
{
private SortedLink first; // Ссылка на первый элемент списка
// -------------------------------------------------------------Конструктор (без аргументов)
public SortedList()
{ first = null; } // Инициализация списка
// -------------------------------------------------------------Конструктор (аргумент - массив)
public SortedList(SortedLink[] linkArr)
{
first = null; // Инициализация списка
for(int j=0; j<linkArr.length; j++) // Копирование массива
insert( linkArr[j] ); // в список
}
// -------------------------------------------------------------Вставка (в порядке сортировки)
public void insert(SortedLink k)
{
SortedLink previous = null; // От начала списка
SortedLink current = first; // До конца списка
while(current != null && k.dData > current.dData) // или если ключ > current,
{
previous = current;
current = current.next; // Перейти к следующему элементу
}
if(previous==null) // В начале списка
first = k; // first --> k
else // Не в начале
previous.next = k; // старое значение prev --> k
k.next = current; // k --> старое значение current
}
/*
////////////////////////////////////////////////////////////////////
//-----------------------------------------------------------------Обычная сортировка
public void insertOld(SortedLink[] linkArr) {
int out, in;
SortedLink temp;
// long count=0;
for(out=1; out<linkArr.length; out++){
temp=linkArr[out];
in=out;
while(in>0 && linkArr[in-1].dData>=temp.dData) {
linkArr[in] = linkArr[in-1];
in--;
}
linkArr[in]=temp;
// System.out.println(count);
}
}
//-----------------------------------------------------------------------
/////////////////////////////////////////////////////////////////////////
*/
// -------------------------------------------------------------Возвращает и удаляет первую ссылку
public SortedLink remove()
{ // (assumes non-empty list)
SortedLink temp = first; // Сохранение ссылки
first = first.next; // Удаление первого элемента
return temp; // Метод возвращает ссылку
} // на удаленный элемент
}
////////////////////////////////////////////////////////////////
class SortListInsertionApp
{
public static void main(String[] args)
{
int size = 40000;
// Создание массива
/* SortedLink[] linkArray = new SortedLink[size];
for(int j=0; j<size; j++) // Заполнение массива
{
int n = (int)(java.lang.Math.random()*99); // Случайные числа
SortedLink newLink = new SortedLink(n); // Создание элемента
linkArray[j] = newLink; // Сохранение в массиве
}
*/
Date currentTime = new Date(); //получаем текущее время.
// Создание массива
SortedLink[] linkArray = new SortedLink[size];
for(int j=0; j<size; j++) // Заполнение массива
{
int n = (int)(java.lang.Math.random()*99); // Случайные числа
SortedLink newLink = new SortedLink(n); // Создание элемента
linkArray[j] = newLink; // Сохранение в массиве
}
// Вывод содержимого массива
System.out.print("Unsorted array: ");
for(int j=0; j<size; j++)
System.out.print( linkArray[j].dData + " " );
System.out.println("");
// Создание нового списка,
// инициализированного содержимым массива
SortedList theSortedList = new SortedList(linkArray);
for(int j=0; j<size; j++) // links from list to array
linkArray[j] = theSortedList.remove();
Date newTime = new Date(); //получаем новое текущее время.
long msDelay = newTime.getTime() - currentTime.getTime(); //вычисляем разницу
System.out.println("Длительность сортировки " + msDelay + " мс");
System.out.println("");
// Вывод содержимого массива
System.out.print("Sorted Array: ");
for(int j=0; j<size; j++)
System.out.print(linkArray[j].dData + " ");
System.out.println("");
/*
//////////////////////////////////////////////////////////////////////////////////////////////////
//-----------------------------------------------------------------------обыная сортировка массива
Date currentTime1 = new Date(); //получаем текущее время.
// Создание массива
SortedLink[] linkArray1 = new SortedLink[size];
for(int j=0; j<size; j++) // Заполнение массива
{
int n = (int)(java.lang.Math.random()*99); // Случайные числа
SortedLink newLink = new SortedLink(n); // Создание элемента
linkArray1[j] = newLink; // Сохранение в массиве
}
// Вывод содержимого массива
System.out.print("Unsorted array: ");
for(int j=0; j<size; j++)
System.out.print( linkArray1[j].dData + " " );
System.out.println("");
// Создание нового списка,
// инициализированного содержимым массива
// for(int j=0; j<size; j++) // links from list to array
// linkArray[j] = theSortedList1.remove();
SortedList theSortedList1 = new SortedList();
theSortedList1.insertOld(linkArray1);
Date newTime1 = new Date(); //получаем новое текущее время.
long msDelay1 = newTime1.getTime() - currentTime1.getTime(); //вычисляем разницу
System.out.println("Длительность сортировки " + msDelay1 + " мс");
System.out.println("");
// Вывод содержимого массива
System.out.print("Sorted Array: ");
for(int j=0; j<size; j++)
System.out.print(linkArray1[j].dData + " ");
System.out.println("");
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////
}
}