Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# QUICK SORT

Last Updated on March 30, 2022 by Ria Pathak

Qucik sort.

Hard.

### Problem Statement :

You are given a pointer to the head of a linked list. Now the length of the linked list is N.You are asked to form the linked list and then perform a quick sort on the list.

See original problem statement here

#### Example:

``````1
5
3 2 1 4 5

1 2 3 4 5``````

### EXPLANATION:

In this method the main idea is to swap pointers rather than swaping data.

1. Partition:
Take the last element as the pivot.Traverse through the list and move the node after the tail if it has value greater than the pivot.Else leave it in the same position.

2. QuickSort:

Call partition(),which places the pivot at the right position and returns the pivot.Find the tail node of the left side and recur for left list.Now recur for the right list.

### SOLUTIONS:

```#include &lt;iostream&gt;
#include &lt;cstdio&gt;
using namespace std;

struct Node
{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;

new_node-&gt;data = new_data;

}

void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d ", node-&gt;data);
node = node-&gt;next;
}
printf("\n");
}
struct Node *getTail(struct Node *cur)
{
while (cur != NULL &amp;&amp; cur-&gt;next != NULL)
cur = cur-&gt;next;
return cur;
}
struct Node *partition(struct Node *head, struct Node *end,
struct Node **newHead, struct Node **newEnd)
{
struct Node *pivot = end;
struct Node *prev = NULL, *cur = head, *tail = pivot;
while (cur != pivot)
{
if (cur-&gt;data &lt; pivot-&gt;data)
{

prev = cur;
cur = cur-&gt;next;
}
else
{
if (prev)
prev-&gt;next = cur-&gt;next;
struct Node *tmp = cur-&gt;next;
cur-&gt;next = NULL;
tail-&gt;next = cur;
tail = cur;
cur = tmp;
}
}
(*newEnd) = tail;
return pivot;
}
struct Node *quickSortRecur(struct Node *head, struct Node *end)
{
// base condition

Node *newHead = NULL, *newEnd = NULL;
{
while (tmp-&gt;next != pivot)
tmp = tmp-&gt;next;
tmp-&gt;next = NULL;
tmp-&gt;next = pivot;
}
pivot-&gt;next = quickSortRecur(pivot-&gt;next, newEnd);

}
{
return;
}
int main()
{ int t;cin&gt;&gt;t;
while(t--)
{
int n;cin&gt;&gt;n;
int x[n];
for(int i=0;i&lt;n;i++)cin&gt;&gt;x[i];
struct Node *a = NULL;
for(int i=n-1;i&gt;=0;i--)
push(&amp;a,x[i]);
quickSort(&amp;a);
printList(a);
}
return 0;
}
```
```#include &lt;iostream&gt;
#include &lt;cstdio&gt;
using namespace std;

struct Node
{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node;
new_node=(struct Node *)malloc(sizeof(struct Node));

/* put in the data */
new_node-&gt;data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}
void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d ", node-&gt;data);
node = node-&gt;next;
}
printf("\n");
}
struct Node *getTail(struct Node *cur)
{
while (cur != NULL &amp;&amp; cur-&gt;next != NULL)
cur = cur-&gt;next;
return cur;
}

struct Node *partition(struct Node *head, struct Node *end,
struct Node **newHead, struct Node **newEnd)
{
struct Node *pivot = end;
struct Node *prev = NULL, *cur = head, *tail = pivot;

while (cur != pivot)
{
if (cur-&gt;data &lt; pivot-&gt;data)
{

prev = cur;
cur = cur-&gt;next;
}
else
{
if (prev)
prev-&gt;next = cur-&gt;next;
struct Node *tmp = cur-&gt;next;
cur-&gt;next = NULL;
tail-&gt;next = cur;
tail = cur;
cur = tmp;
}
}
(*newEnd) = tail;

return pivot;
}
struct Node *quickSortRecur(struct Node *head, struct Node *end)
{
// base condition

Node *newHead = NULL, *newEnd = NULL;
{
// Set the node before the pivot node as NULL
while (tmp-&gt;next != pivot)
tmp = tmp-&gt;next;
tmp-&gt;next = NULL;
tmp-&gt;next = pivot;
}
pivot-&gt;next = quickSortRecur(pivot-&gt;next, newEnd);

}
{
return;
}
int main()
{ int t;scanf("%d",&amp;t);
while(t--)
{
int n;scanf("%d",&amp;n);
int x[n];
for(int i=0;i&lt;n;i++)scanf("%d",&amp;x[i]);
struct Node *a = NULL;
for(int i=n-1;i&gt;=0;i--)
push(&amp;a,x[i]);
quickSort(&amp;a);
printList(a);
}
return 0;
}
```
```import java.util.*;
import java.io.*;
class QuickSort
{
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1);
for (int j=low; j&lt;high; j++)
{
if (arr[j] &lt; pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;

return i+1;
}
void sort(int arr[], int low, int high)
{
if (low &lt; high)
{
int pi = partition(arr, low, high);
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}

static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i&lt;n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}

public static void main(String args[])
{ Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- &gt;0 ){
int n = sc.nextInt();
int arr[]=new int[n];
for(int i=0;i&lt;n;i++)
{
arr[i] = sc.nextInt();
}
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
printArray(arr); }
}
}
```

[forminator_quiz id="1813"]

This article tried to discuss the concept of Quick Sort. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.