what is Quick Sort or partition Exchanger in data structure

[Venugopala]

Hello friends, I am an I.T student where I am having a subject as data structure in which I am finding a topic very difficult to understand. I tried very hard but it was extremely difficult. I am finding quick sort topic very much tough in data structure. I am not able to understand anything in this topic. If I get to know it with help of program then it will quite easier for me to understand. If program is written in C language then it will be quite easier for me to understand. If anyone having any information related to this topic then please let me know as soon as possible.

[Villiers]

This sorting method sort the data faster than any of the common sorting algorithm.This algorithm is based on the fact that it is faster and easier to sort two small arrays than one large one. The basic strategy is to divide and conquer. This method picks an element from the array, known as pivot element and divides the array into two parts. Then take the first array(part) and subdivide it into two array .The array will be further broken down into two array. This process goes on until the arrays are small enough to be easily sorted. This strategy is based on recursion.

[Vandam]

a) In the first iteration,we will place the 0th element 11 at its final position and divide the arrayHere 11 is pivot element .To divide the array two index variable p and q are taken. The index are initialized in such a way that p refers to the 1st element 2 and q refers to (n-1)th element 3.
b) The job of index variable p is to search an element that is greater than the value 0th location. So p is incremented by one till the value stored at p is greater than 0th element. n our case it is incremented till 13, as 13 is greater than 11.
c) Similarly q needs to search element that is smaller than 0th element.So q is decremented by one till the value stored at q is smaller than the value at 0th element.In our case q is not decremented because 3 is less than 11
d) When these elements are found they are interchanged .Again from the current position p and q are incremented and decremented respectively and exchange are made appropriately
e) The process ends whenever the index pointers meet or crossover.In our case they are crossed at the values 1 and 25 for the indexes q and p respectively.Finally the 0th element 11 is interchanged with the value at index q i.e. 1 the position q is now the final position of the pivot element 11.
f) As a result the whole array is divided into two parts. where all elements before 11 are less than 11 and all the elements after 11 are greater than 11.
g) Now the same procedure is applied for two sub arrays.As a result ,at the end when all sub arrays are left with one element,the original array become sorted.

[Jacques25]

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

int split ( int*, int, int ) ;

void main( )
{
	int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
	int i ;

	void quicksort ( int *, int, int ) ;

	clrscr( ) ;

	printf ( "Quick sort.\n" ) ;
	printf ( "\nArray before sorting:\n") ;

	for ( i = 0 ; i <= 9 ; i++ )
		printf ( "%d\t", arr[i] ) ;

	quicksort ( arr, 0, 9 ) ;

	printf ( "\nArray after sorting:\n") ;

	for ( i = 0 ; i <= 9 ; i++ )
		printf ( "%d\t", arr[i] ) ;

	getch( ) ;
}

void quicksort ( int a[ ], int lower, int upper )
{
	int i ;
	if ( upper > lower )
	{
		i = split ( a, lower, upper ) ;
		quicksort ( a, lower, i - 1 ) ;
		quicksort ( a, i + 1, upper ) ;
	}
}
  int split ( int a[ ], int lower, int upper )
{
	int i, p, q, t ;

	p = lower + 1 ;
	q = upper ;
	i = a[lower] ;

	while ( q >= p )
	{
		while ( a[p] < i )
			p++ ;

		while ( a[q] > i )
			q-- ;

		if ( q > p )
		{
			t = a[p] ;
			a[p] = a[q] ;
			a[q] = t ;
		}
	}

	t = a[lower] ;
	a[lower] = a[q] ;
	a[q] = t ;

	return q ;
}