Cpp program for quick sort

Answer 1

//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;

}

Answer 2

//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);

}

Answer 3

#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;

}

Answer 4

#include

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;

}

Answer 5

#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 );

}