Logo

Navigation
  • Home
  • Services
    • ERP Solutions
    • Implementation Solutions
    • Support and Maintenance Solutions
    • Custom Solutions
    • Upgrade Solutions
    • Training and Mentoring
    • Web Solutions
    • Production Support
    • Architecture Designing
    • Independent Validation and Testing Services
    • Infrastructure Management
  • Expertise
    • Microsoft Development Expertise
    • Mobile Development
    • SQL Server Database and BI
    • SAP BI, SAP Hana, SAP BO
    • Oracle and BI
    • Oracle RAC
  • Technical Training
    • Learn Data Management
      • Business Intelligence
      • Data Mining
      • Data Modeling
      • Data Warehousing
      • Disaster Recovery
    • Learn Concepts
      • Application Development
      • Client Server
      • Cloud Computing Tutorials
      • Cluster Computing
      • CRM Tutorial
      • EDI Tutorials
      • ERP Tutorials
      • NLP
      • OOPS
      • Concepts
      • SOA Tutorial
      • Supply Chain
      • Technology Trends
      • UML
      • Virtualization
      • Web 2.0
    • Learn Java
      • JavaScript Tutorial
      • JSP Tutorials
      • J2EE
    • Learn Microsoft
      • MSAS
      • ASP.NET
      • ASP.NET 2.0
      • C Sharp
      • MS Project Training
      • Silverlight
      • SQL Server 2005
      • VB.NET 2005
    • Learn Networking
      • Networking
      • Wireless
    • Learn Oracle
      • Oracle 10g
      • PL/SQL
      • Oracle 11g Tutorials
      • Oracle 9i
      • Oracle Apps
    • Learn Programming
      • Ajax Tutorial
      • C Language
      • C++ Tutorials
      • CSS Tutorial
      • CSS3 Tutorial
      • JavaScript Tutorial
      • jQuery Tutorial
      • MainFrame
      • PHP Tutorial
      • VBScript Tutorial
      • XML Tutorial
    • Learn Software Testing
      • Software Testing Types
      • SQA
      • Testing
  • Career Training
    • Career Improvement
      • Career Articles
      • Certification Articles
      • Conflict Management
      • Core Skills
      • Decision Making
      • Entrepreneurship
      • Goal Setting
      • Life Skills
      • Performance Development
      • Personal Excellence
      • Personality Development
      • Problem Solving
      • Relationship Management
      • Self Confidence
      • Self Supervision
      • Social Networking
      • Strategic Planning
      • Time Management
    • Education Help
      • Career Tracks
      • Essay Writing
      • Internship Tips
      • Online Education
      • Scholarships
      • Student Loans
    • Managerial Skills
      • Business Communication
      • Business Networking
      • Facilitator Skills
      • Managing Change
      • Marketing Management
      • Meeting Management
      • Process Management
      • Project Management
      • Project Management Life Cycle
      • Project Management Process
      • Project Risk Management
      • Relationship Management
      • Task Management
      • Team Building
      • Virtual Team Management
    • Essential Life Skills
      • Anger Management
      • Anxiety Management
      • Attitude Development
      • Coaching and Mentoring
      • Emotional Intelligence
      • Stress Management
      • Positive Thinking
    • Communication Skills
      • Conversation Skills
      • Cross Culture Competence
      • English Vocabulary
      • Listening Skills
      • Public Speaking Skills
      • Questioning Skills
    • Soft Skills
      • Assertive Skills
      • Influence Skills
      • Leadership Skills
      • Memory Skills
      • People Skills
      • Presentation Skills
    • Finding a Job
      • Etiquette Tips
      • Group Discussions
      • HR Interviews
      • Interview Notes
      • Job Search Tips
      • Resume Tips
      • Sample Resumes
 

C Algorithms – Quick Sort

By Exforsys | on September 13, 2011 |
C Algorithms

Quick sort is a comparison sort developed by Tony Hoare. Also, like merge sort, it is a divide and conquer algorithm, and just like merge sort, it uses recursion to sort the lists. It uses a pivot chosen by the programmer, and passes through the sorting list and on a certain condition, it sorts the data set.

How it works:

A pivot is chosen from the elements of the data set. The list must be reordered in such a way that the elements with the value less than the pivot come before it and the ones that are greater come after it. This is called the partition operation, and after this was completed, the pivot is in its final position, then, recursively, sort the rest of the elements.

Step by step example :

Having the following list, let’s try to use quick sort to arrange the numbers from lowest to greatest:

Unsorted list:

6 1 4 9 0 3 5 2 7 8

We go from START to END, with the pivot being the first element 6, and let us hide it. :

8 1 4 9 0 3 5 2 7 6
i               j  

Now we scan with i and j. We have to find with i the first value greater than the pivot and with j the first value lower than the pivot. We found that the first value greater than the pivot is 8, and we are still looking for the first value lower than the pivot :

8 1 4 9 0 3 5 2 7 6
i               j  
8 1 4 9 0 3 5 2 7 6
i             j    

We found with j the number 2 which is lower than the pivot, so now we swap the elements pointed by i with j:

2 1 4 9 0 3 5 8 7 6
i             j    

Now, we look again for greater values than the pivot with i:

2 1 4 9 0 3 5 8 7 6
      i       j    

We found the element of 9 which is greater. Now we seek an element lower with j:

2 1 4 9 0 3 5 8 7 6
      i     j      

We found 5. Now we swap them:

2 1 4 5 0 3 9 8 7 6
      i     j      

We begin the search again, but this time, the index i passes over the index j, so this means at the position where i is the index is the proper place for the pivot, and we swap the value of the pivot with the value that is currently there:

2 1 4 5 0 3 9 8 7 6
          j i      
2 1 4 5 0 3 6 8 7 9
          j i      

If you look closely, all the elements before 6 are smaller and all the elements after the former pivot are greater. Now, we split the initial list into two smaller lists according to the former pivot: 2, 1, 4, 5, 0, 3 and 8, 7, 9. We repeat the same procedure for each of the sub-lists. The pivot will be the first element in each case, and when the proper place for the pivot was discovered and moved in accordance to this, again we split the list into two smaller ones using the same rule: one list will be composed by the elements smaller than the pivot and the next list composed by elements greater than the pivot. By the end, the initial list will be put together and it will be sorted.

Sample code:

  1.  #include < iostream >
  2. using namespace std;
  3. void swap(int &a,int &b)
  4. {
  5. 	int aux;
  6. 	aux = a;
  7. 	a = b;
  8. 	b = aux;
  9. }
  10. int partition (int *a, int low,int high)
  11. {
  12. 	int l = low;
  13. 	int h = high;
  14. 	int x = a[l];
  15. 	while (l < h)
  16. 	{
  17. 		while ((a[l] <= x) && (l <= high))
  18. 			l++;
  19. 		while ((a[h] > x) && (h >= low))
  20. 			h--;
  21. 		if (l < h)
  22. 			swap(a[l], a[h]);
  23. 	}
  24. 	swap(a[low], a[h]);
  25. 	return h;
  26. }
  27.  
  28. void QuickSort (int *a, int low, int high)
  29. {
  30. 	int k;
  31. 	if (high > low)
  32. 	{
  33. 		k = partition(a, low, high);
  34. 		QuickSort(a, low, k-1);
  35. 		QuickSort(a, k+1, high);
  36. 	}
  37. }
  38. int main()
  39. {
  40. 	int n;
  41. 	int *a;
  42. 	cout << "Please insert the number of elements to be sorted: ";
  43. 	cin >> n;	// The total number of elements
  44. 	a = (int *)calloc(n, sizeof(int));
  45. 	for(int i=0;i< n;i++)
  46. 	{
  47. 		cout << "Input " << i << " element: ";
  48. 		cin >>a[i]; // Adding the elements to the array
  49. 	}
  50. 	cout << "Unsorted list:" << endl;	// Displaying the unsorted array
  51. 	for(int i=0;i< n;i++)
  52. 	{
  53. 		cout << a[i] << " ";
  54. 	}
  55. 	QuickSort(a, 0, n-1);
  56. 	cout << "nSorted list:" << endl;	// Display the sorted array
  57. 	for(int i=0;i < n;i++)
  58. 	{
  59. 		cout << a[i] << " ";
  60. 	}
  61. 	return 0;
  62. }

Output:

Code explanation:

The partition function does what it is called, it chooses the pivot, then, like in the example, while l is smaller than high (or i smaller than j like in the example) it checks the list for the elements that must be greater or smaller, and when it has found them, a swap function is executed. Then, inside the QuickSort function, after the pivot was found, the list is divided into two smaller lists, according to the pivot, then recursively the partition function is called for each sub-list and in the end the initial list is sorted.

Complexity:

Time

In the best case, the partitions are of equal size at each recursive call, and there are then log2(n) levels of recursive calls. The whole array is scanned at each level of calls, so the total work done is O(N*log(N)).

The average time complexity is also O(N*log(n)).

The worst case time complexity is O(n^2). This occurs when the estimate of the median is systematically always poor, e.g. on already sorted data, but this is very unlikely to happen by chance.

Space

As coded above the best- and average-case space-complexity is O(log(N)), for the stack-space used.

The worst-case space-complexity is O(N), but it can be limited to O(log(N)) if the code is modified so that the smaller half of the array is sorted first (and an explicit stack, or the tail-recursion optimization used).

In that case, the best-case space-complexity becomes O(1) .

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).

Disadvantages:

  • it The worst-case complexity is O(N2);
  • is recursive;

Conclusion:

Commercial applications use Quicksort – generally it runs fast, no additional memory, this compensates for the rare occasions when it runs with O(N2). Never use in applications which require guaranteed response time:

  • Life-critical (medical monitoring, life support in aircraft and space craft)
  • Mission-critical (monitoring and control in industrial and research plants handling dangerous materials, control for aircraft, defense, etc)

unless you assume the worst-case response time.

« « What is Exploratory Testing
C Algorithms – Bucket Sort » »

Author Description

Avatar

Editorial Team at Exforsys is a team of IT Consulting and Training team led by Chandra Vennapoosa.

Free Training

RSSSubscribe 394 Followers
  • Popular
  • Recent
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Bubble Sort

    September 9, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Shell Sort

    September 10, 2011 - 0 Comment
  • C Algorithms – The Problem of Sorting the Elements

    September 8, 2011 - 0 Comment
  • C Algorithms – Radix Sort

    September 10, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Dijkstra’s Algorithm

    September 17, 2011 - 0 Comment
  • C Algorithms – Breadth-First Search (BFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Depth-First Search (DFS)

    September 16, 2011 - 0 Comment
  • C Algorithms – Topological Sort

    September 15, 2011 - 0 Comment
  • C Algorithms – Graph Theory

    September 15, 2011 - 0 Comment
  • C Algorithms – Gnome Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Comb Sort

    September 14, 2011 - 0 Comment
  • C Algorithms – Bucket Sort

    September 13, 2011 - 0 Comment
  • C Algorithms – Counting Sort

    September 12, 2011 - 0 Comment
  • C Algorithms – Merge Sort

    September 12, 2011 - 0 Comment

Exforsys e-Newsletter

ebook
 

Related Articles

  • C Algorithms – Dijkstra’s Algorithm
  • C Algorithms – Breadth-First Search (BFS)
  • C Algorithms – Depth-First Search (DFS)
  • C Algorithms – Topological Sort
  • C Algorithms – Graph Theory

Latest Articles

  • Project Management Techniques
  • Product Development Best Practices
  • Importance of Quality Data Management
  • How to Maximize Quality Assurance
  • Utilizing Effective Quality Assurance Strategies
  • Sitemap
  • Privacy Policy
  • DMCA
  • Trademark Information
  • Contact Us
© 2023. All Rights Reserved.IT Training and Consulting
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptReject Read More
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT