Page 243 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES
P. 243

Fundamentals of Data Structures




                    Notes                          cout << “Input” << i << “ element: “;
                                                   cin >>a[i]; // Adding the elements to the array
                                           }
                                           cout << “Unsorted list:” << endl;       // Displaying the
                                   unsorted array
                                           for(int i=0; i<n; i++)
                                           {
                                                   cout << a[i] << “ ”;
                                           }
                                           QuickSort(a, 0, n-1);
                                           cout << “nSorted list:” << endl;        // Display the sorted
                                   array
                                           for(int i=0; i<n; i++)
                                           {
                                                   cout << a[i] << “ ”;
                                           }
                                           return 0;
                                   }
                                   The output is shown below:












                                   Source: http://www.exforsys.com/tutorials/c-algorithms/quick-sort.html
                                   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.
                                   Some of the advantages of quick sort are:
                                       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).
                                   Some of the disadvantages of quick sort are:

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









          236                               LOVELY PROFESSIONAL UNIVERSITY
   238   239   240   241   242   243   244   245   246   247   248