#include <iostream>
#include <stdlib.h>
struct node {
int item;
node *next;
node(int x, node *t){
item = x;
next = t;
}
};
typedef node *link;
void printList(link list){
while(list != nullptr){
std::cout << list->item << " -> ";
list = list->next;
}
std::cout << "(null)" << std::endl;
}
link getInsertPosition(link sortedList, int valueToSearch);
void insertAfter(link insertPosition, link node);
link generateList(int listLength){
link head = new node(0, nullptr);
link tail = head;
for(int i = 0; i < listLength; i++){
tail->next = new node(rand() % 1000, nullptr);
tail = tail->next;
}
return head;
}
/// @param nonSortedList - несортированный список, с фиктивным узлом вначале
link sortList(link nonSortedList){
link headOfSorted = new node(0, nullptr);
link currentNonSorted = nonSortedList->next;
while(true){
if (currentNonSorted == nullptr){
break;
}
link nextNonSorted = currentNonSorted->next;
link firstGreater = getInsertPosition(headOfSorted, currentNonSorted->item);
insertAfter(firstGreater, currentNonSorted);
currentNonSorted = nextNonSorted;
}
return headOfSorted;
/*
link headOfSorted = new node(0, nullptr);
link nextNonSorted;
for(link currentNonSorted = nonSortedList->next; currentNonSorted != nullptr;){
nextNonSorted = currentNonSorted->next;
link currentSorted;
for(currentSorted = headOfSorted; currentSorted->next != nullptr; currentSorted = currentSorted->next){
if (currentSorted->next->item > currentNonSorted->item) { break; }
}
currentNonSorted->next = currentSorted->next;
currentSorted->next = currentNonSorted;
currentNonSorted = nextNonSorted;
}
return headOfSorted;
*/
}
/// @param sortedList сортированный список, с фиктивным узлом вначале
/// @param valueToSearch - узел для поиска
link getInsertPosition(link sortedList, int valueToSearch){
while(true){
if (sortedList->next == nullptr){
break;
}
if (sortedList->next->item > valueToSearch){
break;
}
sortedList = sortedList->next;
}
return sortedList;
}
void insertAfter(link insertPosition, link node){
node->next = insertPosition->next;
insertPosition->next = node;
}
int main(int argc, char *argv[]){
int listLength = atoi(argv[1]);
link notSortedList = generateList(listLength);
printList(notSortedList);
link sortedList = sortList(notSortedList);
printList(sortedList);
return 0;
}
