answersLogoWhite

0

Quicksort in any programming language is an algorithm for sorting data sequences. It is typically implemented as follows (example demonstrates a quicksort of an array of type int). Note that a half-open range, [begin:end), includes the one-past-the-end of the range and is the conventional means of defining a range of contiguous array values. When begin==end, the range is deemed empty.

// forward declarations

void qsort (int* unsigned); // this is the function you will actually invoke

void qsort_rec (int*, int*); // recursive function

int* partition (int*, int*); // utility functions...

int* select_pivot (int*, int*);

void swap (int*, int*);

int count (int*, int*);

// sort a data sequence of length size

void qsort (int* data, unsigned size) {

qsort_rec (data, data + size);

}

// recursively sort the half-open range [begin:end)

void qsort_rec (int* begin, int* end) {

if (count (begin, end) < 2) return; // end point of recursion

int* pivot = partition (begin, end);

qsort_rec (begin, pivot);

qsort_rec (++pivot, end);

}

// divide the half-open range [begin:end) into two around a pivot value

int* partition (int* begin, int* end) {

if (count (begin, end) < 2) return begin;

int* pivot = select_pivot (begin, end);

swap (begin, pivot);

--end;

while (begin != end) {

while (*(begin) <= *pivot && begin != end) ++begin;

while (*pivot < *(end) && begin != end) --end;

if (begin!=end) swap (begin, end);

}

assert (begin==end); // sanity check!

swap (pivot, begin);

return begin;

}

// select the median of three from a half-open range [begin:end)

int* select_pivot (int* begin, int* end) {

int* mid = begin + (count (begin, end) / 2);

if (*end<*begin) swap (begin, end);

if (*mid<*begin) swap (begin, mid);

if (*end<*mid) swap (mid, end);

return end;

}

// swap the values referred to by p and q

void swap (int* p, int* q) {

if (!p !q) return; // sanity check!

int t = *p;

*p = *q;

*q = t;

}

// count the elements in the half-closed range [begin:end)

int count (int* begin, int* end) {

int cnt = 0;

int add;

if (begin>end) { // swap pointers if the range is reversed

int* t = begin;

begin = end;

end = t;

add = -1; // count will be negative

} else {

add = 1; // count will be positive

}

while (begin++!=end) cnt+=add;

return cnt;

}

User Avatar

Wiki User

8y ago

What else can I help you with?

Related Questions

Different types of sorting techniques in c language?

types of sorting in c language are: insertion sort selection sort bubble sort merge sort two way merge sort heap sort quick sort


What is the code for arranging numbers in c language?

That depends on the sorting algorithm you'd like to use. Usually, Quick-sort is good enough for your purposes, but if your application needs to be fast, you might want to read some documents about sorting.


Are there examples of figurative language in the sorting hat song?

yes, there is a rhyme scheme


What is mean by sorting in c?

arranging items in some ordered sequence,


What are the types of sorting in c?

Any type you want to write. C does not provide sorting routines natively; you have to either use a library routine or write something. Some library implementations are based on quicksort or heapsort but, again, that is not a C (or C++) thing - it is a run-time library thing.


Why c language has name c why not a?

C-language was derived from B-language.


What is previous language of c language?

language before c language is pascal


What is C language what does it do?

C Language is First Step of Programming Language, Help for C Language you are show the correct answer


Program to print sorting of an array?

For program in C language: http://wiki.answers.com/Q/Program_to_print_sorting_of_an_array_in_clanguage&updated=1&waNoAnsSet=2 Program in C++: #include #include void main() { int i,j,n,t,a[50]; clrscr(); cout"%d",&n; cout


What is the topNet class that everything is derived from in c?

C language: int (but C is NOT a .net language) C# language: object or System.Object


What is the program language c?

C is a pop language. C is a case sensetive language. C is motherof all language. C is block structure language. C is a high level language. C is advace of B language. C developed by D.richties in 1972 at AT &amp; T Bell lab in USA. Sachin Bhardwaj 986854722 skbmca@gmail.com


What is versions of c language?

versions of c language?

Trending Questions
Write a program to calculate GPA in C plus plus? What is wiper system in car? In order to find the total inductive reactance in a series or parallel circuit containing more than one inductor the same method must be used that was used to find inductance? What difference have robots made to your human life today? Is it true In a binary search if the search fails to find the item on the first attempt then there are 999 elements left to search in an array of 1000 elements? Which javascript function is most useful for finding erro? What is casting forging and foundry? What are the entrance exams to join in engineering in details? What language is used for robot programming? What are watts and kilowatts? What is studded with ribosomes? 10 Explain the term session in server side programming approach What is the main benefit from implementing the session? How does plywood have so much strength? How a compiler translates? Where is the fuel pump relay and what is the voltage at the pump on a 1987 B2600 with carburetor? What parameter to a function is one for which an automatic value is supplied if do not explicitly use one in C programming? If part of an electric circuit dissipates energy at 6 w when it draws a current of 3 awhat voltage is impressed across it? Do step up-down transformers waste electricity when plugged-in but not in use - note this is not referring to AC-DC converters but transformers that change voltage between 110-120v to 220-240v? What is Jagged Array in C? How do you measure the resistance of a 30-amp cartridge fuse in ohms?