Использование сортировки вставки в односвязном списке
Поэтому у меня есть задание, в котором я даю случайный список чисел, и мне нужно отсортировать их, используя сортировку вставками. Я должен использовать односвязный список. Я осмотрел другие посты, но ни одна из них не помогла. Я понимаю, что такое вставка, но я просто не знаю, как написать это в коде.
Node* insertion_sort(Node* head) {
Node* temp = head_ptr;
while((head->n < temp->n) && (temp != NULL))
temp = temp->next;
head->next = temp->next;
temp->next = head;
head->prev = temp;
}
Я не знаю, правильно ли это или что делать сейчас
Решение
struct node {
int data;
struct node *next;
};void insertion(struct node **head) {
if((*head)== NULL || (*head)->next == NULL) {
return;
}
struct node *t1 = (*head)->next;
while(t1 != NULL) {
int sec_data = t1->data;
int found = 0;
struct node *t2 = *head;
while(t2 != t1) {
if(t2->data > t1->data && found == 0) {
sec_data = t2->data;
t2->data = t1->data;
found = 1;
t2 = t2->next;
} else {
if(found == 1) {
int temp = sec_data;
sec_data = t2->data;
t2->data = temp;
}
t2 = t2->next;
}
}
t2->data = sec_data;
t1 = t1->next;
}
}
Другие решения
Давайте подумаем о том, как работает Insertion Sort: он «разделяет» (теоретически) список на три группы: отсортированное подмножество (которое может быть пустым), текущий элемент и несортированное подмножество (которое может быть пустым). Все до текущего элемента отсортировано. Все после текущего элемента может быть или не быть отсортировано. Алгоритм проверяет ток предмет, сравнивая его со следующим предметом. Помните, что первый элемент после текущего элемента принадлежит несортированному подмножеству.
Предположим, что вы сортируете целые числа в порядке возрастания (поэтому, учитывая «3,1,5,2,4», вы хотите получить «1,2,3,4,5»). Вы устанавливаете текущий элемент на первый элемент в списке. Теперь вы начинаете сортировку:
Если следующий элемент больше текущего, вам не нужно сортировать этот элемент. Просто сделайте это «текущим элементом» и продолжайте.
Если следующий элемент меньше текущего, то у вас есть работа. Сначала сохраните следующий элемент где-нибудь, скажем, в указателе с именем temp, а затем «удалите» следующий элемент из списка, сделав current-> next = current-> next-> next. Теперь вам нужно найти правильное место для удаленного предмета. Вы можете сделать это двумя способами:
- Либо начните с начала списка, двигаясь вперед, пока не найдете правильную позицию. Как только вы это сделаете, вы вставляете элемент туда и продолжаете сортировку вставки. Это самое простое решение, если у вас есть односвязный список.
- Вы идете назад, пока не найдете правильное место для предмета. Как только вы это сделаете, вы вставляете элемент туда и продолжаете сортировку вставки. Это немного сложнее, но может хорошо работать, если у вас есть двусвязный список.
Вы продолжаете этот процесс, пока не достигнете конца списка. Как только вы дойдете до него, вы узнаете, что завершили сортировку вставкой, и список находится в правильном порядке сортировки.
Надеюсь, это поможет.
Подумайте об этом — если список пуст, temp изначально будет NULLтак что вы получите неопределенное поведение, когда вы делаете temp->next = head;,
Попробуйте отладку, это наверняка поможет. Вы, вероятно, либо захотите сохранить предыдущий узел, так что вы можете вставить его позже или посмотреть на 2 узла вперед.
Вот Java-реализация сортировки вставок в связанном списке:
- Сложность времени: O (n ^ 2)
- Сложность пространства: O (1) — сортировка вставкой — алгоритм сортировки по месту
class Solution
{
public ListNode insertionSortList(ListNode head)
{
// Initialize partially sorted list
ListNode dummy = new ListNode(0), prev = dummy, current = head;
while(current != null)
{
if(prev.val > current.val)
prev = dummy;
// Find the right place to insert current node
while(prev.next != null && prev.next.val < current.val)
prev = prev.next;
// Insert current between prev and prev.next
ListNode nextNode = current.next;
current.next = prev.next;
prev.next = current;
current = nextNode;
}
return dummy.next;
}
}
void linked_list::insertion_sort() {
node * p = head;
node * currentNode = head->next; // The node that is being compared at the moment.
node * previousNode = head; // The node previous to the node being compared at the moment.
//We can return from the sorting if the length of the linked list is less than 2.
if (p == nullptr || p->next == nullptr) {
return;
}
while (currentNode != nullptr) {
//If the current node is larger than or equal to the largest element of the sorted linked list on the left, we can move to the next element.
//Helpful for an already sorted array.
if(previousNode->value<=currentNode->value){
currentNode = currentNode->next;
previousNode = previousNode->next;
}
else{
//If the element is the smaller than the head element we need to take care of the head element.
if (head->value > currentNode->value) {
previousNode->next = currentNode->next;
currentNode->next = head;
head = currentNode;
}else {
p = head;
while (p->next != NULL && p->next->value < currentNode->value) {
p = p->next;
}
previousNode->next = currentNode->next;
currentNode->next = p->next;
p->next = currentNode;
}
}
currentNode = previousNode->next;
}
}
detector