quick sort

[inspire_all]

i recently read that quick sort is most popular algorithm.it has a good efficiency but its not stable.can anyone plz explain me quicksort algorithm in short.i am not able to get it:?:

[WaltP]

Try This

[mike_2000_17]

Quicksort is not really the most popular algorithm for sorting. The most popular algorithm for sorting is whatever sorting function your programming language's standard library provides, that is, if you consider "popular" as what most people use. In C++, we use the std::sort() algorithm (and other sorting-related STL algorithms). And the std::sort() function is probably implemented in a way that is very close to the Introsort algorithm. Quicksort is often cited as a popular method because of the C function qsort() which I doubt is actually a vanilla quicksort implementation, probably also closer to an introsort method.

So, quicksort is the basis for most sorting algorithms implemented in standard libraries. But none actually just use quicksort in its basic or vanilla form because its not stable. The problem is mainly that quicksort has so-called "pathological cases" and plenty of them. This means quicksort is generally fast at O(NlogN) with a low constant factor due to its simplicity, however, its worst-case performance is O(N^2) which tends to occur often (depending on the actual original layout of the values in the array you are sorting, i.e., pathological cases). Because of that, actual implementations have a lot of other safe-guards, micro-optimizations, back-up methods (heap-sort), and things like that to avoid really bad performance in the pathological cases. Then, there are all kinds of additional issues (like minimizing swaps, minimizing comparisons, having better locality of reference, etc.) which complicate the matter even further.

If you want a comprehensive study and benchmarking of sorting algorithms, I suggest you take a look at this page.

As for actually explaining the quicksort algorithm, well, I see no way to do a better job than the wikipedia page for QuickSort, it has pictures, animations, explanations, pseudo-code and real code, what more do you need? I mean the basic idea is simple, you pick a value from the array, then put all the elements smaller than it on one side and all the elements bigger than it on the other, and then you apply the same thing recursively to each sub-array that contains all the smaller and bigger elements, and at the end, you'll get a sorted array. Pathological cases basically occur when you constantly get unlucky in your pick for the pivot value (i.e. if you always pick the largest value as the pivot, you basically have a bubble-sort algorithm, which is horrible). So, better versions of the quicksort algorithm basically just make better choices for pivots and possibly try to detect if things aren't going well (too deep recursion) to switch to a different algorithm altogether.

[inspire_all]

//singly linked list in c++
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#define NULL 0
class node
{
 public:
 int data;
 node *next;
 node()
 {
  next=NULL;
 }
 node(int x)
 {
 data=x;
 next=NULL;
 }
};
class lil           //linked list
{
public:
 node *head;
 lil()
 {
  head=NULL;
 }
 void create();
 void print();
 void search();
 void enqueloc();
 void dequeloc();
 ~lil();

};
void lil::create()
{
int n,x;
node *p;
cout<<"enter no of nodes";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"enter el";
cin>>x;
 if(head==NULL)
 head=p=new node(x);
 else
  {
  p->next=new node(x);
  p=p->next;
  }
 }
}
void lil::print()
{
node *p;
 p=head;
 while(p!=NULL)
 {
  cout<<"<"<<p->data<<">";
  p=p->next;
 }
}
void  lil::search()
{
node *p;
 p=head;
 int i=1,x,flag=0;
 cout<<"enter el u wanna search";
 cin>>x;
 while(p!=NULL)
 {
  if(x==p->data)
  {
  cout<<"element found at location "<<i;
  flag=1;
  break;
  }
  else
  {
  i++;
  p=p->next;
  }
 }
 if(flag==0)
 cout<<"sorry el not found";
}

void lil::enqueloc()
{
int loc,x;
node *q=head;
cout<<"enter el u want to insert";
cin>>x;
cout<<"\nenter loc u want to enter the el";
cin>>loc;
if(loc==1)
{
 node *p=new node(x);
 p->next=q;
 head=p;
}
else
{
for(int i=0;i<loc-2;i++)
 {
  q=q->next;
 }
 node *p=new node(x);
 p->next=q->next;
 q->next=p;
 }
}

void lil::dequeloc()
{
node *p=head,*q=head;
int loc;
cout<<"enter loc at which u want to del el";
cin>>loc;
if(loc==1)
{
 head=head->next;
}
else
 {
 for(int i=0;i<loc-1;i++)
 q=q->next;
 for(i=0;i<loc-2;i++)
 p=p->next;
 p->next=q->next;
 delete q;
 }
}

void lil::quicksort()
{
 node *first=head,*last=head,*up=head,*p=head;
 int pivot=head->data;
 while(last->next!=NULL)
 last=last->next;            //last points to last element
 node *down=last;
 while(p->next->next!=NULL)
 p=p->next;			      //p points to second last el
 while(pivot<=up->data)
 up=up->next;
 while(pivot>down->data)
 down=p->next;
// if(up has not crossed down)
{
 int temp=up->data;
 up->data=down->data;        //exchange the el pted to by up and data
 down->data=temp;
}
//if up has crossed down
//replace  down with pivot

//then call recursively



lil::~lil()
{
 node *q=head;
 node *p=head;
 while(p!=NULL)
 {
  p=q->next;
  delete q;
 }
}

int main()
{
clrscr();
lil l,l1,l2;;
int ch;
 do
{
cout<<"\nmenu::\n1.create\n2.print\n3.insert\n4.search\n5.merge\n6.delete\n7.sort\n8.exit";
cout<<"\nenter ur choice";
cin>>ch;
switch(ch)
{
 case 1: l.create();
	 break;
case 2:
	l.print();
	break;

case 3:
       l.enqueloc();
       break;


case 4:
       l.search();
       break;

case 5:
       l1.create();
       l2.create();
       node *r=l1.head;
       while(r->next!=NULL)
       r=r->next;                   //r pts to last el of lil 1
       r->next=l2.head;
       l.head=l1.head;
       break;

case 6: l.dequeloc();
	break;

case 7:
       
       l.quicksort();
       break;

case 8:
       exit(0);

default:
	cout<<"invalid choice" ;

}
cout<<"\nPRESS ENTER TO CONTINUE";
}
while(getche()==13);
getch();
return 0;
}

plz refer quicksort function and tell me how to complete it
cracked my head but in vain now only u guyz can help