Program segment for quick sort, Data Structure & Algorithms

Assignment Help:

Illustrates the program segment for Quick sort. It uses recursion.

Program 1: Quick Sort

Quicksort(A,m,n)

int A[ ],m,n

{

int i, j, k;

if m

{

i=m; j=n+1; k=A[m]; do

do

do

++i;

while (A[i] < k);

do

--j;

while (A[j] > k);

if (i < j)

{

temp = A[i];

A[i] = A[j];

A[j] = temp;

}

while (i

temp = A[m];

A[m] = A[j];

A[j] = temp;

Quicksort(A,m,j-1);

Quicksort(A,j+1,n);

}

The Quick sort algorithm uses the O(N Log2N) comparisons on average. The performance can be developed by keeping in mind the following points.

1.         Switch to a faster sorting scheme such as insertion sort while the sublist size becomes comparatively small.

2.      Employ a better dividing element in the implementations.


Related Discussions:- Program segment for quick sort

The space - time trade off, The best algorithm to solve a given problem is ...

The best algorithm to solve a given problem is one that requires less space in memory and takes less time to complete its execution. But in practice it is not always possible to

Graph traversal schemes, Various graph traversal schemes Graph Traversa...

Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

The theta-notation, This notation bounds a function to in constant factors....

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f

Threads in main method, Create main method or a test class that creates 2 E...

Create main method or a test class that creates 2 Element objects that are neighbours of each other, the first element temperature set at 100, the 2nd at 0 and use an appropriate h

Show that towers of hanoi is o (2n), Question 1 Discuss the advantages of ...

Question 1 Discuss the advantages of implementation checks preconditions Question 2 Write a ‘C' program to search for an item using binary search Question 3 Show that To

Dijkstras algorithm, Djikstra's algorithm (named after it is discovered by ...

Djikstra's algorithm (named after it is discovered by Dutch computer scientist E.W. Dijkstra) resolves the problem of finding the shortest path through a point in a graph (the sour

Breadth-first search, Breadth-first search starts at a given vertex h, whic...

Breadth-first search starts at a given vertex h, which is at level 0. In the first stage, we go to all the vertices that are at the distance of one edge away. When we go there, we

Sort 5, The number of interchanges needed to sort 5, 1, 6, 2 4 in ascending...

The number of interchanges needed to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort is 5

A binary tree in which levels except possibly the last, A binary tree in wh...

A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is called as

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd