# Perform quick sort in doubly linked list

Here given code implementation process.

``````//C Program
//Perform quick sort in doubly linked list
#include <stdio.h>

#include <stdlib.h> //for malloc function

//create structure
struct Node {
int data;
struct Node *next;
struct Node *prev;
};

struct Node *head = NULL, *tail = NULL;

//insert node element of end of linked list
void insert(int value) {

//Create a dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL) {
printf("Memory overflow\n");
} else {
//set data value
node->data = value;
node->next = NULL;
node->prev = NULL;
tail = node;

} else {
node->prev = tail;
tail->next = node;

tail = node;

}
}
}
//display element of Node
void display() {
if (temp == NULL) {
} else {

printf("\n Head to Tail Nodes : \n");
//Traverse doubly linked list from front to rear
while (temp != NULL) {
//print Node value
printf("%3d", temp->data);
temp = temp->next;
}

printf("\n Tail to Head Nodes : \n");

temp = tail;

//Traverse doubly linked list from rear to front
while (temp != NULL) {
//print Node value
printf("%3d", temp->data);
temp = temp->prev;
}
}

}

//Swap two element value in linked list
void swap(struct Node *first, struct Node *second) {

int temp = first->data;
first->data = second->data;
second->data = temp;
}
struct Node *separate(struct Node *front, struct Node *end) {

struct Node *pv = front->prev, *init = front;

while (front && front != end) {
if (front->data <= end->data) {
if (pv == NULL) {
//get first
pv = init;
} else {
pv = pv->next;
}
swap(pv, front);
}
front = front->next;
}
if (pv == NULL) {
pv = init;
} else {
pv = pv->next;
}

swap(pv, end);

return pv;

}
void quick_sort(struct Node *front, struct Node *end) {
if (front == NULL || end == NULL || front == end || front == end->next) {
//base case
return;
} else {
struct Node *pv = separate(front, end);
quick_sort(front, pv->prev);
quick_sort(pv->next, end);
}
}

int main() {

insert(3);
insert(9);
insert(6);
insert(2);
insert(1);
insert(8);
insert(6);
insert(13);
insert(15);
//display all node
display();

printf("\n\n After Sort\n");

display();
return 0;
}```
```

#### Output

`````` Head to Tail Nodes :
3  9  6  2  1  8  6 13 15
15 13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9 13 15
15 13  9  8  6  6  3  2  1``````
``````/*
C++ Program
quick sort in doubly linked list
*/

#include<iostream>

using namespace std;
class Node {
public:
int data;
Node *next;
Node *prev;
Node(int value) {
this->data = value;
this->next = NULL;
this->prev = NULL;
}
};
public:
Node *tail;
this->tail = NULL;
}
void insert(int value) {
Node *node = new Node(value);
if (node == NULL) {
cout << "Memory overflow\n";
return;
}
this->tail = node;
} else {
node->prev = this->tail;
this->tail->next = node;
this->tail = node;
}
}
void display() {
if (temp == NULL) {
return;
}
cout << "\n Head to Tail Nodes : \n";
while (temp != NULL) {
cout << temp->data << "  ";
temp = temp->next;
}
temp = this->tail;
cout << "\n Tail to Head Nodes : \n";
while (temp != NULL) {
cout << temp->data << "  ";
temp = temp->prev;
}
}
void swap(Node *first, Node *second) {
int temp = first->data;
first->data = second->data;
second->data = temp;
}
Node *separate(Node *front, Node *end) {
Node *pv = front->prev, *init = front;
while (front != NULL && front != end) {
if (front->data <= end->data) {
if (pv == NULL) {
pv = init;
} else {
pv = pv->next;
}
this->swap(pv, front);
}
front = front->next;
}
if (pv == NULL) {
pv = init;
} else {
pv = pv->next;
}
this->swap(pv, end);
return pv;
}
void quick_sort(Node *front, Node *end) {
if (front == NULL || end == NULL || front == end || front == end->next) {
return;
} else {
Node *pv = this->separate(front, end);
this->quick_sort(front, pv->prev);
this->quick_sort(pv->next, end);
}
}
};

int main() {
obj.insert(3);
obj.insert(9);
obj.insert(6);
obj.insert(2);
obj.insert(1);
obj.insert(8);
obj.insert(6);
obj.insert(13);
obj.insert(15);
cout << "\nBefore";
obj.display();
cout << "\n\n After Sort\n";
obj.display();
return 0;
}```
```

#### Output

``````Before
3  9  6  2  1  8  6  13  15
15  13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9  13  15
15  13  9  8  6  6  3  2  1``````
``````/*
Java Program
Perform quick sort in doubly linked list

*/
class Node {

public int data;

public Node next;

public Node prev;

public Node(int value) {
//Setup initial values of linked list node
this.data = value;
this.next = null;
this.prev = null;
}
}

public Node tail;

tail = null;
}
public void insert(int value) {
Node node = new Node(value);

if (node == null) {

System.out.print("Memory overflow\n");
return;
}
tail = node;
} else {
node.prev = tail;
tail.next = node;
tail = node;
}
}

public void display() {
if (temp == null) {
return;
}

System.out.print("\n Head to Tail Nodes : \n");

while (temp != null) {
System.out.print(temp.data + "  ");
temp = temp.next;
}

temp = tail;

System.out.print("\n Tail to Head Nodes : \n");

while (temp != null) {
System.out.print(temp.data + "  ");
temp = temp.prev;
}

}
public void swap(Node first, Node second) {
int temp = first.data;
first.data = second.data;
second.data = temp;
}
Node separate(Node front, Node end) {
Node pv = front.prev, init = front;

while (front != null && front != end) {

if (front.data <= end.data) {

if (pv == null) {
pv = init;
} else {
pv = pv.next;
}
swap(pv, front);
}
front = front.next;
}

if (pv == null) {
pv = init;
} else {
pv = pv.next;
}
swap(pv, end);
return pv;
}
void quick_sort(Node front, Node end) {

if (front == null || end == null || front == end || front == end.next) {
return;
} else {
Node pv = separate(front, end);
quick_sort(front, pv.prev);
quick_sort(pv.next, end);
}
}

public static void main(String[] args) {
obj.insert(3);
obj.insert(9);
obj.insert(6);
obj.insert(2);
obj.insert(1);
obj.insert(8);
obj.insert(6);
obj.insert(13);
obj.insert(15);
System.out.print("\nBefore");
obj.display();

System.out.print("\n\n After Sort\n");
obj.display();
}

}```
```

#### Output

``````Before
3  9  6  2  1  8  6  13  15
15  13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9  13  15
15  13  9  8  6  6  3  2  1``````
``````/*
C# Program
Perform quick sort in doubly linked list

*/
using System;
public class Node {

public int data;

public Node next;

public Node prev;

public Node(int value) {
//Setup initial values of linked list node
this.data = value;
this.next = null;
this.prev = null;
}
}

public Node tail;

tail = null;
}
public void insert(int value) {
Node node = new Node(value);

if (node == null) {

Console.Write("Memory overflow\n");
return;
}
tail = node;
} else {
node.prev = tail;
tail.next = node;
tail = node;
}
}

public void display() {
if (temp == null) {
return;
}

Console.Write("\n Head to Tail Nodes : \n");

while (temp != null) {
Console.Write(temp.data + "  ");
temp = temp.next;
}

temp = tail;

Console.Write("\n Tail to Head Nodes : \n");

while (temp != null) {
Console.Write(temp.data + "  ");
temp = temp.prev;
}

}
public void swap(Node first, Node second) {
int temp = first.data;
first.data = second.data;
second.data = temp;
}
Node separate(Node front, Node end) {
Node pv = front.prev, init = front;

while (front != null && front != end) {

if (front.data <= end.data) {

if (pv == null) {
pv = init;
} else {
pv = pv.next;
}
swap(pv, front);
}
front = front.next;
}

if (pv == null) {
pv = init;
} else {
pv = pv.next;
}
swap(pv, end);
return pv;
}
void quick_sort(Node front, Node end) {

if (front == null || end == null || front == end || front == end.next) {
return;
} else {
Node pv = separate(front, end);
quick_sort(front, pv.prev);
quick_sort(pv.next, end);
}
}

public static void Main(String[] args) {
obj.insert(3);
obj.insert(9);
obj.insert(6);
obj.insert(2);
obj.insert(1);
obj.insert(8);
obj.insert(6);
obj.insert(13);
obj.insert(15);
Console.Write("\nBefore");
obj.display();

Console.Write("\n\n After Sort\n");
obj.display();
}

}```
```

#### Output

``````Before
3  9  6  2  1  8  6  13  15
15  13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9  13  15
15  13  9  8  6  6  3  2  1``````
``````# Python 3 Program
# quick sort in doubly linked list

class Node :

def __init__(self, value) :
self.data = value
self.next = None
self.prev = None

def __init__(self) :
self.tail = None

def insert(self, value) :
node = Node(value)
if (node == None) :
print("Memory overflow\n")
return

self.tail = node
else :
node.prev = self.tail
self.tail.next = node
self.tail = node

def display(self) :
if (temp == None) :
return

print("\n Head to Tail Nodes : ")
while (temp != None) :
print(temp.data ,end="  ")
temp = temp.next

temp = self.tail
print("\n Tail to Head Nodes : ")
while (temp != None) :
print(temp.data ,end="  ")
temp = temp.prev

def swap(self, first, second) :
temp = first.data
first.data = second.data
second.data = temp

def separate(self, front, end) :
pv = front.prev
init = front
while (front != None and front != end) :
if (front.data <= end.data) :
if (pv == None) :
pv = init
else :
pv = pv.next

self.swap(pv, front)

front = front.next

if (pv == None) :
pv = init
else :
pv = pv.next

self.swap(pv, end)
return pv

def quick_sort(self, front, end) :
if (front == None or end == None or front == end or front == end.next) :
return
else :
pv = self.separate(front, end)
self.quick_sort(front, pv.prev)
self.quick_sort(pv.next, end)

def main() :
obj.insert(3)
obj.insert(9)
obj.insert(6)
obj.insert(2)
obj.insert(1)
obj.insert(8)
obj.insert(6)
obj.insert(13)
obj.insert(15)
print("\nBefore")
obj.display()
print("\n\n After Sort")
obj.display()

if __name__ == "__main__":
main()```
```

#### Output

``````Before
3  9  6  2  1  8  6  13  15
15  13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9  13  15
15  13  9  8  6  6  3  2  1``````
``````# Ruby Program
# quick sort in doubly linked list

class Node
attr_accessor :data, :next, :prev
def initialize(value)
self.data = value
self.next = nil
self.prev = nil
end
end

def initialize()
@tail = nil
end
def insert(value)
node = Node.new(value)
if (node == nil)
print("Memory overflow\n")
return
end
@tail = node
else
node.prev = @tail
@tail.next = node
@tail = node
end
end
def display()
if (temp == nil)
return
end
print("\n Head to Tail Nodes  :\n")
while (temp != nil)
print(temp.data ,"  ")
temp = temp.next
end
temp = @tail
print("\n Tail to Head Nodes  :\n")
while (temp != nil)
print(temp.data ,"  ")
temp = temp.prev
end
end
def swap(first, second)
temp = first.data
first.data = second.data
second.data = temp
end
def separate(front, last)
pv = front.prev
init = front
while (front != nil and front != last)
if (front.data <= last.data)
if (pv == nil)
pv = init
else
pv = pv.next
end
self.swap(pv, front)
end
front = front.next
end
if (pv == nil)
pv = init
else
pv = pv.next
end
self.swap(pv, last)
return pv
end
def quick_sort(front, last)
if (front == nil or last == nil or front == last or front == last.next)
return
else
pv = self.separate(front, last)
self.quick_sort(front, pv.prev)
self.quick_sort(pv.next, last)
end
end

end

def main()
obj.insert(3)
obj.insert(9)
obj.insert(6)
obj.insert(2)
obj.insert(1)
obj.insert(8)
obj.insert(6)
obj.insert(13)
obj.insert(15)
print("\nBefore")
obj.display()
print("\n\n After Sort\n")
obj.display()
end
main()```
```

#### Output

``````Before
3  9  6  2  1  8  6  13  15
15  13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9  13  15
15  13  9  8  6  6  3  2  1``````
``````<?php
/*
Php Program
quick sort in doubly linked list
*/

class Node {
public \$data;
public \$next;
public \$prev;

function __construct(\$value) {
\$this->data = \$value;
\$this->next = null;
\$this->prev = null;
}
}
public \$tail;

function __construct() {
\$this->tail = null;
}
public  function insert(\$value) {
\$node = new Node(\$value);
if (\$node == null) {
echo("Memory overflow\n");
return;
}
\$this->tail = \$node;
} else {
\$node->prev = \$this->tail;
\$this->tail->next = \$node;
\$this->tail = \$node;
}
}
public  function display() {
if (\$temp == null) {
return;
}
echo("\n Head to Tail Nodes : \n");
while (\$temp != null) {
echo(\$temp->data ."  ");
\$temp = \$temp->next;
}
\$temp = \$this->tail;
echo("\n Tail to Head Nodes : \n");
while (\$temp != null) {
echo(\$temp->data ."  ");
\$temp = \$temp->prev;
}
}
public  function swap(\$first, \$second) {
\$temp = \$first->data;
\$first->data = \$second->data;
\$second->data = \$temp;
}

function separate(\$front, \$end) {
\$pv = \$front->prev;
\$init = \$front;
while (\$front != null && \$front != \$end) {
if (\$front->data <= \$end->data) {
if (\$pv == null) {
\$pv = \$init;
} else {
\$pv = \$pv->next;
}
\$this->swap(\$pv, \$front);
}
\$front = \$front->next;
}
if (\$pv == null) {
\$pv = \$init;
} else {
\$pv = \$pv->next;
}
\$this->swap(\$pv, \$end);
return \$pv;
}

function quick_sort(\$front, \$end) {
if (\$front == null || \$end == null || \$front == \$end || \$front == \$end->next) {
return;
} else {
\$pv = \$this->separate(\$front, \$end);
\$this->quick_sort(\$front, \$pv->prev);
\$this->quick_sort(\$pv->next, \$end);
}
}
}
function main() {
\$obj->insert(3);
\$obj->insert(9);
\$obj->insert(6);
\$obj->insert(2);
\$obj->insert(1);
\$obj->insert(8);
\$obj->insert(6);
\$obj->insert(13);
\$obj->insert(15);
echo("\nBefore");
\$obj->display();
echo("\n\n After Sort\n");
\$obj->display();
}
main();```
```

#### Output

``````Before
3  9  6  2  1  8  6  13  15
15  13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9  13  15
15  13  9  8  6  6  3  2  1``````
``````/*
Node Js Program
quick sort in doubly linked list
*/

class Node {
constructor(value) {
this.data = value;
this.next = null;
this.prev = null;
}
}

constructor() {
this.tail = null;
}
insert(value) {
var node = new Node(value);
if (node == null) {
process.stdout.write("Memory overflow\n");
return;
}
this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
}
display() {
if (temp == null) {
return;
}
process.stdout.write("\n Head to Tail Nodes : \n");
while (temp != null) {
process.stdout.write(temp.data + "  ");
temp = temp.next;
}
temp = this.tail;
process.stdout.write("\n Tail to Head Nodes : \n");
while (temp != null) {
process.stdout.write(temp.data + "  ");
temp = temp.prev;
}
}
swap(first, second) {
var temp = first.data;
first.data = second.data;
second.data = temp;
}
separate(front, end) {
var pv = front.prev;
var init = front;
while (front != null && front != end) {
if (front.data <= end.data) {
if (pv == null) {
pv = init;
} else {
pv = pv.next;
}
this.swap(pv, front);
}
front = front.next;
}
if (pv == null) {
pv = init;
} else {
pv = pv.next;
}
this.swap(pv, end);
return pv;
}
quick_sort(front, end) {
if (front == null || end == null || front == end || front == end.next) {
return;
} else {
var pv = this.separate(front, end);
this.quick_sort(front, pv.prev);
this.quick_sort(pv.next, end);
}
}
}

function main() {
obj.insert(3);
obj.insert(9);
obj.insert(6);
obj.insert(2);
obj.insert(1);
obj.insert(8);
obj.insert(6);
obj.insert(13);
obj.insert(15);
process.stdout.write("\nBefore");
obj.display();
process.stdout.write("\n\n After Sort\n");
obj.display();
}

main();```
```

#### Output

``````Before
3  9  6  2  1  8  6  13  15
15  13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9  13  15
15  13  9  8  6  6  3  2  1``````
``````/*
Swift 4 Program
quick sort in doubly linked list
*/

class Node {
var data: Int;
var next: Node? ;
var prev: Node? ;
init(_ value: Int) {
self.data = value;
self.next = nil;
self.prev = nil;
}
}
var tail: Node? ;
init() {
self.tail = nil;
}
func insert(_ value: Int) {
let node: Node? = Node(value);
if (node == nil) {
print("Memory overflow\n");
return;
}
self.tail = node;
} else {
node!.prev = self.tail;
self.tail!.next = node;
self.tail = node;
}
}
func display() {
if (temp == nil) {
return;
}
print("\n Head to Tail Nodes : ");
while (temp != nil) {
print(temp!.data ,terminator:"  ");
temp = temp!.next;
}
temp = self.tail;
print("\n Tail to Head Nodes : ");
while (temp != nil) {
print(temp!.data ,terminator:"  ");
temp = temp!.prev;
}
}
func swap(_ first: Node? , _ second : Node? ) {
let temp: Int = first!.data;
first!.data = second!.data;
second!.data = temp;
}
func separate(_ front: Node? , _ end : Node? ) -> Node? {
var pv: Node? = front!.prev;

var local_front:Node? = front;
while (local_front != nil && !(local_front === end)) {
if (local_front!.data <= end!.data) {
if (pv == nil) {
pv = front;
} else {
pv = pv!.next;
}
self.swap(pv, local_front);
}
local_front = local_front!.next;
}
if (pv == nil) {
pv = front;
} else {
pv = pv!.next;
}
self.swap(pv, end);
return pv;
}
func quick_sort(_ front: Node? , _ end : Node? ) {
if (front == nil || end == nil || front === end || front === end!.next) {
return;
} else {
let pv: Node? = self.separate(front, end);
self.quick_sort(front, pv!.prev);
self.quick_sort(pv!.next, end);
}
}
}
func main() {
obj.insert(3);
obj.insert(9);
obj.insert(6);
obj.insert(2);
obj.insert(1);
obj.insert(8);
obj.insert(6);
obj.insert(13);
obj.insert(15);
print("\nBefore");
obj.display();
print("\n\n After Sort");
obj.display();
}
main();```
```

#### Output

``````Before
3  9  6  2  1  8  6  13  15
15  13  6  8  1  2  6  9  3

After Sort

1  2  3  6  6  8  9  13  15
15  13  9  8  6  6  3  2  1``````

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.