Quick Sort

Quick Sort

Quicksort is an in-place sorting algorithm which means it doesn't take an additional array to sort the data. It uses the same array to sort the elements.

Advantages;

• The quick sort is regarded as the best sorting algorithm.
• It is able to deal well with a huge list of items.
• Because it sorts in place, no additional storage is required as well

Disadvantages:

• The slight disadvantage of quick sort is that its worst-case performance is similar to average performances of the bubble, insertion or selections sorts.
• If the list is already sorted than bubble sort is much more efficient than quick sort
• If the sorting element is integers than radix sort is more efficient than quick sort.

Complexity of the Quick Sort Algorithm;

• Data structure: Array
• Worst-case time complexity: O(n2)
• Average-case time complexity Θ(nlogn)
• Best-case time complexity:           Ω(nlogn)
• Worst-case space complexity: O(logn)

CODE:

1. #include <stdio.h>
2. void quicksort(int a[20], int low, int high);
3. int partition(int a[], int low, int high);
4. void main()
5. {
6. int a[20],n,i;
7. printf("How many elements you want to enter \n");
8. scanf("%d", &n);
9. printf("Enter %d elements \t",n);
10. for(i=0; i<n; i++)
11. {
12. scanf("%d", &a[i]);
13. }
14. quicksort(a,0,n-1);
15. printf("Sorted elements are \t");
16. for(i=0; i<n; i++)
17. {
18. printf("%d\t",a[i]);
19. }
20. }
21. void quicksort(int a[20], int low, int high)
22. {
23. int j;
24. if(low<high)
25. {
26. j=partition(a,low,high);
27. quicksort(a,low,j-1);
28. quicksort(a, j+1, high);
29. }
30. }
31. int partition(int a[], int low, int high)
32. {
33. int end,start,temp,pivot;
34. end=high;
35. start=low+1;
36. pivot=a[low];
37. do
38. {
39. while((a[start] <= pivot) && (start < end))
40. start++;
41. while((a[end] > pivot) && (end > low))
42. end--;
43. if(start < end)
44. {
45. temp=a[start];
46. a[start]=a[end];
47. a[end]=temp;
48. }
49. }while(start<end);
50. a[low]=a[end];
51. a[end]=pivot;
52. return end;
53. }

//Execute

//Output

/*

How many elements you want to enter 

5

Enter 5 elements  78

41

54

67

84

Sorted elements are  41 54 67 78 84

*/

EXPLANATION:

- The code is a function that takes an array of integers and sorts them.

- The code starts by declaring the variables it will use, then declares the quicksort function which is defined in line 3.

- Line 4 defines what happens if low < high, which is to call partition(a,low,high) with low as the first parameter and high as the second parameter.

- Then lines 5-7 define what happens if high > low, which is to call partition(a,low+1,high).

- Lines 8-9 define what happens when start <= pivot (which means start is less than or equal to pivot), so line 10 sets up a while loop that goes through each element from start until end (line 11).

- Line 12 sets up another while loop that goes through each element from end until start (line 13).

- Line 14 sets up a do/while loop where line 15 checks whether both loops are true before continuing on with whatever else needs to happen in this part of the program.

- The main() function begins by asking for how many elements you want enter using printf("How many elements you want to enter \n"); followed by scanning those values into n using scanf("%d", &n); followed then printing out "Enter.

                                                                                                                                  //ThE ProFessoR