Quick Sort on Linked List in C++,Java,Python

[Rohith1816]

Is your feature request related to a problem? Please describe. Quick Sort on Linked List is one of the important algorithm which is used to sort the Linked List in a particular pattren

Describe the solution you'd like I will make a function such that when we pass a head of the linked list to that function it return the pointer to the head after sorting the linked list

Additional context Please assign this task to me under SSOC23

[Shanukumar2929]

please assign this issue to me

[mayank2mahi]

@Kumar-laxmi Sir ji please assign me this issue as I eagerly want to contribute to this issue under SSoC'23.

[NupurHardiya]

Hey @Kumar-laxmi !

I hope this message finds you well. I am writing to express my interest in working on the issue "Quick Sort on Linked List" for SSOC'23. I believe this project aligns perfectly with my skills and interests, and I would be thrilled to contribute to it.

My approach will be:-

1. Implement the Node class to represent a node in the linked list. Each node should have a data attribute and a next attribute pointing to the next node.

2. Implement the QuickSortLinkedList class to perform Quick Sort on the linked list.

3. Define the push() method in QuickSortLinkedList class to insert a new node at the beginning of the linked list.

4. Implement the partition() method to choose a pivot element and partition the linked list around the pivot.

• Choose the last node as the pivot.
• Initialize three pointers: pivot_prev, curr, and pivot.
• Traverse the linked list using the curr pointer.
• If the current node's data is less than the pivot's data, swap the data of the current node with the data of pivot_prev node, and move pivot_prev to the next node.
• After traversing the linked list, swap the data of the pivot node with the data of pivot_prev node.
• Return the pivot_prev node as the new pivot position.

5. Implement the quickSortLinkedList() method to recursively perform Quick Sort on the linked list.

• Base case: If the start and end pointers are the same or either of them is None, return.
• Call the partition() method to get the new pivot position.
• Recursively call quickSortLinkedList() for the left sub-list (start to pivot_prev) and right sub-list (pivot_prev.next to end).

6. Implement the getTail() method to get the tail node of the linked list.

• Traverse the linked list until the next pointer is None and return the last node.

• 7. To use the QuickSortLinkedList class, create an instance, add nodes using the push() method, and then call the sort() method to perform Quick Sort on the linked list.

Thank you for considering my request. I look forward to the opportunity to contribute to SSOC'23.

[shivangi2002]

@Kumar-laxmi .Please assign this task to me under SSOC23

[github-actions[bot]]

Stale issue message