quick sort

[rithish]

 #include<stdio.h>

void quicksort(int [10],int,int);

int main(){
  int x[20],size,i;

  printf("Enter size of the array: ");
  scanf("%d",&size);

  printf("Enter %d elements: ",size);
  for(i=0;i<size;i++)
    scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("Sorted elements: ");
  for(i=0;i<size;i++)
    printf(" %d",x[i]);

  return 0;
}

void quicksort(int x[],int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

    }
}

hello friends iam learning quick sort currently.so i took the code my doubt is here can we take pivot element randomly???? or is there any rule for tat

[rithish]

and i know about bubble sort .but quick sort is bit different i couldn't understand properly .so please suggest me in which topic should i be strong for learning quick sort

[rithish]

hii decptikon if ur der please give me a task for learning quick sort

[zeroliken]

so i took the code my doubt is here can we take pivot element randomly???? or is >there any rule for tat

choosing the pivot doesn't have too many rules cause in most cases it's found in the middle element of a list or chosen randomly but take note if it's the latter choosing the first or last element will cause a worst-case performance ( O(n^2) if I remember correctly ) for sorted/reverse-sorted data

hii decptikon if ur der please give me a task for learning quick sort

lol looks like someone's gaining fame ;)

[deceptikon]

I think the most common options for choosing a pivot are random and median of three. Ideally you want the pivot to be a perfect median of the current subset being sorted, because that produces an optimal recursive tree.

Give this a read. It's not perfect, but there's more detail in normal people words than the majority of articles I've read.

lol looks like someone's gaining fame ;)

Don't forget infamy too. I think someone started a petition to have me banned earlier today. ;)

[zeroliken]

Don't forget infamy too. I think someone started a petition to have me banned earlier today. ;)

banning an admin!? wth, why would someone want to do that

[deceptikon]

wth, why would someone want to do that

Intimidated by my sheer awesomeness, I suppose. :D

[shashikumar s g]

can i know the time complexity of this program

[deceptikon]

an i know the time complexity of this program

The program you posted? It's a naive quicksort, so the worst case is O(n^2), the average case is O(n log(n)), and the best case is Θ(n log(n)). Optimizations to the pivot selection (or variations such as introsort) are intended to minimize any chance of the worst case.

[rithish]

ok for learning and understanding quick sort easily which is the prequesite knowledge i should have.what r the neccesary things

ritish, I know what you try to ask :) you and me are at same stage. try to calculate inversions in the array. It is a best question to understand merge sort problem. secondly, read a chapter in CLRS book, you will get best from anywhere. thirdly, When you will done with this and want more in quick sort, then do closest pair algorithm. fourthly, You will be master in this step if u have completed these 3 ;) . i have done it and enjoy then.

[np complete]

Go through K & R book's quick sort program. Its short and simple.

[rithish]

ooh deceptikon ur in professional and world class level in c.i dont know even wat is time complexity in c or o(log(n)).iam in basic stage

[rithish]

i have done even paper and pen work here but still its difficult decptikon

[rithish]

@ nitin inversion in array means is like this

int counter = 0;

for(int i = 0; i < n - 1; i++)
{
    for(int j = i+1; j < n; j++)
    {
        if( A[i] > A[j] )
        {
            counter++;
        }
    }
}

right???

[rithish]

hii deceptikon iam waiting for ur reply

[deceptikon]

i dont know even wat is time complexity in c or o(log(n)).

You know, you could explore the site I keep referencing. There's an article on complexity there too.

yes! but it is of order n^2 . but merge sort can do it in nlogn. so try that. I think you are also a big fan of deceptikon. ;) I am too! He is really a nice teacher and though a nice person. ;) I also wait for his replies as just like you. keep it up!

[rithish]

@ nitin wat is that clrs book?? can u send a e-book copy

[deceptikon]

wat is that clrs book??

Introduction to Algorithms.

can u send a e-book copy

As far as I'm aware, there's not a free version. You'll either have to buy it, or acquire a pirated copy from somewhere else as such discussion violates Daniweb's rules.

[rithish]

hii deceptikon actually in quick sort they say its a divide and conquer method but i dont uderstand because we have a single array and we dont split into two different arrays

[deceptikon]

because we have a single array

Yes.

and we dont split into two different arrays

Actually, that's not true. You'll notice that in the naive algorithm, the array is partitioned and then each subarray separated by the pivot gets recursively quicksorted. So conceptually at each recursive call you're sorting a unique array. That those arrays happen to share the same memory as one bigger array is irrelevant to labeling the algorithm as divide and conquer.

As an example, take the array {5, 3, 7, 2, 1, 6, 0}. Assuming a perfect partition, we'd select 3 as the pivot and partition the array into something like {0, 2, 1, 3, 7, 5, 6}. Then the array is subdivided into two smaller arrays: {0, 2, 1}, and {3, 7, 5, 6}. Repeat that process until (at least in the naive algorithm) you have as many subarrays as there are items, and the top level array will be sorted.

Here's the whole process on that set of numbers:

{5, 3, 7, 2, 1, 6, 0}
{0, 2, 1, 3, 7, 5, 6}
{0, 2, 1}{3, 7, 5, 6}
{0, 1, 2}{3, 5, 7, 6}
{0}{1, 2}{3}{5, 7, 6}
   {1}{2}   {5, 6, 7}
            {5}{6, 7}
               {6}{7}

@ritish truly saying, your level is yet not too high coding wise... stop doing these tuff things for time being...first learn divide and conquer, do study and then try to implement. it will be good for you. :)

[shashikumar s g]

any other book same as the introduction to algorithms ,deceptikon

just Do CLRS book. it is god of algorithms. If you read and understand this book, you will be very good in alogrithms. seriuosly, just try.

[deceptikon]

any other book same as the introduction to algorithms ,deceptikon

I used to collect programming books, but I've since cleaned house and sold the majority of them. However, the data structure and algorithm books I still keep on my bookshelf related to C are:

• Algorithms in C (Robert Sedgewick)
  The material is first class, but the code is absolute shit. However, I firmly believe that one can learn a lot by fixing the bugs.

• Practical Algorithms (Andrew Binstock & John Rex)
  I have this one more for the code than anything. It's not great code, but not bad either, and I imagine it would be an informative book for a beginner.

• Practical Algorithms in C++ (Bryan Flamig)
  This is my favorite on algorithms. Great book.

• Practical Data Structures in C++ (Bryan Flamig)
  This is my favorite on data structures. Fantastic book.

• Data Structures and Algorithms in C++ (Adam Drozdek)
  I actually haven't read this one... I had an older version that focused on C and upgraded to the latest edition in C++. I just haven't had the time to work my way through it. But from what I've seen, it's pretty decent.

I'm actually not a huge fan of CLRS, mostly because I don't find its contents inspired at all, which makes reading it boring. But if you're not familiar with the subject, CLRS is definitely the most recommended book.

If you read and understand this book, you will be very good in alogrithms

Actually, I would recommend taking advantage of the web more than books. A good book is a fine way to get started, but searching the vast resources online and learning piecemeal strikes me as a far superior (if slower) method. It's better for pointed searches in my experience, like if you want to learn about a red black tree instead of just data structures in general.

The problem with books is that they're notoriously bad about excluding the most important and difficult parts. One laughable example is balanced tree deletion. I've read only a handful (out of hundreds) of books that actually made an attempt to provide code for balanced tree deletion. The rest leave it as an exercise despite the well known fact that it's both the longest and hardest base functionality algorithm to write.

[rithish]

@ nitin wat u said is true iam not good in programming.but i have seen divide and conquer problem.but i have not seen in a practicl wise

geeksforgeeks.org is another source and if u want a simple learning for algorithms, then try www.coursera.org and register for algortihms course of stanford university.It is damn awesome way to get starting if alsorithms. So leave CLRS , leave everything just start that course. all the best. thanks

[rithish]

@ nitin and @ deceptikon thanks for ur help god bless u with thousand blossoms thanks nitin for www.coursera.org

[rithish]

hii deceptikon for wat reason we are taking time complexity into account????for wat purpose???
bcoz all programmers cant take less steps for finishing an algorithm