Is there another way of doing this program?

Question

I wanted to know if there was any other way of doing the below program. The below program works properly, but it's kind of big and cluttered. If this is the most optimal way of programming this then feel free to leave your solution! I'm always looking for different ways of programming. -Thanks! :)

void processorSort() {

        if (headNode == nullptr) {
            return;
        }

        int end = LLsize() - 1;

        for (int i = 0; i < LLsize(); i++) {

            Node* current = headNode;
            Node* currentsNext = headNode->next;
            Node* currentsNextNext = currentsNext->next;

            for (int j = 0; j < end - i; j++) { 
                if (currentsNextNext->processorID < currentsNext->processorID) { 
          
                    current->next = currentsNextNext; 
                    currentsNext->next = currentsNextNext->next; 
                    currentsNextNext->next = currentsNext; 
                    currentsNext = currentsNextNext; 
                    currentsNextNext = currentsNextNext->next; 

                }

                current = current->next;
                currentsNext = currentsNext->next;
                currentsNextNext = currentsNextNext->next;

            }
        }
    }

Hi, What are you trying to solve here ? Are you tying to implement something like linked list ? If you can provide your question bit more detail I might be able to help you. — VoidA313, Nov 02 '20 at 01:15
Yes, there certainly is a better way to sort a list than your current extremely naive `O(N^2)` algorithm. For linked lists, merge sort is often a good choice and guarantees `O(N.logN)` performance. Being a linked list, you might suffer performance loss due to bad cache locality. It might be faster to copy the list to a `std::vector` or `std::deque` and use quicksort (via `std::sort`). As always, do your own benchmarking if you're concerned about performance. Also read [this](https://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list) — paddy, Nov 02 '20 at 01:16

score 0 · Answer 1 · answered Nov 02 '20 at 01:28

One reason your code looks cluttered is the use of 3 Node pointers in your loop, when all the information can be obtained from the current pointer. Also, the complexity of the code in the inner loop can be reduced by using the appropriate algorithm to re-link the Nodes as needed:

Node* current = headNode;

for (int j = 0; j < end - i; j++) 
{ 
  if (current->next->next->processorID < current->next->processorID) 
  { 
    current->next = std::exchange(current->next->next,
                      std::exchange(current->next->next->next, current->next);
  }
  current = current->next;
}

Your code appears to be doing a bubble-sort on a linked-list. However, your implementation may have bugs for some corner cases, so I suggest writing a bunch of tests to check that. But you can still apply the above suggestions to the code if it needs to be fixed.

Is there another way of doing this program?

1 Answers1