Quicksort on singly linked list
Here given code implementation process.
// C Program
// Quicksort on singly linked list
#include <stdio.h>
//for malloc function
#include <stdlib.h>
//Create structure
struct Node
{
int data;
struct Node *next;
};
//Add new node at end of linked list
void insert(struct Node **head, int value)
{
//Create dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
node->data = value;
node->next = NULL;
if ( *head == NULL)
{
*head = node;
}
else
{
struct Node *temp = *head;
//find last node
while (temp->next != NULL)
{
temp = temp->next;
}
//add node at last possition
temp->next = node;
}
}
}
//Display linked list element
void display(struct Node *head)
{
if (head == NULL)
{
printf("Empty linked list");
return;
}
struct Node *temp = head;
printf("\n Linked List :");
while (temp != NULL)
{
printf(" %d", temp->data);
temp = temp->next;
}
}
//Find last node of linked list
struct Node *last_node(struct Node *head)
{
struct Node *temp = head;
while (temp != NULL && temp->next != NULL)
{
temp = temp->next;
}
return temp;
}
//Set of given last node position to its proper position
struct Node *parition(struct Node *first, struct Node *last)
{
//Get first node of given linked list
struct Node *pivot = first;
struct Node *front = first;
int temp = 0;
while (front != NULL && front != last)
{
if (front->data < last->data)
{
pivot = first;
//Swap node value
temp = first->data;
first->data = front->data;
front->data = temp;
//Visit to next node
first = first->next;
}
//Visit to next node
front = front->next;
}
//Change last node value to current node
temp = first->data;
first->data = last->data;
last->data = temp;
return pivot;
}
//Perform quick sort in given linked list
void quick_sort(struct Node *first, struct Node *last)
{
if (first == last)
{
return;
}
struct Node *pivot = parition(first, last);
if (pivot != NULL && pivot->next != NULL)
{
quick_sort(pivot->next, last);
}
if (pivot != NULL && first != pivot)
{
quick_sort(first, pivot);
}
}
int main()
{
struct Node *head = NULL;
//Create linked list
insert( &head, 41);
insert( &head, 5);
insert( &head, 7);
insert( &head, 22);
insert( &head, 28);
insert( &head, 63);
insert( &head, 4);
insert( &head, 8);
insert( &head, 2);
insert( &head, 11);
printf("\n Before Sort ");
display(head);
quick_sort(head, last_node(head));
printf("\n After Sort ");
display(head);
return 0;
}
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
// Java Program
// Quicksort on singly linked list
//Node of LinkedList
class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
public Node head;
public Node tail;
//Class constructors
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
public void display()
{
if (this.head != null)
{
System.out.print("\n Linked List :");
Node temp = this.head;
while (temp != null)
{
System.out.print(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
System.out.println("Empty Linked List");
}
}
//Find last node of linked list
public Node last_node()
{
Node temp = this.head;
while (temp != null && temp.next != null)
{
temp = temp.next;
}
return temp;
}
//Set of given last node position to its proper position
public Node parition(Node first, Node last)
{
//Get first node of given linked list
Node pivot = first;
Node front = first;
int temp = 0;
while (front != null && front != last)
{
if (front.data < last.data)
{
pivot = first;
//Swap node value
temp = first.data;
first.data = front.data;
front.data = temp;
//Visit to next node
first = first.next;
}
//Visit to next node
front = front.next;
}
//Change last node value to current node
temp = first.data;
first.data = last.data;
last.data = temp;
return pivot;
}
//Perform quick sort in given linked list
public void quick_sort(Node first, Node last)
{
if (first == last)
{
return;
}
//Find pivot node
Node pivot = parition(first, last);
if (pivot != null && pivot.next != null)
{
quick_sort(pivot.next, last);
}
if (pivot != null && first != pivot)
{
quick_sort(first, pivot);
}
}
public static void main(String[] args)
{
MyLinkedList obj = new MyLinkedList();
//Create linked list
obj.insert(41);
obj.insert(5);
obj.insert(7);
obj.insert(22);
obj.insert(28);
obj.insert(63);
obj.insert(4);
obj.insert(8);
obj.insert(2);
obj.insert(11);
System.out.print("\n Before Sort ");
obj.display();
obj.quick_sort(obj.head, obj.last_node());
System.out.print("\n After Sort ");
obj.display();
}
}
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
//Include header file
#include <iostream>
using namespace std;
// C++ Program
// Quicksort on singly linked list
//Node of LinkedList
class Node
{
public: int data;
Node * next;
Node(int data)
{
//set node value
this->data = data;
this->next = NULL;
}
};
class MyLinkedList
{
public: Node * head;
Node * tail;
//Class constructors
MyLinkedList()
{
this->head = NULL;
this->tail = NULL;
}
//insert node at last of linke list
void insert(int value)
{
//Create a node
Node * node = new Node(value);
if (this->head == NULL)
{
//When linked list empty add first node
this->head = node;
this->tail = node;
}
else
{
//Add new node at end of linked list
this->tail->next = node;
this->tail = node;
}
}
//Display linked list nodes
void display()
{
if (this->head != NULL)
{
cout << "\n Linked List :";
Node * temp = this->head;
while (temp != NULL)
{
cout << " " << temp->data;
temp = temp->next;
if (temp == this->head)
{
//avoid loop
return;
}
}
}
else
{
cout << "Empty Linked List";
}
}
//Find last node of linked list
Node * last_node()
{
Node * temp = this->head;
while (temp != NULL && temp->next != NULL)
{
temp = temp->next;
}
return temp;
}
//Set of given last node position to its proper position
Node * parition(Node * first, Node * last)
{
//Get first node of given linked list
Node * pivot = first;
Node * front = first;
int temp = 0;
while (front != NULL && front != last)
{
if (front->data < last->data)
{
pivot = first;
//Swap node value
temp = first->data;
first->data = front->data;
front->data = temp;
//Visit to next node
first = first->next;
}
//Visit to next node
front = front->next;
}
//Change last node value to current node
temp = first->data;
first->data = last->data;
last->data = temp;
return pivot;
}
//Perform quick sort in given linked list
void quick_sort(Node * first, Node * last)
{
if (first == last)
{
return;
}
//Find pivot node
Node * pivot = this->parition(first, last);
if (pivot != NULL && pivot->next != NULL)
{
this->quick_sort(pivot->next, last);
}
if (pivot != NULL && first != pivot)
{
this->quick_sort(first, pivot);
}
}
};
int main()
{
MyLinkedList obj = MyLinkedList();
//Create linked list
obj.insert(41);
obj.insert(5);
obj.insert(7);
obj.insert(22);
obj.insert(28);
obj.insert(63);
obj.insert(4);
obj.insert(8);
obj.insert(2);
obj.insert(11);
cout << "\n Before Sort ";
obj.display();
obj.quick_sort(obj.head, obj.last_node());
cout << "\n After Sort ";
obj.display();
return 0;
}
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
//Include namespace system
using System;
// C# Program
// Quicksort on singly linked list
//Node of LinkedList
class Node
{
public int data;
public Node next;
public Node(int data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
public Node head;
public Node tail;
//Class constructors
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int value)
{
//Create a node
Node node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
public void display()
{
if (this.head != null)
{
Console.Write("\n Linked List :");
Node temp = this.head;
while (temp != null)
{
Console.Write(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
Console.WriteLine("Empty Linked List");
}
}
//Find last node of linked list
public Node last_node()
{
Node temp = this.head;
while (temp != null && temp.next != null)
{
temp = temp.next;
}
return temp;
}
//Set of given last node position to its proper position
public Node parition(Node first, Node last)
{
//Get first node of given linked list
Node pivot = first;
Node front = first;
int temp = 0;
while (front != null && front != last)
{
if (front.data < last.data)
{
pivot = first;
//Swap node value
temp = first.data;
first.data = front.data;
front.data = temp;
//Visit to next node
first = first.next;
}
//Visit to next node
front = front.next;
}
//Change last node value to current node
temp = first.data;
first.data = last.data;
last.data = temp;
return pivot;
}
//Perform quick sort in given linked list
public void quick_sort(Node first, Node last)
{
if (first == last)
{
return;
}
//Find pivot node
Node pivot = parition(first, last);
if (pivot != null && pivot.next != null)
{
quick_sort(pivot.next, last);
}
if (pivot != null && first != pivot)
{
quick_sort(first, pivot);
}
}
public static void Main(String[] args)
{
MyLinkedList obj = new MyLinkedList();
//Create linked list
obj.insert(41);
obj.insert(5);
obj.insert(7);
obj.insert(22);
obj.insert(28);
obj.insert(63);
obj.insert(4);
obj.insert(8);
obj.insert(2);
obj.insert(11);
Console.Write("\n Before Sort ");
obj.display();
obj.quick_sort(obj.head, obj.last_node());
Console.Write("\n After Sort ");
obj.display();
}
}
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
<?php
// Php Program
// Quicksort on singly linked list
//Node of LinkedList
class Node
{
public $data;
public $next;
function __construct($data)
{
//set node value
$this->data = $data;
$this->next = null;
}
}
class MyLinkedList
{
public $head;
public $tail;
//Class constructors
function __construct()
{
$this->head = null;
$this->tail = null;
}
//insert node at last of linke list
public function insert($value)
{
//Create a node
$node = new Node($value);
if ($this->head == null)
{
//When linked list empty add first node
$this->head = $node;
$this->tail = $node;
}
else
{
//Add new node at end of linked list
$this->tail->next = $node;
$this->tail = $node;
}
}
//Display linked list nodes
public function display()
{
if ($this->head != null)
{
echo "\n Linked List :";
$temp = $this->head;
while ($temp != null)
{
echo " ". $temp->data;
$temp = $temp->next;
if ($temp == $this->head)
{
//avoid loop
return;
}
}
}
else
{
echo "Empty Linked List";
}
}
//Find last node of linked list
public function last_node()
{
$temp = $this->head;
while ($temp != null && $temp->next != null)
{
$temp = $temp->next;
}
return $temp;
}
//Set of given last node position to its proper position
public function parition($first, $last)
{
//Get first node of given linked list
$pivot = $first;
$front = $first;
$temp = 0;
while ($front != null && $front != $last)
{
if ($front->data < $last->data)
{
$pivot = $first;
//Swap node value
$temp = $first->data;
$first->data = $front->data;
$front->data = $temp;
//Visit to next node
$first = $first->next;
}
//Visit to next node
$front = $front->next;
}
//Change last node value to current node
$temp = $first->data;
$first->data = $last->data;
$last->data = $temp;
return $pivot;
}
//Perform quick sort in given linked list
public function quick_sort($first, $last)
{
if ($first == $last)
{
return;
}
//Find pivot node
$pivot = $this->parition($first, $last);
if ($pivot != null && $pivot->next != null)
{
$this->quick_sort($pivot->next, $last);
}
if ($pivot != null && $first != $pivot)
{
$this->quick_sort($first, $pivot);
}
}
}
function main()
{
$obj = new MyLinkedList();
//Create linked list
$obj->insert(41);
$obj->insert(5);
$obj->insert(7);
$obj->insert(22);
$obj->insert(28);
$obj->insert(63);
$obj->insert(4);
$obj->insert(8);
$obj->insert(2);
$obj->insert(11);
echo "\n Before Sort ";
$obj->display();
$obj->quick_sort($obj->head, $obj->last_node());
echo "\n After Sort ";
$obj->display();
}
main();
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
// Node Js Program
// Quicksort on singly linked list
//Node of LinkedList
class Node
{
constructor(data)
{
//set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
//Class constructors
constructor()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
insert(value)
{
//Create a node
var node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
display()
{
if (this.head != null)
{
process.stdout.write("\n Linked List :");
var temp = this.head;
while (temp != null)
{
process.stdout.write(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
process.stdout.write("Empty Linked List");
}
}
//Find last node of linked list
last_node()
{
var temp = this.head;
while (temp != null && temp.next != null)
{
temp = temp.next;
}
return temp;
}
//Set of given last node position to its proper position
parition(first, last)
{
//Get first node of given linked list
var pivot = first;
var front = first;
var temp = 0;
while (front != null && front != last)
{
if (front.data < last.data)
{
pivot = first;
//Swap node value
temp = first.data;
first.data = front.data;
front.data = temp;
//Visit to next node
first = first.next;
}
//Visit to next node
front = front.next;
}
//Change last node value to current node
temp = first.data;
first.data = last.data;
last.data = temp;
return pivot;
}
//Perform quick sort in given linked list
quick_sort(first, last)
{
if (first == last)
{
return;
}
//Find pivot node
var pivot = this.parition(first, last);
if (pivot != null && pivot.next != null)
{
this.quick_sort(pivot.next, last);
}
if (pivot != null && first != pivot)
{
this.quick_sort(first, pivot);
}
}
}
function main()
{
var obj = new MyLinkedList();
//Create linked list
obj.insert(41);
obj.insert(5);
obj.insert(7);
obj.insert(22);
obj.insert(28);
obj.insert(63);
obj.insert(4);
obj.insert(8);
obj.insert(2);
obj.insert(11);
process.stdout.write("\n Before Sort ");
obj.display();
obj.quick_sort(obj.head, obj.last_node());
process.stdout.write("\n After Sort ");
obj.display();
}
main();
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
# Python 3 Program
# Quicksort on singly linked list
# Node of LinkedList
class Node :
def __init__(self, data) :
# set node value
self.data = data
self.next = None
class MyLinkedList :
# Class constructors
def __init__(self) :
self.head = None
self.tail = None
# insert node at last of linke list
def insert(self, value) :
# Create a node
node = Node(value)
if (self.head == None) :
# When linked list empty add first node
self.head = node
self.tail = node
else :
# Add new node at end of linked list
self.tail.next = node
self.tail = node
# Display linked list nodes
def display(self) :
if (self.head != None) :
print("\n Linked List :", end = "")
temp = self.head
while (temp != None) :
print(" ", temp.data, end = "")
temp = temp.next
if (temp == self.head) :
# avoid loop
return
else :
print("Empty Linked List", end = "")
# Find last node of linked list
def last_node(self) :
temp = self.head
while (temp != None and temp.next != None) :
temp = temp.next
return temp
# Set of given last node position to its proper position
def parition(self, first, last) :
# Get first node of given linked list
pivot = first
front = first
temp = 0
while (front != None and front != last) :
if (front.data < last.data) :
pivot = first
# Swap node value
temp = first.data
first.data = front.data
front.data = temp
# Visit to next node
first = first.next
# Visit to next node
front = front.next
# Change last node value to current node
temp = first.data
first.data = last.data
last.data = temp
return pivot
# Perform quick sort in given linked list
def quick_sort(self, first, last) :
if (first == last) :
return
# Find pivot node
pivot = self.parition(first, last)
if (pivot != None and pivot.next != None) :
self.quick_sort(pivot.next, last)
if (pivot != None and first != pivot) :
self.quick_sort(first, pivot)
def main() :
obj = MyLinkedList()
# Create linked list
obj.insert(41)
obj.insert(5)
obj.insert(7)
obj.insert(22)
obj.insert(28)
obj.insert(63)
obj.insert(4)
obj.insert(8)
obj.insert(2)
obj.insert(11)
print("\n Before Sort ", end = "")
obj.display()
obj.quick_sort(obj.head, obj.last_node())
print("\n After Sort ", end = "")
obj.display()
if __name__ == "__main__": main()
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
# Ruby Program
# Quicksort on singly linked list
# Node of LinkedList
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
# set node value
self.data = data
self.next = nil
end
end
class MyLinkedList
# Define the accessor and reader of class MyLinkedList
attr_reader :head, :tail
attr_accessor :head, :tail
# Class constructors
def initialize()
self.head = nil
self.tail = nil
end
# insert node at last of linke list
def insert(value)
# Create a node
node = Node.new(value)
if (self.head == nil)
# When linked list empty add first node
self.head = node
self.tail = node
else
# Add new node at end of linked list
self.tail.next = node
self.tail = node
end
end
# Display linked list nodes
def display()
if (self.head != nil)
print("\n Linked List :")
temp = self.head
while (temp != nil)
print(" ", temp.data)
temp = temp.next
if (temp == self.head)
# avoid loop
return
end
end
else
print("Empty Linked List")
end
end
# Find last node of linked list
def last_node()
temp = self.head
while (temp != nil && temp.next != nil)
temp = temp.next
end
return temp
end
# Set of given last node position to its proper position
def parition(first, last)
# Get first node of given linked list
pivot = first
front = first
temp = 0
while (front != nil && front != last)
if (front.data < last.data)
pivot = first
# Swap node value
temp = first.data
first.data = front.data
front.data = temp
# Visit to next node
first = first.next
end
# Visit to next node
front = front.next
end
# Change last node value to current node
temp = first.data
first.data = last.data
last.data = temp
return pivot
end
# Perform quick sort in given linked list
def quick_sort(first, last)
if (first == last)
return
end
# Find pivot node
pivot = self.parition(first, last)
if (pivot != nil && pivot.next != nil)
self.quick_sort(pivot.next, last)
end
if (pivot != nil && first != pivot)
self.quick_sort(first, pivot)
end
end
end
def main()
obj = MyLinkedList.new()
# Create linked list
obj.insert(41)
obj.insert(5)
obj.insert(7)
obj.insert(22)
obj.insert(28)
obj.insert(63)
obj.insert(4)
obj.insert(8)
obj.insert(2)
obj.insert(11)
print("\n Before Sort ")
obj.display()
obj.quick_sort(obj.head, obj.last_node())
print("\n After Sort ")
obj.display()
end
main()
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
// Scala Program
// Quicksort on singly linked list
//Node of LinkedList
class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
class MyLinkedList(var head: Node,
var tail: Node)
{
//Class constructors
def this()
{
this(null, null);
}
//insert node at last of linke list
def insert(value: Int): Unit = {
//Create a node
var node: Node = new Node(value);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list nodes
def display(): Unit = {
if (this.head != null)
{
print("\n Linked List :");
var temp: Node = this.head;
while (temp != null)
{
print(" " + temp.data);
temp = temp.next;
if (temp == this.head)
{
//avoid loop
return;
}
}
}
else
{
print("Empty Linked List");
}
}
//Find last node of linked list
def last_node(): Node = {
var temp: Node = this.head;
while (temp != null && temp.next != null)
{
temp = temp.next;
}
return temp;
}
//Set of given last node position to its proper position
def parition(start: Node, last: Node): Node = {
//Get first node of given linked list
var first: Node = start;
var pivot: Node = first;
var front: Node = first;
var temp: Int = 0;
while (front != null && front != last)
{
if (front.data < last.data)
{
pivot = first;
//Swap node value
temp = first.data;
first.data = front.data;
front.data = temp;
//Visit to next node
first = first.next;
}
//Visit to next node
front = front.next;
}
//Change last node value to current node
temp = first.data;
first.data = last.data;
last.data = temp;
return pivot;
}
//Perform quick sort in given linked list
def quick_sort(first: Node, last: Node): Unit = {
if (first == last)
{
return;
}
//Find pivot node
var pivot: Node = parition(first, last);
if (pivot != null && pivot.next != null)
{
quick_sort(pivot.next, last);
}
if (pivot != null && first != pivot)
{
quick_sort(first, pivot);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyLinkedList = new MyLinkedList();
//Create linked list
obj.insert(41);
obj.insert(5);
obj.insert(7);
obj.insert(22);
obj.insert(28);
obj.insert(63);
obj.insert(4);
obj.insert(8);
obj.insert(2);
obj.insert(11);
print("\n Before Sort ");
obj.display();
obj.quick_sort(obj.head, obj.last_node());
print("\n After Sort ");
obj.display();
}
}
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
// Swift Program
// Quicksort on singly linked list
//Node of LinkedList
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.next = nil;
}
}
class MyLinkedList
{
var head: Node? ;
var tail: Node? ;
//Class constructors
init()
{
self.head = nil;
self.tail = nil;
}
//insert node at last of linke list
func insert(_ value: Int)
{
//Create a node
let node: Node? = Node(value);
if (self.head == nil)
{
//When linked list empty add first node
self.head = node;
self.tail = node;
}
else
{
//Add new node at end of linked list
self.tail!.next = node;
self.tail = node;
}
}
//Display linked list nodes
func display()
{
if (self.head != nil)
{
print("\n Linked List :", terminator: "");
var temp: Node? = self.head;
while (temp != nil)
{
print(" ", temp!.data, terminator: "");
temp = temp!.next;
if (temp === self.head)
{
//avoid loop
return;
}
}
}
else
{
print("Empty Linked List", terminator: "");
}
}
//Find last node of linked list
func last_node() -> Node?
{
var temp: Node? = self.head;
while (temp != nil && temp!.next != nil)
{
temp = temp!.next;
}
return temp;
}
//Set of given last node position to its proper position
func parition(_ start: Node? , _ last : Node? ) -> Node?
{
//Get first node of given linked list
var first: Node? = start;
var pivot: Node? = first;
var front: Node? = first;
var temp: Int = 0;
while (front != nil && !(front === last))
{
if (front!.data < last!.data)
{
pivot = first;
//Swap node value
temp = first!.data;
first!.data = front!.data;
front!.data = temp;
//Visit to next node
first = first!.next;
}
//Visit to next node
front = front!.next;
}
//Change last node value to current node
temp = first!.data;first!.data = last!.data;last!.data = temp;
return pivot;
}
//Perform quick sort in given linked list
func quick_sort(_ first: Node? , _ last : Node? )
{
if (first === last)
{
return;
}
//Find pivot node
let pivot: Node? = self.parition(first, last);
if (pivot != nil && pivot!.next != nil)
{
self.quick_sort(pivot!.next, last);
}
if (pivot != nil && !(first === pivot))
{
self.quick_sort(first, pivot);
}
}
}
func main()
{
let obj: MyLinkedList = MyLinkedList();
//Create linked list
obj.insert(41);
obj.insert(5);
obj.insert(7);
obj.insert(22);
obj.insert(28);
obj.insert(63);
obj.insert(4);
obj.insert(8);
obj.insert(2);
obj.insert(11);
print("\n Before Sort ", terminator: "");
obj.display();
obj.quick_sort(obj.head, obj.last_node());
print("\n After Sort ", terminator: "");
obj.display();
}
main();
Output
Before Sort
Linked List : 41 5 7 22 28 63 4 8 2 11
After Sort
Linked List : 2 4 5 7 8 11 22 28 41 63
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment