Сортировка прядей - Strand sort

Анимация сортировки цепочек

Сортировка прядей это рекурсивный алгоритм сортировки который сортирует элементы списка в порядке возрастания. Она имеет О (п2) наихудшая временная сложность, которая возникает при обратной сортировке входного списка.[1] Это лучший случай временная сложность of O (n), которое происходит, когда входные данные являются уже отсортированным списком.[2] Сортировка прядей не на месте поскольку его пространственная сложность равна O (n).[1]

Алгоритм сначала перемещает первый элемент списка в подсписок.[1] Затем он сравнивает последний элемент в подсписке с каждым последующим элементом в исходном списке.[1] Как только в исходном списке есть элемент, который больше, чем последний элемент в подсписке, этот элемент удаляется из исходного списка и добавляется в подсписок.[1] Этот процесс продолжается до тех пор, пока последний элемент в подсписке не будет сравнен с остальными элементами в исходном списке.[1] Подсписок затем объединяется в новый список.[1] Повторите этот процесс и объедините все подсписки, пока все элементы не будут отсортированы.[1] Этот алгоритм называется сортировкой цепочек, потому что в несортированных элементах есть цепочки отсортированных элементов, которые удаляются по одному.[1] Этот алгоритм также используется в J Сортировка менее 40 элементов.[3]

Пример

Этот пример основан на описании алгоритма, приведенном в книге, Практики с поддержкой ИТ и новые парадигмы управления.[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 требует большого количества вставок и удалений, при реализации алгоритма лучше всего использовать связанный список.[2] Связанные списки требуют постоянного времени как для вставки, так и для удаления элементов с помощью итераторов. Время прохождения через связанный список напрямую связано с размером ввода списка.[4] Следующая реализация сделана на Java 8 и основана на описании алгоритма из книги, Практики с поддержкой ИТ и новые парадигмы управления.[1]

  1 упаковка strandSort;  2   3 импорт java.util. *;  4   5 общественный учебный класс strandSort {  6 	статический LinkedList<Целое число> solList = новый LinkedList<Целое число>();  7 	статический int k = 0;  8   9 	/** 10 * Это рекурсивный метод Strand Sort. Требуется связанный список 11 * целые числа в качестве параметра. Сначала он проверяет базовый случай, чтобы увидеть, 12 * связанный список пуст. Затем переходит к алгоритму сортировки Strand, пока 13 * связанный список пуст. 14 	 *  15 * @param origList: 16 * связанный список целых чисел 17 	 */ 18 	общественный статический пустота strandSortIterative(LinkedList<Целое число> origList) { 19  20 		// Базовый вариант 21 		если (origList.пусто()) { 22 			возвращаться; 23 		} 24  25 		еще { 26 			// Создаем подсписок и добавляем первый элемент 27 			// Исходный связанный список с подсписком. 28 			// Затем удаляем первый элемент из исходного списка. 29 			LinkedList<Целое число> подсписок = новый LinkedList<Целое число>(); 30 			подсписок.Добавить(origList.getFirst()); 31 			origList.removeFirst(); 32  33 			// Перебираем исходный список, проверяя, есть ли какие-либо элементы 34 			// Больше, чем элемент в подсписке. 35 			int индекс = 0; 36 			за (int j = 0; j < origList.размер(); j++) { 37 				если (origList.получать(j) > подсписок.получать(индекс)) { 38 					подсписок.Добавить(origList.получать(j)); 39 					origList.удалять(j); 40 					j = j - 1; 41 					индекс = индекс + 1; 42 				} 43 			} 44 			// Объединить подсписок в список решений. 45 			// Для этого шага есть два случая / 46 			// Случай 1: первый рекурсивный вызов, добавляем все элементы в 47 			// список решений в последовательном порядке 48 			если (k == 0) { 49 				за (int я = 0; я < подсписок.размер(); я++) { 50  51 					solList.Добавить(подсписок.получать(я)); 52 					k = k + 1; 53 				} 54  55 			} 56  57 			// Случай 2: после первого рекурсивного вызова  58 			// объединить подсписок со списком решений. 59 			// Это работает путем сравнения самого большого элемента в подсписке (который всегда является последним элементом) 60 			// с первым элементом в списке решений.  61 			еще { 62 				int subEnd = подсписок.размер() - 1; 63 				int solStart = 0; 64 				пока (!подсписок.пусто()) { 65  66 					если (подсписок.получать(subEnd) > solList.получать(solStart)) { 67 						solStart++; 68  69 					} еще { 70 						solList.Добавить(solStart, подсписок.получать(subEnd)); 71 						подсписок.удалять(subEnd); 72 						subEnd--; 73 						solStart = 0; 74 					} 75  76 				} 77  78 			} 79  80 			strandSortIterative(origList); 81 		} 82  83 	} 84  85 	общественный статический пустота главный(Нить[] аргументы) { 86 		// Создаем новый связанный список целых чисел 87 		LinkedList<Целое число> origList = новый LinkedList<Целое число>(); 88  89 		// Добавить в связанный список следующие целые числа: {5, 1, 4, 2, 0, 9, 6, 3, 8, 7} 90  91 		origList.Добавить(5); 92 		origList.Добавить(1); 93 		origList.Добавить(4); 94 		origList.Добавить(2); 95 		origList.Добавить(0); 96 		origList.Добавить(9); 97 		origList.Добавить(6); 98 		origList.Добавить(3); 99 		origList.Добавить(8);100 		origList.Добавить(7);101 102 		strandSortIterative(origList);103 		// Распечатываем список решений104 		за (int я = 0; я < solList.размер(); я++) {105 			Система.из.println(solList.получать(я));106 		}107 108 	}109 110 }

Рекомендации

  1. ^ а б c d е ж грамм час я j k ИТ-практики и новые парадигмы управления. Гупта, И.С. (Ишвар Чандра), 1946-, Джаролия, Дипак., Престижный институт менеджмента и исследований. (1-е изд.). Индор: Престижный институт менеджмента и исследований. 2008 г. ISBN  9788174466761. OCLC  641462443.CS1 maint: другие (связь)
  2. ^ а б "сортировка прядей". xlinux.nist.gov. Получено 2018-11-06.
  3. ^ Sudipta., Мукерджи (2008). Структуры данных с использованием C: 1000: проблемы и решения. Нью-Дели: Тата МакГроу-Хилл. ISBN  9780070667655. OCLC  311311576.
  4. ^ "LinkedLists". www.cs.cmu.edu. Получено 2018-11-06.