A few recommendations for Data Structures and Algorithms: Basic Sorting and Searching Algorithms for Arrays, at a glance
To go through the C program / source-code, scroll down to the end of this pageQuick SortQuick Sort is divide and conquer algorithm like Merge Sort. Unlike Merge Sort this does not require extra space. So it sorts in place. Here dividing step is to chose a pivot and partition the array such that all elements less than or equal to pivot are to the left of it and all the elements which are greater than or equal to the pivot are to the right of it. Recursively sort the left and right parts. Algorithm (described in detail in the document for this tutorial)The key to the algorithm is the partition procedure. A 'partition' element is chosen. All elements less than the partition are put in the left half of the array, all elements greater than the partition are placed in the right half of the array. The two halves are sorted independently and recursively. Property:1. Best case performance – When the partitioning produces two regions of size n/2 (where, n is the total number of elements in the list) O(nlgn). 2. Worst case performance - When the partitioning produces one region of size n-1 (where, n is the total number of elements in the list) and other of size 1 O(n2). 3. Average case – O(n(lgn)) 4. It is not stable and uses O(lg(n)) extra space in the worst case. Complete tutorial document with examples : Quick Sort - C Program Source Code#include<stdio.h>
MCQ Quiz: Efficient Sorting Algorithms- Quick sort, Merge Sort, Heap Sort- Check how much you can score!Your score will be e-mailed to the address filled up by you. Related Tutorials :
Visualizing Quick Sort ( A Java Applet Visualization ) :Here's a Java Applet Visualization which might give you a more 'colorful' idea of what happens in Quick Sort. Click here, or on the image beloq to check out a Quick Sort Algorithm - Java Applet Visualization
Testing Zone For Programmers-Try out our online Multiple-Choice-Question tests in Programming and Computer Science! |
Computer Science >