Hello there, I am new to C++.
I have a task from school to make simple sorting program using Insertion Sort with a linked list.
I would like to have comment, feedback, and correction of my code below.

``````#include <iostream>
using namespace std;

struct Sort{
int value;
Sort *next; // Point to the next address on this element
};

int main(){
Sort *anchor; // A "bookmark" for pointer
// Put into anchor everytime we make
// another Sort
// Use this pointer to arrange data
Sort *anchor_temp; // To display the data after arrangement
Sort *actual; // Actual position
int _value = {30, 20, 100, 2, 10, 80};
int temp; // For storing temporary data

anchor = new Sort; // Anchor creating the first element
anchor_temp = anchor;
actual = anchor; // Actual is the same of anchor for the first time
anchor -> value = _value; // Value of first element

// Do the rest of the element
for(int i = 1; i < 6; i ++){
actual -> next = new Sort; // Creating new Sort for next inside
// the struct
actual = actual -> next; // Make the actual is the newest element
actual -> value = _value[i]; // Put a value for each element
}
actual -> next = NULL; // After put lastest value
// next value will be NULL

/** Sorting Algorthm **/
while(anchor -> next != NULL){ // Take two pointer before NULL
temp = anchor -> value; // Put into temporary variable
while(temp > anchor -> next -> value){
anchor -> value = anchor -> next -> value;
anchor -> next -> value = temp;
anchor -> next -> value = anchor -> next -> value;
}
anchor = anchor -> next; // Move to next anchor
}

// Display
while(anchor_temp != NULL){
cout << anchor_temp -> value << endl;
anchor_temp = anchor_temp -> next;
}

return 0;
}
``````

The values that I want to sort is 30, 20, 100, 2, 10, 80, while the result is 20, 30, 2, 10, 80, 100.
So, I would like to know which part I should change in order to get the result of 2, 10, 20, 30, 80, 100.

Thank you.

## All 2 Replies

Not sure about your sorting algorithm. In the algorithm (WikiPedia), it starts from a node right after the first one and compares the node value with the previous node value. In your algorithm, you starts from the head and compares the node value with the next node value...

Simple sort-of-pseudo-code algorithm for array-based insertion sort:

``````SourceArray = {30, 20, 100, 2, 10, 80};
TargetArray = {};
for (i = 0; i < SourceArray.length(); i++)
{
inserted = false;
value = SourceArray[i];
for (j = 0; j < TargetArray.length() && inserted == false; j++)
{
// Check if value is smaller than the current position value.
// If so, then insert and set inserted flag to break out of the loop.
if (TargetArray[j] > value)
{
TargetArray from j move down one position;
TargetArray[j] = value;
inserted = true;
}
}
// Check if not inserted. If so, then add to bottom of TargetArray
if (inserted == false)
{
TargetArray[TargetArray.length()] = value;
}
}
``````

This is an array-based design, not a linked list. The logic is similar, except that a linked-list is simpler, but the algorithms are very much the same. Instead of moving elements down in the array, you would just link in a new node. I'll leave that up to you. In any case, your code is way too complicated. Simplify! Simplify! Simplify!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.