It is a divide and conquer algorithm. Quick sort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quick sort can then recursively sort the sub-lists.

Complexity of Quick sort

In the best/ average case it gives a time complexity of O(n log n) and worst case time complexity of O(n*n).

Quick sort is often faster in practice than other algorithms.

The best case occurs when the partition occurs exactly in the middle of the array and then the left and the right part will have same size.

Worst case occurs when the Minimum or Maximum element is chosen as the pivot.

Average-case.

Quick Sort Algorithm:

* Quick Sorting involves these steps:

Pick an element, called a pivot, from the list.

Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

Recursively apply the above steps to the sub-list of elements with smaller values and separately to the sub-list of elements with greater values.

The base case of the recursion is lists of size zero or one, which never need to be sorted.

Continue ..

void quicksort(int *input, int p, int r) // The quicksort recursive function

{

if ( p < r )

{

int j = partition(input, p, r);

quicksort(input, p, j-1);

quicksort(input, j+1, r);

}

}

int main()

{

int input[INPUT_SIZE] = {50, 70, 80, 10, 30, 20, 90, 40, 60};

cout << "\nInput: ";

print(input);

quicksort(input, 0, 9);

cout << "Output: ";

print(input);

return 0;

}

**Quick Sort Algorithm**

What is Quick Sort Algorithm?

#include <iostream>

using namespace std;

const int INPUT_SIZE = 9;

void print(int *input) // A simple print function

{

for ( int i = 0; i < INPUT_SIZE; i++ )

cout << input[i] << " ";

cout << endl;

}

int partition(int* input, int p, int r) // The partition function

{

int pivot = input[r];

while ( p < r )

{

while ( input[p] < pivot )

p++;

while ( input[r] > pivot )

r--;

if ( input[p] == input[r] )

p++;

else if ( p < r )

{

int tmp = input[p];

input[p] = input[r];

input[r] = tmp;

}

}

return r;

}

Quick Sort Example

Continue ..

Output Result

http://www.csepedia.com/Quick_Sort.html

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

http://www.sourcetricks.com/2011/06/what-is-quick-sort-algorithm-how-to.html

Data Structure Using C++

References ..

Habiba Mohammad ..

Shaymah Hmoud..

Supervision:

Preparation:

Lubna Maqbool ..

Thanks :)

Comparison with heapsort:

both algorithms have O(n logn) complexity.

quicksort runs faster, (does not support a heap tree).

the speed of quick sort is not guaranteed.

Comparison with mergesort:

mergesort guarantees O(n logn) time, however it requires additional memory with size N.

quicksort does not require additional memory, however the speed is not quaranteed

usually mergesort is not used for main memory sorting, only for external memory sorting.

Some Comparisons

Advantages:

One of the fastest algorithms on average.

Does not need additional memory (the sorting takes place in the array - this is called in-place processing). Compare with mergesort: mergesort needs additional memory for merging.

Disadvantages:

The worst-case complexity is O(N2)

Applications:

Commercial applications use Quicksort - generally it runs fast, no additional memory,

Conclusions: