Сортировка прядей
Сортировка нитей — это рекурсивный алгоритм сортировки , который сортирует элементы списка в порядке возрастания. Он имеет O (n 2 ) наихудшая временная сложность, возникающая при обратной сортировке входного списка. [1] В лучшем случае временная сложность O(n) возникает, когда входные данные представляют собой уже отсортированный список. [ нужна ссылка ]
Алгоритм сначала перемещает первый элемент списка в подсписок. [1] Затем он сравнивает последний элемент подсписка с каждым последующим элементом исходного списка. [1] Если в исходном списке есть элемент, превышающий последний элемент в подсписке, этот элемент удаляется из исходного списка и добавляется в подсписок. [1] Этот процесс продолжается до тех пор, пока последний элемент подсписка не сравнится с остальными элементами исходного списка. [1] Затем подсписок объединяется в новый список. [1] Повторите этот процесс и объедините все подсписки, пока все элементы не будут отсортированы. [1] Этот алгоритм называется сортировкой цепочек, поскольку внутри несортированных элементов есть цепочки отсортированных элементов, которые удаляются по одному. [1] Этот алгоритм также используется в J-сортировке для менее 40 элементов. [2]
Пример
[ редактировать ]Этот пример основан на описании алгоритма, представленном в книге IT Enabled Practices and Emerging Management Paradigms . [1]
Шаг 1. Начните со списка чисел: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7 }
Шаг 2. Затем переместите первый элемент списка в новый подсписок: подсписок содержит {5}.
Шаг 3: Затем пройдитесь по исходному списку и сравните каждое число с 5, пока не появится число больше 5.
- 1 < 5, поэтому 1 не добавляется в подсписок.
- 4 < 5, поэтому 4 не добавляется в подсписок.
- 2 < 5, поэтому 2 не добавляется в подсписок.
- 0 < 5, поэтому 0 не добавляется в подсписок.
- 9 > 5, поэтому 9 добавляется в подсписок и удаляется из исходного списка.
Шаг 4: Теперь сравните 9 с остальными элементами исходного списка, пока не будет число больше 9.
- 6 < 9, поэтому 6 не добавляется в подсписок.
- 3 < 9, поэтому 3 не добавляется в подсписок.
- 8 < 9, поэтому 8 не добавляется в подсписок.
- 7 < 9, поэтому 7 не добавляется в подсписок.
Шаг 5: Теперь больше нет элементов для сравнения (9), поэтому объедините подсписок в новый список, называемый списком решений.
После шага 5 исходный список содержит {1, 4, 2, 0, 6, 3, 8, 7}.
Подсписок пуст, а список решений содержит {5, 9}
Шаг 6. Переместите первый элемент исходного списка в подсписок: подсписок содержит {1}
Шаг 7: Переберите исходный список и сравните каждое число с 1, пока не появится число больше 1.
- 4 > 1, поэтому 4 добавляется в подсписок, а 4 удаляется из исходного списка.
Шаг 8: Теперь сравните 4 с остальными элементами исходного списка, пока не будет число больше 4.
- 2 < 4, поэтому 2 не добавляется в подсписок.
- 0 < 4, поэтому 0 не добавляется в подсписок.
- 6 > 4, поэтому 6 добавляется в подсписок и удаляется из исходного списка.
Шаг 9: Теперь сравните 6 с остальными элементами исходного списка, пока не будет число больше 6.
- 3 < 6, поэтому 3 не добавляется в подсписок.
- 8 > 6, поэтому 8 добавляется в подсписок и удаляется из исходного списка.
Шаг 10: Теперь сравните 8 с остальными элементами исходного списка, пока не будет число больше 8.
- 7 < 8, поэтому 7 не добавляется в подсписок.
Шаг 11: Поскольку в исходном списке больше нет элементов для сравнения {8}, подсписок объединяется со списком решений. Теперь исходный список содержит {2, 0, 3, 7}, подсписок пуст, а список решений содержит: {1, 4, 5, 6, 8, 9}.
Шаг 12: Переместите первый элемент исходного списка во подсписок. Подсписок содержит {2}
Шаг 13: Переберите исходный список и сравните каждое число с 2, пока не появится число больше 2.
- 0 < 2, поэтому 0 не добавляется в подсписок.
- 3 > 2, поэтому 3 добавляется в подсписок и удаляется из исходного списка.
Шаг 14: Теперь сравните 3 с остальными элементами исходного списка, пока не будет число больше 3.
- 7 > 3, поэтому 7 добавляется в подсписок и удаляется из исходного списка.
Шаг 15: Поскольку в исходном списке больше нет элементов для сравнения {7}, подсписок объединяется со списком решений. Исходный список теперь содержит {0}, подсписок пуст, а список решений содержит: {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Шаг 16: Переместите первый элемент исходного списка во подсписок. Подсписок содержит {0}.
Шаг 17: Поскольку исходный список теперь пуст, подсписок объединяется со списком решений. Список решений теперь содержит: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. В исходном списке больше нет элементов, и все элементы в списке решений успешно отсортированы в порядке возрастания номеров.
Выполнение
[ редактировать ]Поскольку Strand Sort требует большого количества вставок и удалений, при реализации алгоритма лучше всего использовать связанный список. [3] Связанные списки требуют постоянного времени как для вставки, так и для удаления элементов с помощью итераторов. Время прохождения связанного списка напрямую зависит от входного размера списка. [4] Следующая реализация выполнена на Java 8 и основана на описании алгоритма из книги IT Enabled Practices and Emerging Management Paradigms . [1]
package strandSort;
import java.util.*;
public class strandSort {
static LinkedList<Integer> solList = new LinkedList<Integer>();
static int k = 0;
/**
* This is a recursive Strand Sort method. It takes in a linked list of
* integers as its parameter. It first checks the base case to see if the
* linked list is empty. Then proceeds to the Strand sort algorithm until
* the linked list is empty.
*
* @param origList:
* a linked list of integers
*/
public static void strandSortIterative(LinkedList<Integer> origList) {
// Base Case
if (origList.isEmpty()) {
return;
}
else {
// Create the subList and add the first element of
// The original linked list to the sublist.
// Then remove the first element from the original list.
LinkedList<Integer> subList = new LinkedList<Integer>();
subList.add(origList.getFirst());
origList.removeFirst();
// Iterate through the original list, checking if any elements are
// Greater than the element in the sub list.
int index = 0;
for (int j = 0; j < origList.size(); j++) {
if (origList.get(j) > subList.get(index)) {
subList.add(origList.get(j));
origList.remove(j);
j = j - 1;
index = index + 1;
}
}
// Merge sub-list into solution list.
// There are two cases for this step/
// Case 1: The first recursive call, add all of the elements to the
// solution list in sequential order
if (k == 0) {
for (int i = 0; i < subList.size(); i++) {
solList.add(subList.get(i));
k = k + 1;
}
}
// Case 2: After the first recursive call,
// merge the sub-list with the solution list.
// This works by comparing the greatest element in the sublist (which is always the last element)
// with the first element in the solution list.
else {
int subEnd = subList.size() - 1;
int solStart = 0;
while (!subList.isEmpty()) {
if (subList.get(subEnd) > solList.get(solStart)) {
solStart++;
} else {
solList.add(solStart, subList.get(subEnd));
subList.remove(subEnd);
subEnd--;
solStart = 0;
}
}
}
strandSortIterative(origList);
}
}
public static void main(String[] args) {
// Create a new linked list of Integers
LinkedList<Integer> origList = new LinkedList<Integer>();
// Add the following integers to the linked list: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7}
origList.add(5);
origList.add(1);
origList.add(4);
origList.add(2);
origList.add(0);
origList.add(9);
origList.add(6);
origList.add(3);
origList.add(8);
origList.add(7);
strandSortIterative(origList);
// Print out the solution list
for (int i = 0; i < solList.size(); i++) {
System.out.println(solList.get(i));
}
}
}
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с д и ж г час я дж Практики, основанные на информационных технологиях, и новые парадигмы управления . Гупта, И.С. (Ишвар Чандра), 1946-, Джаролия, Дипак, Престижный институт менеджмента и исследований. (1-е изд.). Индаур: Престижный институт менеджмента и исследований. 2008. ISBN 9788174466761 . OCLC 641462443 .
{{cite book}}: CS1 maint: другие ( ссылка ) - ^ Судипта., Мукерджи (2008). Структуры данных с использованием C:1000 задач и решений . Нью-Дели: Тата МакГроу-Хилл. ISBN 9780070667655 . OCLC 311311576 .
- ^ «сортировка прядей» . xlinux.nist.gov . Проверено 6 ноября 2018 г.
- ^ «Связанные списки» . www.cs.cmu.edu . Проверено 6 ноября 2018 г.