//Quicksort the array
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
//Partition the array into two halves and return the
//index about which the array is partitioned
int partition(int* array, int left, int right)
{
//Makes the leftmost element a good pivot,
//specifically the median of medians
findMedianOfMedians(array, left, right);
int pivotIndex = left, pivotValue = array[pivotIndex], index = left, i;
swap(array, pivotIndex, right);
for(i = left; i < right; i++)
{
if(array[i] < pivotValue)
{
swap(array, i, index);
index += 1;
}
}
swap(array, right, index);
return index;
}
//Computes the median of each group of 5 elements and stores
//it as the first element of the group. Recursively does this
//till there is only one group and hence only one Median
int findMedianOfMedians(int* array, int left, int right)
{
if(left == right)
return array[left];
int i, shift = 1;
while(shift <= (right - left))
{
for(i = left; i <= right; i+=shift*5)
{
int endIndex = (i + shift*5 - 1 < right) ? i + shift*5 - 1 : right;
int medianIndex = findMedianIndex(array, i, endIndex, shift);
swap(array, i, medianIndex);
}
shift *= 5;
}
return array[left];
}
//Find the index of the Median of the elements
//of array that occur at every "shift" positions.
int findMedianIndex(int* array, int left, int right, int shift)
{
int i, groups = (right - left)/shift + 1, k = left + groups/2*shift;
for(i = left; i <= k; i+= shift)
{
int minIndex = i, minValue = array[minIndex], j;
for(j = i; j <= right; j+=shift)
if(array[j] < minValue)
{
minIndex = j;
minValue = array[minIndex];
}
swap(array, i, minIndex);
}
return k;
}
//Swap integer values by array indexes
void swap(int * array, int a, int b)
{
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
//quick sort recursive c program #define maxsize 6 int A[maxsize]; void quicksort(int a, int b)
{
int rtidx=0,ltidx=0,k=a,l=0,pivot;
int leftarr[maxsize],rtarr[maxsize];
pivot=A[a];
if(a==b)return;
while(k<b)
{
++k;
if(A[k]<A[a])
{
leftarr[ltidx]=A[k];
ltidx++;
}
else
{
rtarr[rtidx]=A[k];
rtidx++;
}
} k=a;
for(l=0;l<ltidx;++l)A[k++]=leftarr[l];
A[k++]=pivot;
for(l=0;l<rtidx;++l)A[k++]=rtarr[l];
if(ltidx>0)quicksort(a,a+ltidx-1);
if(rtidx>0)quicksort(b-rtidx+1,b);
} void printarr(int a)
{
int i;
for(i=0;i<a;i++)
{
printf("%d",A[i]);
printf("\n");
}
} main()
{
int i,s;
printf("enter the number of numbers to be entered \n");
scanf("%d",&s);
for(i=0;i<s;i++)
{
printf("enter the number \n" );
scanf("%d",&A[i]);
}
printf("array before sorting ");
printarr(s);
quicksort(0,s-1);
printf("array after sorting");
printarr(s);
}
#include<iostream>
#include<string>
#include<vector>
class X
{
private:
int m_key;
std::string m_value;
public:
X (const int key, const std::string& value): m_key {key}, m_value (value) {}
X (const X& other): m_key {other.m_key}, m_value (other.m_value) {}
X (X&& other): m_key {std::move (other.m_key)}, m_value (std::move (other.m_value)) {}
X& operator= (const X& other) { m_key=other.m_key; m_value=other.m_value; return *this; }
X& operator= (X&& other) { m_key=std::move (other.m_key); m_value=std::move (other.m_value); return *this; }
~X () {}
int key() const {return m_key;}
std::string value() const {return m_value;}
};
bool operator< (const X& lhs, const X& rhs) { return lhs.key()<rhs.key(); }
std::ostream& operator<< (std::ostream& os, const X& x) { return os << x.value(); }
template<typename T>
void quicksort (std::vector<T>& v, int l, int r)
{
if (r<=l)
return;
int m=(r-l)/2+l;
std::swap (v[m], v[r]);
int i=l-1;
int j=r;
while (1)
{
while (v[++i]<v[r]);
while (v[r]<v[--j])
if (j==l)
break;
if (i>=j)
break;
std::swap (v[i], v[j]);
}
std::swap (v[i], v[r]);
quicksort (v, l, i-1);
quicksort (v, i+1, r);
}
template<class T>
void quicksort (std::vector<T>& v)
{
if (2<v.size())
quicksort (v, 0, v.size()-1);
}
int main()
{
std::vector<X> numbers {X {2,"two"}, X {6,"six"}, X {3,"three"}, X {1,"one"}, X {4,"four"}, X {5,"five"}};
std::cout << "Unsorted:\t";
for (auto number : numbers) std::cout << number << ' ';
std::cout << std::endl;
quicksort (numbers);
std::cout << "Sorted:\t\t";
for (auto number : numbers) std::cout << number << ' ';
std::cout << std::endl;
}
int
main(){
int
s,i,j,temp,a[20];
printf(
"Enter total elements: "
);
scanf(
"%d"
,&s);
printf(
"Enter %d elements: "
,s);
for
(i=0;i
scanf(
"%d"
,&a[i]);
for
(i=0;i
for
(j=i+1;j
if
(a[i]>a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf(
"After sorting is: "
);
for
(i=0;i
printf(
" %d"
,a[i]);
return
0;
}
#include<time.h>
template<class T>
void exch( T& x, T& y )
{
T tmp=x;
x=y;
y=tmp;
}
// Generates a pseudo-random number in the range min to max (inclusive).
int get_rand( const int range_min=0, const int range_max=RAND_MAX )
{
static bool seeded = false;
if( !seeded )
{
seeded = !seeded;
std::srand((unsigned) time(NULL));
}
return((int)((double)std::rand() / (RAND_MAX+1) * ((range_max+1) - range_min) + range_min));
}
template<class T>
void quicksort( T a[], int l, int r )
{
int i;
static int j;
tail_call:
if(r<=l)
return;
// Select random pivot and move it to end of array.
exch( a[get_rand(l,r)], a[r] );
i = l-1;
j = r;
while(1)
{
// Locate the 1st value from left that is not less than the pivot.
while(a[++i]<a[r]);
// Locate the 1st value from right that is not greater than the pivot
while(a[r]<a[--j])
if(j==l)
break;
if(i>=j)
break;
exch(a[i], a[j]);
}
exch( a[i], a[r] );
// Determine the smaller subset
static int l1, l2;
l1=l, l2=i-1;
int r1=i+1, r2=r;
if(r2-r1<l2-l1)
{
l1=r1, l2=r2;
r1=l, r2=i-1;
}
// Recurse over smallest subset
quicksort( a, l1, l2);
// Tail-call over largest subset
l=r1, r=r2;
goto tail_call;
}
template<class T>
void quicksort( T a[], const size_t size )
{
if( size < 2 )
return;
quicksort( a, 0, size-1 );
}
what is the pure algorithm instead of cpp program?
Such a program is called a Quine. http://en.wikipedia.org/wiki/Quine_(computing)
Yes, that's how quick-sort works.
The .cpp extension is merely conventional; it is not required by the C++ standard. You can actually use any file extension you wish.
int main (void) { puts ("charminar"); return 0; }
what is the pure algorithm instead of cpp program?
Yes because a program can run without a CPP extension, especially if program extension is .exe
Go to the link. You will got use of "this" keywork with simple explanation and example. http://cpp.codenewbie.com/articles/cpp/1527/Keyword_this-Page_5.html
Such a program is called a Quine. http://en.wikipedia.org/wiki/Quine_(computing)
The .cpp extension is merely conventional; it is not required by the C++ standard. You can actually use any file extension you wish.
The extension of a file containing a C program can be any extension, so long as the compiler or platform can infer the proper rules to build it. Commonly, for C programs, the extension is .c, so myfile.c would be a C program. The term cpp is not a designation for C++. It means C Program Precompiler, and it is the normal way to build one or more C programs into an executable. Over the years, cpp has evolved into being able to handle all sorts of languages. C++ is one of them. Typical extensions for C++ programs are .cc, .cpp, and .cxx.
Yes, that's how quick-sort works.
int main (void) { puts ("charminar"); return 0; }
Quick Sort
That is possible. Try it.
CPP
When you want to sort an array.