Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

Quick Sort Technique In Data Structure

Loading...

Published in: Data Structures
6,673 Views

The subject of this presentation is Quick Sort Technique. This is one of the critical sorting method in Data Structure.

Prachi G / Nagpur

3 years of teaching experience

Qualification: B.Tech/B.E. (YCCE - 2011)

Teaches: Basic Computer, Computer for official job, MS Office, School Level Computer, Computer Science, Marathi, Mathematics, C / C++, C# (C Sharp), Java And J2EE, Visual Basic, Java Script, PHP And MySQL, Web CMS, Wordpress Training

Contact this Tutor
  1. Quick Sort Technique: By, Miss, Prachi Paunikar Lecturer, CO dept AST, Wardha
  2. Contents: ' Introduction Algorithm ' Process C program with output Efficiency ' Applications
  3. Introduction: ' Fastest algorithm Developed by C,A.R. Hoare Also known as Partition Exchange Sort ' Internal sorting algorithm With time complexity O(n log n) Uses partitioning and recursion technique Makes use of a Pivot element for comparison purpose each time
  4. Stepl Step2 Step3 Algorithm:(partition) ' If n V right of V and all elements Xi
  5. Step4 Step5 Algorithm(Continue): Apply quick sort recursively to a[O] a[j-l] and a[j+l]-----a[n-l] Entire array will thus be sorted by selecting an element A] partitioning the array around V B] recursively sorting the left partition C] recursively sorting the right partition Exit
  6. All] 13 A[O] =Pivot element 13 Process 25 25 A[n-l]
  7. As (13>11) & (311) & (1
  8. As p>q , So Exchange pivot 11 & qth element 1 11 25 25 25 57 57 57 13 13 13
  9. Now, Pivot element 11 is at its final position . All the elements before 11 are smaller than it and all the elements after 11 are greater than it. So, here an array is divided into left and right partitions as follows: 1 Left partition 2 9 3 q 3 11 25 25 Pivot 57 p 13 Right partition 1 Pivot 2 p 57 13 q
  10. Consider, Left Partition Here, p>q ,so the process stops here and also pivot 1 is at its final position
  11. Here, p>q , so the process stops here
  12. 9 3 1 2 2 9 9 3 2 9 pivot 3 3 9 3 Here, p=q, so the process stops .Now, exchange qth element with pivot i.e exchange 3 and 9
  13. N/A
  14. Now, Consider right partition as follows 25 25 25 p 57 13 p 13 13 q 57 q 57 p q Here, pivot 25 is at its correct position and again this right partition is divided into its left sub partition and right sub partition
  15. 13 Left sub 13 partition 13 25 90 25 57 57 90 90 Right sub partition
  16. 13 13 11 11 13 13 25 25 90 90 Here, we get the final result i.e Sorted Array in Ascending Order using Quick Sort
  17. #include #include void qS(int [l,int,int); int partiton(int [l,int,int); void main() int clrscr(); printf("\n Enter size of array:"); scanf("%d" &n); printf("\n Enter %d elements in array:",n), for(i=O;i
  18. void qS(int p,int q) int j; if(p
  19. do if(i
  20. IDE Enter size of aryay:5 Enter 5 elements in appay:85 1 96 100 3 Sorted array is: I 3 85 96 100.
  21. Complexity and Efficiency: Average Case O(n log n) Best Case O(n log n) Worst Case O(n2) Efficiency of Quick sort depends upon the Element that is chosen as the Pivot occurs when Worst case 1. Array is already sorted either in ascending or descending order 2. Left-most element is chosen as Pivot
  22. Advantages & Applications: ' Faster than bubble, selection and insertion sort techniques arrays of small ' Used to sort size, medium size or large size
  23. ????? ??? !

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related PPTs

Upload PPTs

If you have your own PowerPoint Presentations which you think can benefit others, please upload on LearnPick. For each approved PPT you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > PowerPoint Slides > Quick Sort Technique In Data Structure