Concepts Used

Qucik sort.

Difficulty Level

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 go through some online programming courses and 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 <iostream> 
#include <cstdio> 
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->data = new_data; 
    new_node->next = (*head_ref); 

    (*head_ref) = new_node; 
} 

void printList(struct Node *node) 
{ 
    while (node != NULL) 
    { 
        printf("%d ", node->data); 
        node = node->next; 
    } 
    printf("\n"); 
} 
struct Node *getTail(struct Node *cur) 
{ 
    while (cur != NULL && cur->next != NULL) 
        cur = cur->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->data < pivot->data) 
        { 
            if ((*newHead) == NULL) 
                (*newHead) = cur; 

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

    Node *newHead = NULL, *newEnd = NULL; 
    struct Node *pivot = partition(head, end, &newHead, &newEnd); 
    if (newHead != pivot) 
    { 
        struct Node *tmp = newHead; 
        while (tmp->next != pivot) 
            tmp = tmp->next; 
        tmp->next = NULL; 
        newHead = quickSortRecur(newHead, tmp); 
        tmp = getTail(newHead); 
        tmp->next = pivot; 
    } 
    pivot->next = quickSortRecur(pivot->next, newEnd); 

    return newHead; 
} 
void quickSort(struct Node **headRef) 
{ 
    (*headRef) = quickSortRecur(*headRef, getTail(*headRef)); 
    return; 
} 
int main() 
{ int t;cin>>t;
while(t--)
{
  int n;cin>>n;
  int x[n];
  for(int i=0;i<n;i++)cin>>x[i];
  struct Node *a = NULL; 
  for(int i=n-1;i>=0;i--)
  push(&a,x[i]);
  quickSort(&a);
  printList(a); 
}
    return 0; 
} 
#include <iostream> 
#include <cstdio> 
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->data = new_data; 

    /* link the old list off the new node */
    new_node->next = (*head_ref); 

    /* move the head to point to the new node */
    (*head_ref) = new_node; 
} 
void printList(struct Node *node) 
{ 
    while (node != NULL) 
    { 
        printf("%d ", node->data); 
        node = node->next; 
    } 
    printf("\n"); 
} 
struct Node *getTail(struct Node *cur) 
{ 
    while (cur != NULL && cur->next != NULL) 
        cur = cur->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->data < pivot->data) 
        { 
            if ((*newHead) == NULL) 
                (*newHead) = cur; 

            prev = cur;  
            cur = cur->next; 
        } 
        else 
        { 
            if (prev) 
                prev->next = cur->next; 
            struct Node *tmp = cur->next; 
            cur->next = NULL; 
            tail->next = cur; 
            tail = cur; 
            cur = tmp; 
        } 
    } 
    if ((*newHead) == NULL) 
        (*newHead) = pivot; 
    (*newEnd) = tail; 

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

    Node *newHead = NULL, *newEnd = NULL; 
    struct Node *pivot = partition(head, end, &newHead, &newEnd); 
    if (newHead != pivot) 
    { 
        // Set the node before the pivot node as NULL 
        struct Node *tmp = newHead; 
        while (tmp->next != pivot) 
            tmp = tmp->next; 
        tmp->next = NULL; 
        newHead = quickSortRecur(newHead, tmp); 
        tmp = getTail(newHead); 
        tmp->next = pivot; 
    } 
    pivot->next = quickSortRecur(pivot->next, newEnd); 

    return newHead; 
} 
void quickSort(struct Node **headRef) 
{ 
    (*headRef) = quickSortRecur(*headRef, getTail(*headRef)); 
    return; 
} 
int main() 
{ int t;scanf("%d",&t);
while(t--)
{
  int n;scanf("%d",&n);
  int x[n];
  for(int i=0;i<n;i++)scanf("%d",&x[i]);
  struct Node *a = NULL; 
  for(int i=n-1;i>=0;i--)
  push(&a,x[i]);
  quickSort(&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<high; j++) 
        { 
            if (arr[j] < 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 < 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<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-- >0 ){
            int n = sc.nextInt();
            int arr[]=new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i] = sc.nextInt();
            }
        QuickSort ob = new QuickSort(); 
        ob.sort(arr, 0, n-1); 
        printArray(arr); }
    } 
} 

Previous post MERGE K SORTED LINKED LISTS
Next post FIND PAIR SUM

Leave a Reply

Your email address will not be published. Required fields are marked *