quick sort

[tifa farouk]

s=55 50 10 40 80 90 60 100 70 80 20
i want to know how many comparisions are performed by this algorithm using quick sort

[olredixsis]

hmmm... I suggest you to read STL algorithms
http://www.cplusplus.com/reference/algorithm/
Hope this help.

[jsmith]

OP needs to understand how the quicksort algorithm works, then execute the
algorithm by hand, counting the number of comparisons. I would recommend
looking at psuedo-code or at whatever is in OP's notes/textbook instead of
looking at C++ code. Particularly the std::sort() is not all that easy to follow
even for an experienced professional.

[gcampton]

wiki has all the bigO notations.
and to see an illstrated design of how most sorts work you this link was written by the founders of java.

http://people.cs.ubc.ca/~harrison/Java/sorting-demo.html

on average quick sorts compare the whole array about 3 times.
where as something like selection sort will go through number of times for each element but each iteration is reducing for each value already read.

[tifa farouk]

can you learn me how qick sort work in brief

[gcampton]

that website I linked has examples, however they include the code for the animation. so you can remove the animation code, pauses() etc. or just wiki search quicksort.

http://en.wikipedia.org/wiki/Quicksort

there's also a C standard for quicksort called qsort

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));


or: I got this code from the second google link after typing in "C++ quicksort"
the power of googling.... I'm not quite sure what's the deal with line 37, but I'm sure you can figure it out.
-----------------------------------------

void quickSort(int arr[], int left, int right) {

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

 

      /* partition */

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };

 

      /* recursion */

      if (left < j)

            quickSort(arr, left, j);

      if (i < right)

            quickSort(arr, i, right);

}

[gcampton]

looks like a good site:

http://www.algolist.net/Algorithms/Sorting/Quicksort