Go Back   TechArena Community > Software > Software Development
Become a Member!
Forgot your username/password?
Tags Active Topics RSS Search Mark Forums Read

Sponsored Links



what is Quick Sort or partition Exchanger in data structure

Software Development


Reply
 
Thread Tools Search this Thread
  #1  
Old 03-01-2011
Member
 
Join Date: Dec 2010
Posts: 12
what is Quick Sort or partition Exchanger in data structure
  

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.

Reply With Quote
  #2  
Old 03-01-2011
Member
 
Join Date: Apr 2009
Posts: 484
Re: what is Quick Sort or partition Exchanger in data structure

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.
Reply With Quote
  #3  
Old 03-01-2011
Member
 
Join Date: May 2009
Posts: 503
Re: what is Quick Sort or partition Exchanger in data structure

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.
Reply With Quote
  #4  
Old 03-01-2011
Member
 
Join Date: May 2009
Posts: 533
Re: what is Quick Sort or partition Exchanger in data structure

Code:
#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 ;
}
Reply With Quote
Reply

  TechArena Community > Software > Software Development
Tags: , , ,



Thread Tools Search this Thread
Search this Thread:

Advanced Search


Similar Threads for: "what is Quick Sort or partition Exchanger in data structure"
Thread Thread Starter Forum Replies Last Post
What is bubble sort in data structure punguzhali Software Development 3 04-01-2011 03:49 AM
What is the use of insertion sort in data structure? Venugopala Software Development 3 04-01-2011 02:41 AM
What do you mean by Merge sort in data structure fLUTE Software Development 3 04-01-2011 02:12 AM
What is the difference between binary tree sort and heap sort in data structure sRIPRIYA Software Development 3 04-01-2011 01:25 AM
Choice of data structure Hashim Software Development 5 02-11-2009 07:27 PM


All times are GMT +5.5. The time now is 06:35 PM.