median 3 quick sort implementation

Question

my median 3 implementation is not working fine here. i have to choose 3 numbers randomly for medium here is my code please help me.

#include"stdafx.h"
#include <iostream>
#include<algorithm>
using namespace std;
#define size 10
int i;                               
void show(int* array, int n);
int partition(int* array, int pValue, int left, int right);
void QuickSort(int* array, int left, int right);

int main(void)
{
    int array[size];
    int i;

    for( i = 0; i < size; i++)              
    {
         array[i]=rand()%100;
    }

    cout<<endl<<"The random generated numbers are: "<<endl;
    show(array, size);
    QuickSort(array,0,size - 1);                
    cout<<endl<<"The sorted numbers are : "<<endl;
    show(array, size);

    system("pause");
    return 0;
}

void show(int* array, int n)
{
    int i;

    for( i = 0; i < n; i++) cout<<array[i]<<'\t';
}



void QuickSort(int* array, int left, int right)
{
    for(i=0;i<3;i++)
    {
       array[i]=array[rand()%100];
      }
      stable_sort(array,array+3);
     int p=array[(i+1)/2];
    //int p = array[left];              
    int split;

    if(right > left)                         
    {
        split = partition(array, p, left, right);

        array[split] = p;
        QuickSort(array, left, split-1);   
        QuickSort(array, split+1, right);    
    }
}


int partition(int* array, int p, int left, int right)
{
    int lb = left;
    int rb = right;

    while(lb < rb)             
    {
         while( p < array[rb]&& rb > lb)      
         {
              rb--;                     
         }
         swap(array[lb], array[rb]);

         while( p >= array[lb]&& lb < rb)     
         {
              lb++;                      
         }
         swap(array[rb], array[lb]);

    }
    return lb;                            


}

Answer 1

Your code was way too complex for this simple algorithm, check code below:

void QuickSortMedian(int a[],int start,int end) {
    int q;
    count++;
    if (end-start<2) return;
    q=MedianOfThreePartition(a,start,end);
    QuickSortMedian(a,start,q);
    QuickSortMedian(a,q,end);
}

int MedianOfThreePartition(int a[],int p, int r) {
    int x=a[p],y=a[(r-p)/2+p],z=a[r-1],i=p-1,j=r;
    if (y>x && y<z || y>z && y<x ) x=y;
    else if (z>x && z<y || z>y && z<x ) x=z;
    while (1) {
        do  {j--;count++;} while (a[j] > x);
        do  {i++;count++;} while (a[i] < x);
        if  (i < j) swap(&a[i],&a[j]);
        else return j+1;
    }
}


void QuickSortRandomAndMedian(int a[],int start,int end) {
    int q;
    count++;
    if (end-start<2) return;
    q=RandomAndMedianPartition(a,start,end);
    QuickSortRandomAndMedian(a,start,q);
    QuickSortRandomAndMedian(a,q,end);
}

int RandomAndMedianPartition(int a[],int p, int r) {
    int t,x=a[t=((rand()%(r-p))/2)+p+(r-p)/4],y=a[t+1],z=a[t-1],i=p-1,j=r;
    if (y>x && y<z || y>z && y<x ) x=y;
    else if (z>x && z<y || z>y && z<x ) x=z;
    while (1) {
        do  {j--;count++;} while (a[j] > x);
        do  {i++;count++;} while (a[i] < x);
        if  (i < j) swap(&a[i],&a[j]);
        else return j+1;
    }
}

The second algorithm is just a boost that I wrote for the optimization of quick sort, for example on a 40000 elements array regular quick sorts did about 800k actions, the median one did 650k and the random median one did about 620k. That's the best I got so far. :)

Answer 2

Maybe the problem is here:

array[i]=array[rand()%100];

First, you're changing some elements of the array, when you should be swapping them with others. If you don't you are destroying data.

Second, your array has size 10, but you're asking for an index at a random position between 0 and 99. Obviously, you can't do that, and that's why you're getting garbage.