Learn Computer Science programming - C# and C++ Algorithms

 
Partition Sort
The list is partitioned around a pivot element. A different array is used to hold the partially ordered list. A pivot element is selected as the middle value of three randomly chosen elements. The list is thendivided into lower than or equal keys are placed at the head of a new array, higher keys at the tail. The new list becomes the old list and the sublists are partioned in the same way, until all partitions hold fewer than two elements. Partition sort is not a good as Quicksort.
Code
partition_sort.zip
File Size: 4110 kb
File Type: zip
Download File

#include <iostream.h>


char* Partition(char* a, int Low, int High);

void main()
{
char a[] = {'F','O','L','M','O','A','D','Q','J','E','M','F'};
// F,O,L,M,O,A,D,Q,J,E,M,F
for (int i = 0; i< sizeof(a) ; i++)
{
cout << a[i] << " , " ;
}
cout << endl << "The New Array : " << endl;
Partition(a, 0, (sizeof(a)-1));

for (i = 0; i< sizeof(a) ; i++)
{
cout << a[i] << " , " ;
}

int x;
cin >> x;

}
char* Partition(char* a, int Low, int High)
{
int Pivot = Low;
int Left = Low;
int Right = High;
char Temp;
while (Left < Right)
{
//If Left < Pivot move left
if (a[Left] <= a[Pivot]) Left++;
if (a[Right] > a[Pivot]) Right--;
if (Left < Right) 
{
Temp = a[Left];
a[Left] = a[Right];
a[Right] = Temp;
}
}
Temp = a[Pivot];
a[Low] = a[Right];
a[Right] = Temp;
return a;
}

Output
// F,O,L,M,O,A,D,Q,J,E,M,F
A , F , E , D , F , O , Q , J , M , M , L , O