Quick Sort

 Quick Sort

Quick sort is the widely used sorting algorithm that makes n log n comparisons in average case for sorting of an array of n elements. This algorithm follows divide and conquer approach. The algorithm processes the array in the following way.

  1. Set the first index of the array to left end loc variable. Set the last index of the array to right variable. i.e. left = 0, loc = 0, end = n - 1, where n is the length of the array.

  2. Start from the right of the array and scan the complete array from right to beginning comparing each element of the array with the element pointed by loc.

Ensure that, a[loc] is less than a[right].

  1. If this is the case, then continue with the comparison until right becomes equal to the loc.

  2. If a[loc] > a[right], then swap the two values. And go to step 3.

  3. Set, loc = right

  1. start from element pointed by left and compare each element in its way with the element pointed by the variable loc. Ensure that a[loc] > a[left]

    1. If this is the case, then continue with the comparison until loc becomes equal to left.

    2. a[loc] < a[left], then swap the two values and go to step 3.

    3. Set, loc = left.

Algorithm

PARTITION (ARR, BEG, END, LOC)

  • Step 1: [INITIALIZE] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG =

  • Step 2: Repeat Steps 3 to 6 while FLAG =

  • Step 3: Repeat while ARR[LOC] <=ARR[RIGHT]
    AND LOC != RIGHT
    SET RIGHT = RIGHT - 1
    [END OF LOOP]

  • Step 4: IF LOC = RIGHT
    SET FLAG = 1
    ELSE IF ARR[LOC] > ARR[RIGHT]
    SWAP ARR[LOC] with ARR[RIGHT]
    SET LOC = RIGHT
    [END OF IF]

  • Step 5: IF FLAG = 0
    Repeat while ARR[LOC] >= ARR[LEFT] AND LOC != LEFT
    SET LEFT = LEFT + 1
    [END OF LOOP]

  • Step 6:IF LOC = LEFT
    SET FLAG = 1
    ELSE IF ARR[LOC] < ARR[LEFT]
    SWAP ARR[LOC] with ARR[LEFT]
    SET LOC = LEFT
    [END OF IF]
    [END OF IF]

  • Step 7: [END OF LOOP]

  • Step 8: END

QUICK_SORT (ARR, BEG, END)

  • Step 1: IF (BEG < END)
    CALL PARTITION (ARR, BEG, END, LOC)
    CALL QUICKSORT(ARR, BEG, LOC - 1)
    CALL QUICKSORT(ARR, LOC + 1, END)
    [END OF IF]

  • Step 2: END

C Program

#include <stdio.h>  

int partition(int a[], int beg, int end);  

void quickSort(int a[], int beg, int end);  

void main()  

{  

    int i;  

    int arr[10]={90,23,101,45,65,23,67,89,34,23};  

    quickSort(arr, 0, 9);  

    printf("\n The sorted array is: \n");  

    for(i=0;i<10;i++)  

    printf(" %d\t", arr[i]);  

}  

int partition(int a[], int beg, int end)  

{  

      

    int left, right, temp, loc, flag;     

    loc = left = beg;  

    right = end;  

    flag = 0;  

    while(flag != 1)  

    {  

        while((a[loc] <= a[right]) && (loc!=right))  

        right--;  

        if(loc==right)  

        flag =1;  

        else if(a[loc]>a[right])  

        {  

            temp = a[loc];  

            a[loc] = a[right];  

            a[right] = temp;  

            loc = right;  

        }  

        if(flag!=1)  

        {  

            while((a[loc] >= a[left]) && (loc!=left))  

            left++;  

            if(loc==left)  

            flag =1;  

            else if(a[loc] <a[left])  

            {  

                temp = a[loc];  

                a[loc] = a[left];  

                a[left] = temp;  

                loc = left;  

            }  

        }  

    }  

    return loc;  

}  

void quickSort(int a[], int beg, int end)  

{  

      

    int loc;  

    if(beg<end)  

    {  

        loc = partition(a, beg, end);  

        quickSort(a, beg, loc-1);  

        quickSort(a, loc+1, end);  

    }  

}  


Output:

The sorted array is: 

23

23

23

34

45

65

67

89

90

101

 

Comments

Post a Comment

Popular posts from this blog

Huffman coding || Huffman coding with example || Huffman coding method || Huffman coding in c/c++ ||Huffman coding programe in c/c++/data structure /java || what is Huffman coding || Huffman complete,

Image
  Huffman coding Huffman Algorithm was developed by David Huffman in 1951. This is a technique which is used in a data compression or it can be said that it is a coding technique which is used for encoding data. This technique is a mother of all data compression scheme. This idea is basically dependent upon the frequency, i.e. the frequency of the corresponding character which needs to be compressed, and by that frequency, only Huffman code will be generated. In case of Huffman coding, the most generated character will get the small code and least generated character will get the large code. Huffman tree is a specific method of representing each symbol. This technique produces a code in such a manner that no codeword is a prefix of some other code word. These codes are called as prefix code. Algorithm for Huffman code     1. Input:-Number of message with frequency         count.     2. Output: - Huffman merge tree. ...
Read more

Ada important question bank

  UNIT 1 Define asymptotic notations. Explain different asymptotic notations with the help of Graphical representations (BL-04, CO-1, PO-1, 2) Describe the various methods of solving recurrences? Explain them in Brief ? (BL-04, CO-1, PO-3) State the Master’s theorem and explain it with examples ? (BL-04, CO-1, PO-4) Show the operation of heap sort on the following array {4,1,3,2,16,9,10,14,8,7} (BL-04, CO-1, PO-1, 2, 3) UNIT 2 Find the solution of following knapsack instance:  n=3,W=20,{v1,v2,v3}={60,100,120},{w1,w2,w3)={18,15,10} (BL-04, CO-2, PO-3,6) Explain the merge sort method of sorting with example (BL-04, CO-2, PO-1, 2) Find the minimum spanning tree using Prim’s method for the following graph: (BL-04, CO-2, PO-1)   Explain optimal storage on tapes and optimal merge patterns. ? (BL-04, CO-2, PO-1, 2) UNIT 3 Write short notes on: (BL-6, (i) Strongly Connected Components    (BL-04, CO-3, PO-1) Identify an optimal parenthesization of a matrix chain pr...
Read more

Unix assignment question

  UNIX & SHELL PROGRAMMING ASSIGNMENT QUESTIONS UNIT 1 Extend internal and external command ?         [CO-1,BL-2,PO-3] Outline the ARCHITECTURE OF UNIX ?          [CO-1,BL-2 PO-4] UNIT 2 What are filter commands?List any two with help of example. [CO-2,BL-4,PO-2] Classify the working of pipes and shell variables. [CO-2,BL-4,PO-4] UNIT 3 Simplify the concept of Function and create a shell script for finding factorial of a number ? [CO-3,L-6,L-4,PO-3] Maximize all meta characters used in grep commands. [CO-3,L- 6,PO-3 ] UNIT 4 simplify the names of special files of korn shell ? [CO-4,L-4,PO-2] Design a korn shell script to display a message using select case? [CO-4,L-6,PO-2] UNIT 5 Justify the concept of superblock   ? Develop a c shell script to find a factorial of a number [CO-5,L-5,PO-1]. Discuss system call ? Formulate any four system calls? [CO-5,L-6,PO-1]
Read more

Graphs in data structure, it's algorithm

  Graphs and their Applications Graph A graph can be defined as group of vertices and edges that are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent child relationship. Definition A graph G can be defined as an ordered set G (V, E) where V (G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices. A Graph G (V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the following figure. Directed and Undirected Graph A graph can be directed or undirected. However, in an undirected graph, edges are not associated with the directions with them. An undirected graph is shown in the above figure since its edges are not attached with any of the directions. If an edge exists between vertex A and B then the vertices can be traversed from B to A as well as A to B. In a dir...
Read more

Java question bank

  UNIT-I What is the object oriented programming concepts in Java? What are the data types in java and how to convert one data type to another? What is constructor? Explain types of constructor and demonstrate calculate area using constructor. Explain static, final and this keyword with suitable example. What is object oriented programming? Write a program in Java to generate the Fibonacci series taking into consideration the following constraints: Create a class FIBO Class FIBO should have a data member n, that will hold the number of terms to be displayed in the Fibonacci series. Using the constructor of the class FIBO fill the value of n from the user during run time.  A member method named “series-generate” should be used to generate and display the Fibonacci series. Write a program that multiplies two 3x3 matrices. Describe different bitwise operators and their uses with proper example. Define Java.  Explain Java virtual Machine in brief. Explain the features of Java...
Read more

M-way Trees

  M- Way Trees A  multi-way tree  is a tree that can have more than two children A  multi-way tree of order m (number or a **m-way tree ) is one in which a tree can have m children. An m-way search tree is a m-way tree in which: a) Each node has m children and m-1 key fields b) The keys in each node are in ascending order. c) The keys in the first i children are smaller than the  i th  key d) The keys in the last m-i children are larger than the  i th  key In a binary search tree, m=2. So it has one value and two sub trees. The figure above is a m-way search tree of order 3. M-way search trees give the same advantages to m-way trees that binary search trees gave to binary trees - they provide fast information retrieval and update. However, they also have the same problems that binary search trees had - they can become unbalanced, which means that the construction of the tree becomes of vital importance. In m-way search tree, each sub-tree is also ...
Read more

Data structure question bank

Question Bank Unit 3 Write Shortnote on: i) Binary Tree             ii) Complete Binary Tree iii) Extended Binary Tree     iv) Threaded Binary trees Design an algorithm of preorder Traversal/In order Traversal/ Post order Traversal. Design an algorithm of Huffman with suitable example? Data items: A   B    C    D   E    F    G    H Weight :      22  5   11  19  2   11  25   5 Design a Binary tree of given order. Post order: A F E B C I J L N O P H M D IN Order   : A B F E D C J I M L H N P O  UNIT 4 Define Activity Networks. Design an algorithm of BFS with suitable example. Evaluate minimum spanning tree using prims / kruskal algorithm.                              ...
Read more

B Tree

  B Tree B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m-1 keys and m children. One of the main reasons of using B tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small. A B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties. Every node in a B-Tree contains at most m children. Every node in a B-Tree except the root node and the leaf node contain at least m/2 children. The root nodes must have at least 2 child nodes. All leaf nodes must be at the same level. It is not necessary that, all the nodes contain the same number of children but, each node must have m/2 number of nodes. A B tree of order 4 is shown in the following image. While performing some operations on B Tree, any property of B Tree may violate such as number of minimum children a node can have. To maintain ...
Read more

Radix Sort

  Radix Sort Radix sort processes the elements the same way in which the names of the students are sorted according to their alphabetical order. There are 26 radix in that case due to the fact that, there are 26 alphabets in English. In the first pass, the names are grouped according to the ascending order of the first letter of names. In the second pass, the names are grouped according to the ascending order of the second letter. The same process continues until we find the sorted list of names. The bucket are used to store the names produced in each pass. The number of passes depends upon the length of the name with the maximum letter. In the case of integers, radix sort sorts the numbers according to their digits. The comparisons are made among the digits of the number from LSB to MSB. The number of passes depend upon the length of the number with the most number of digits. Complexity Complexity Best Case Average Case Worst Case Time Complexity Ξ©(n+k) ΞΈ(nk) O(nk) Space Complexit...
Read more

csa unit 01 part 01 basic of computers notes pdf

Image
csa unit 01 part 01 basic of computers notes pdf you can download by given below linkπŸ‘‡πŸ‘‡πŸ‘‡πŸ‘‡ πŸ‘‰πŸ‘‰πŸ‘‰        https://drive.google.com/file/d/116nBDVQ_1yRi843EwuFq2X2ZefZq8IMM/view?usp=sharing Scanned with CamSca Scanned with CamScanner Scanned with CamScanner Scanned Scanned with CamScanner Scanned with CamScanner Scanned with CamScanner
Read more