Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

QuickSort Algorithm

No description
by

bella M

on 2 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of QuickSort Algorithm

Quick Sort is a sorting algorithm. It is also referred as partition exchange sort.
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:
Full transcript