CPlusOne
Notes, Syllabus, Questions, Ideas,
Books, Reference materials on Electronics


Quick Links
#Login #Sign up #Forum #Feedback

 

#Previous question #Index of C Questions #Next question

QUICK SORT A.K.A Partition Exchange Sort: This algorithm sorts the array by positioning each element in its proper position and partitioning the array into two sub arrays at the proper position of the moved element.

Proper position in the array refers to the position of the element in the array when the position of the element in the array is the same as the position of the element in the sorted array containing the same element.

Let us consider an array a[] consisting of n elements. Let an element x be chosen from any position in the array (generally for ease in coding and reduction in program volume, the first element is considered for placement) and be placed in the position i such that:

  • All elements placed to the left of i are less than or equal to x
  • All elements placed to the right of i are greater than x

We see that x is the ith smallest element of array a[]. If we repeat the process for the sub arrays a[0] to a[i-1] and a[i+1] to a[n], we get another element placed in its proper position compared to the sortd array. Thus if we repeat the process till no more sub arrays can be formed, the resultant array is the sorted array.

Let us take an example:

Let the initial array contains the elements

 29	23	17	57	34	89	65	27

When the first element (29) is placed in its proper position, the array becomes

 27	23	17	29	34	89	65	57

Here 29 is in its proper position (i) in the array. The elements to the left of i (27 23 17) is less than or equal to 29 and the elements to the right of i (34 89 65 57) are greater than 29. Since 29 has reached its final position, the array is partitioned at i(position of 29) into two sub arrays

(27 23 17) and (34 89 65 57)

Now each sub array is sorted individually. This is done by considering each sub array as an array and applying the above stated process to it.

The left sub array has three elements. Considering it as an array, when the first element (27) is placed in its proper position, it becomes:

17 23 27

The right sub array has four elements. Considering it as an array, when the first element (34) is placed in its proper position, it becomes:

34 89 65 57

No change takes place as the first element is the smallest element.

Thus the array (considering sorted element and both sub arrays) becomes

17 23 27 29 34 89 65 57

The sub arrays are further divided into two sub arrays each resulting in

(17 23) 27 29 34 (89 65 57)

Since the sorted elements are placed at extremities the partitioning results in only one sub array each.

The process is repeated till the array is sorted.

17 (23) 27 29 34 (89 65 57)

17 23 27 29 34 (89 65 57)

17 23 27 29 34 (89 65 57)

17 23 27 29 34 (57 65) 89

17 23 27 29 34 57 (65) 89

17 23 27 29 34 57 65 89

The final array obtained is a sorted array.

The quicksort algorithm may be best defined by two methods:

quick(x[],lb,ub) :
This method sorts all elements in an array (x[]) between lb and ub. The sorting is done recursively as it is most convenient.

An algorithm for this method is as follows:

quick(int x[],int lb,int ub) 
/* the parameter list includes array pointer x[],
   the position of the first or lowermost element in the array(lb),
   the position of the last or uppermost element in the array(ub)
*/

	int j;
	if(lb>=ub)
	
		return; // array is sorted //
	
	else
      /* a method that puts an element (x[lb])
      at the proper position (j) in the array and
      partitions the array at that position.
      The position is sent to the calling method as an argument */
		j=partition(x,lb,ub); 

		quick(x,lb,j-1); //recursively sorts the left sub array

		quick(x,j+1,ub); //recursively sorts the right sub array

partition(x[],lb,ub) :
This method is used to seek the proper position of an element in the array. The element is placed at the proper position and the position is sent back to the quick() method as an argument.

Let a=x[lb] be the element whose position is to be found. The position of lowermost element (lb) and uppermost element (ub) are sent to the method. Two local variables down and up are initialized with the values of lb and ub respectively. Now, the variables down and up will be used to point to the variables present in the array. lb initially points to lowermost element while ub initially points to uppermost element. down and up are moved towards each other such that

  • down is incremented by 1 if x[down]<=a
  • up is decremented by 1 if x[up]>a
  • if down<up, the elements at x[down] and x[up] are exchanged.

These steps are repeated as long as the condition is true. When the condition fails, x[up] is swapped with x[lb] which is equal to a and the value of up is returned.

The algorithm can be best explained by the example taken before:

29 23 17 57 34 89 65 27

Now, when partition method is called, the lb and ub sent as argument are copied to down and up respectively. The following shows the progress of down and up variables.

An asterisks (*) means exchange being made between down and up.

a=x[lb]=29

down							up
29	23	17	57	34	89	65	27 

down						up
29	23	17	57	34	89	65	27 

down					up
29	23	17	57	34	89	65	27

down				up
29	23	17	57	34	89	65	27 

down				up
29	23	17	57	34	89	65	27 *

down				up
29	23	17	27	34	89	65	57 

down			up
29	23	17	27	34	89	65	57 

down			up
29	23	17	27	34	89	65	57 

down		up
29	23	17	27	34	89	65	57 

down	up
29	23	17	27	34	89	65	57 

down/up
29	23	17	27	34	89	65	57 

up    down
29	23	17	27	34	89	65	57 *

up    down	
27	23	17	29	34	89	65	57 

Thus the element a=x[lb]=29 reaches its proper position at the end of the partition method. The position of 29 (up) is returned.

An algorithm for the method is as follows:

partition(int x[],int lb,int ub)
/* the parameter list includes array pointer x[],
   the position of the first or lowermost element in the array(lb),
   the position of the last or uppermost element in the array(ub)
*/
  int temp,a,down,up;
  a=x[lb]; // a is the element whose final position is to be found

  up=ub;
  down=lb;

  while(down<up)
  {
    /*down<ub is checked to ensure that the
      pointer does not go beyond the boundary of the array */
    while(x[down]<=a && down<ub)
		
      down++; //move up the array
		
      while(x[up]>a)
		
        up--; //move down the array
		
		if(down<up) 
		{
			//exchange x[down] and x[up]
			temp=x[down];
			x[down]=x[up];
			x[up]=temp;
		}
	}
	
	//exchange a(x[lb]) with x[up]
	x[lb]=x[up];
	x[up]=a;

	return up; //proper position of a is returned to caller method

A fully working program using quicksort algorithm is given below. The coding has been done in C compiler. The main function asks for the size of the array and the elements of the array and sorts the array using quicksort algorithm.

#include<stdio.h>
#include<conio.h>
int partition(int x[],int lb,int ub)
{
	int temp,a,down,up;
	a=x[lb];
	up=ub;
	down=lb;
	while(down<up)
	{
		while(x[down]<=a && down<ub)
		{
			down++;
		}
		while(x[up]>a)
		{
			up--;
		}
		if(down<up)
		{
			temp=x[down];
			x[down]=x[up];
			x[up]=temp;
		}
	}
	x[lb]=x[up];
	x[up]=a;
	return up;
}
void quick(int x[],int lb,int ub)
{
	int j;
	if(lb>=ub)
	{
		return;
	}
	else
	{
		j=partition(x,lb,ub);
		quick(x,lb,j-1);
		quick(x,j+1,ub);
	}
}
void main()
{
	clrscr();
	int ar[100];
	int n,i,down,up;
	printf("\n Enter the size of the array:");
	scanf("%d",&n);
	printf("\n Enter the elements of the array:");
	for(i=0;i<n;i++)
	{
		scanf("%d",&ar[i]);
	}
	down=0;
	up=n-1;
	quick(ar,down,up);
	printf("\n The sorted array is:");
	for(i=0;i<n;i++)
	{
		printf("%d",ar[i]);
	}
	getch();
}

Quicksort may also be applied using linked list instead of an array. The following program shows implementation of quicksort using linked list.

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct node
{
	int data;
	struct node *prev;
	struct node *next;
};

struct node *getnode()
{
	struct node *n;
	n=(struct node *)malloc(sizeof(struct node));
	return n;
}
void display(struct node *n)
{
	if(n)
	{
		printf("%d\n",n->data);
		display(n->next);
	}
}
struct node *partition(struct node *f,struct node *l)
{
	struct node *first,*last;
	int d;
	bool flag=false;
	first=f;
	last=l;
	while(first!=last && flag==false)
	{
		while((first->data)<=(f->data) && first!=l)
		{
			first=first->next;
			if(first==last)
				flag=true;
		}
		while(last->data>f->data && last!=f)
		{
			last=last->prev;
			if(first==last)
				flag=true;
		}
		if(first!=last && flag==false)
		{
			d=first->data;
			first->data=last->data;
			last->data=d;
		}
	}
	d=f->data;
	f->data=last->data;
	last->data=d;
	return last;
}
void quick(struct node *h,struct node *t)
{
	struct node *n;
	n=NULL;
	n=partition(h,t);
	if(h!=n && n->prev!=h)
		quick(h,n->prev);
	if(t!=n && n->next!=t)
		quick(n->next,t);	
}
void main()
{
	struct node *head,*t,*p;
	char c='y';
	head=getnode();
	t=head; p=NULL;
	do
	{
		printf("\nEnter element:");
		scanf("%d",&(t->data));
		t->prev=p;
		p=t;
		fflush(stdin);
		printf("\nDo you want to continue (y/n):");
		scanf("%c",&c);
		if(c=='y')
		{
			t->next=getnode();
			t=t->next;
		}
	}while(c=='y');
	t->next=NULL;
	display(head);
	quick(head,t);
	printf("\n The sorted array is:\n");
	display(head);
}

You have viewed 1 page out of 204. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

structured programming language, first C program, header files, library, compilation, pre-processing, compilation, optimization, linking format, debugging with GDB, data types, storage classes, if, if-else, if-else-if, label and goto, switch case, loop statements, break and continue, pointers, enum type, macro, basic operators, logical operators, logical vs bitwise operators, bit shifting, bit set, reset/clear, toggle, Operator precedence, array, multidimensional arrays, 2D and 3D dynamic array, add Matrix, multiply Matrix, adjacency Matrix, Circuler buffer, user defined types, typedef, struct type, union type, struct vs union, struct pack padding, bit fields, obtain bit mask, reverse bits, swap bits, structure as function argument, array as function argument, printing pointers, scanf string input, scan string with blanks, scanf string ends with newline, return of scanf, return of printf, scanf with printf, print using fprintf, take input using fscanf, floating point formatting, multiple arguments in printf and scanf, variadic functions, variadic macro, calling conventions, calling convention of C,C++ and PASCAL, operator precedence, ternary operator, switch statement, continue in switch and loops, for, while, do-while loop syntax, for to while, do-while and while usage, infinite loops, function declaration and definition, library function linking, call-by-value and call-by-reference, parameter passing call-by-value, parameter passing call-by-reference, address of local and dynamic variable, volatile variable, external vs static, global vs static variable, register vs auto variable, const, macro vs constant, debug builds, debug macros, compiler macro for C++, FILE, LINE, DATE, TIME, compiler marcos, token pasting, characterizing, const char *,char * const, const char * const, char array and char pointers, enum vs macro, macro vs typedef, size of a structure, upper and lower 16bit of 32bit unsigned, near, far and huge pointer, typed pointers and void pointer, sizeof void, sizeof void and void pointer, operators for void pointer, l-value, struct and array, NULL pointer, inline-functions, macro vs inline-function, malloc vs calloc, function pointer, compare with ==, argc and argv, C startup routine, strcpy and strcat source, memcpy vs memmove, strrev source, strdup, strtok, palindrome, reverse decimal digits, signed and unsigned compare, string vs integer pointer, xor operator, bitwise shifting, logical and bitwise or, macro definition, long pointer increment, default C++ argument value, short pointer increment, short pointer increment, execution sequence, exceptions, setjump and longjump, trace a memory leak, detect memory corruption, Big Endian and Little Endian, stack grows up or down, prime number, HCF, LCM, star triangle, Exchange variables, C and Data Structures, Data Structures using array, Linked List, Single Linked list, Doubly Linked list, Circular Linked list, Doubly Circular Linked list, Queue, reverse single linked list, delete single linked list, Stack, Tree and Binary tree, Binary tree, traverse Binary tree, Binary search tree, double Binary tree, mirror Binary tree, height of Binary tree, heap, Complexity, Linear Search, Binary Search, Hash Table, Sorting, Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort, Merge sort, Radix Sort, Recursion, factorial using recursion, Fibonaci using recursion, amrongstrong number, argv environ, system(), atexit, raise signal, abort exit, Libraries, static linking, dynamic linking methods, implicit dynamic linking, explicit dynamic linking, access C from VB, access C from Java, sleep/delay, sound, nosound, alpha numeric, convert case, string to int, int to string, fprintf, fscanf working principal, palindrome digits, arithmeic math, trigonometric, fopen, fdopen, write vs append mode, binary vs text mode, binary mode, fseek, fprintf, fscanf, fflush, ioctl, mmap, fcntl, poll, select, poll, select, fputs,fgets,fgetc,fputc, printf, scanf, DOS graphics, compilers, Turbo C, GCC, VC++,

# C/C++ Interview questions and answers - Shetty's World
# C Interview Questions and Answers - C Interview FAQs & C Books
# C interview questions and answers | TechInterviews
# C Interview Questions and Answers :: ALL Interview .com
# C Interview Questions and Answers

* #1 webmaster Sun 02 Feb/2014 03:11:38(GMT)  Like 0 Unlike 0

Dear Users,

We are pleased to inform you that a forum/blog has been incorporated with www.mybestnotes.co.in. You are welcomed to add your comments, requests, codes, solutions and feedback to it. Please login(if already a member) or signup(for free) to avail to this facility.

Regards,
Webmaster

Your message goes here:

Name:Guest
Email:anonymous@unknown.com
My Post:*
Secutiry Code: ******  *
Preview this compose before posting this in discussion forum.
 
Note:
  1. Use [Sxx] code to show smiles. Example [S02]
  2. Use [URL ], example [URL http://www.google.com/]
  3. To display code or un formatted text use [CODE] [/CODE]. Example: [CODE] printf("Hello world"); [/CODE]
 [S01]   [S02]   [S03]   [S04]   [S05]   [S06]   [S07]   [S08] 
 [S09]   [S10]   [S11]   [S12]   [S13]   [S14]   [S15]   [S16] 
 [S17]   [S18]   [S19]   [S20]   [S21]   [S22]   [S23]   [S24] 

Note: Only members are allowed, * fields are mandatory.