

 Thread Tools  Search this Thread 
#1
 
 
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. 
#2
 
 
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. 
#3
 
 
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 (n1)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. 
#4
 
 
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 ; } 

Tags: data structure, partition exchanger, quick sort, searching 
Thread Tools  Search this Thread 

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  04012011 03:49 AM 
What is the use of insertion sort in data structure?  Venugopala  Software Development  3  04012011 02:41 AM 
What do you mean by Merge sort in data structure  fLUTE  Software Development  3  04012011 02:12 AM 
What is the difference between binary tree sort and heap sort in data structure  sRIPRIYA  Software Development  3  04012011 01:25 AM 
Choice of data structure  Hashim  Software Development  5  02112009 07:27 PM 