Explain the characteristics of the performance of sorting algorithm, discuss quick sort algorithm.
Answer: – The fundamental knowledge necessary to solve problem using a computer is the notation of an algorithm. An algorithm is a precise specification of a sequence of constructions to be carried out in order to solve a given problem. Each instruction tells what task in to be performed. Specification of a sequence of instructions to do a job is used in many fields.
As soon as we can write sorting algorithm, it is necessary to learn how to store data in memory either using pointer or array. First of all we store data in a sequence, elements of array or pointer may be in random order. When data stored in memory, we can arrange data either in ascending or in descending order using various sorting algorithm. Finally stored data will replace their original position and stored in a desired order a sorting algorithm is as follows.
Bubble_sort (n,list) Where n: - Represent the number of elements in the list The list 1: - Represent the list of elements Step 1: [Initialization] I=0 Step 2: Repeat through step 5 while (1<n) Step 3: j=0 Step 4: Repeat through step 5 while (j<n-1) Step 5: if (list[j] < list [j+1])
Step 6: Exit
From the algorithm it is clear that for the pass the inner loop performs the n-1 comparisons to find the smallest element. Total number of compassions for all the passes is: –
Normally, any sorting algorithm in differ from each other. Only the similarity that the input and output of all algorithm are exactly same. The quick which is also know a partition sorting algorithm of quick sort is based on partition. Home methods falls under divide and cangues technique the main list of elements is divided into two sub lists. For example, a list of X elements is to be sorted. The quick sort marks an element in a list called as pivot or key consider the first element j as a pivot. Shift all elements whose value is less than j towards. The left and element whose value is greater than j to the right of the j now, the key element divides the main list into two parts. It is not necessary that selected key element must be the middle any element from the list can act as a key element. However, for the best performance is given to middle element time consumption of the quick sort technique depends on the location of the key in the list quick sort algorithm is as follows: –
Q_sort(array,first,last) Where array: - Represents the list of elements. First: - Represents the position of the first element in the list (only at the starting point, it’s value changes during the execution of the function). Last: - Represent the position of the last element in the list (only at starting point the value of it’s changes during the execution of the function). Step 1: [Initially] Low=first High=last Pivot=array[(low+high)/2][Middle element of the element of the list] Step 2: Repeat through step 7 while(low<=high) Step 3: Repeat step 4 while(array[low]<pivot) Step 4: low=low+1 Step 5: Repeat step 6 while (array[high]>pivot) Step 6: high=high-1 Step 7: if(low<=high)
Step 8: if(first<high) q_sort(array,first,high) Step 9: if(low<last) q_sort(array,low,last) Step 10: Exit