{"id":1811,"date":"2020-06-11T18:18:37","date_gmt":"2020-06-11T18:18:37","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1811"},"modified":"2022-03-30T22:59:48","modified_gmt":"2022-03-30T22:59:48","slug":"quick-sort","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/quick-sort\/","title":{"rendered":"QUICK SORT"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Qucik sort.<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard.<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

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.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Example:<\/h4>\n
1\n5 \n3 2 1 4 5\n\n1 2 3 4 5<\/code><\/pre>\n
EXPLANATION:<\/h3>\n
\n
In this method the main idea is to swap pointers rather than swaping data.<\/p>\n<\/blockquote>\n
    \n
  1. \n
    Partition:<\/strong>
    \nTake 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.<\/p>\n<\/li>\n
  2. \n
    QuickSort:<\/strong><\/p>\n
    \n
    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.<\/p>\n<\/blockquote>\n<\/li>\n<\/ol>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t