# QuickSort分区

``````void Partition(int data[], int low , int high){
int pivot = data[low];
int fromLow = low;
int fromHigh = high;
int ptr = low;

goto QStart;
while(true){
do {
fromHigh--;
if(fromLow >= fromHigh)
goto QEnd;
QStart:;
}while(data[fromHigh] > pivot)

data[ptr] = data[fromHigh];
ptr = fromHigh;

do{
fromLow++;
if(fromLow >= fromHigh){
ptr = fromHigh;
goto QEnd;
}
}while(data[fromLow] < pivot)
data[ptr] = data[fromLow];
ptr = fromLow;
}
QEnd:;
data[ptr] = pivot;
}
``````

``````void MyPartition(int data[], int low , int high){

int pivot = data[low];
int fromLow = low;
int fromHigh = high;
int ptr = low;
while(fromLow != fromHigh){
if(data[fromHigh] >= pivot)
fromHigh--;
else{
data[ptr] = data[fromHigh];
ptr = fromHigh;

while(data[fromLow] <= pivot && fromLow != fromHigh)
fromLow ++;
data[ptr] = data[fromLow];
ptr = fromLow;
}
}
data[ptr] = pivot;
}
``````

1. first, scanning array from high end to low end (right => left) for finding the first value is less than pivot.
2. then, scanning array from low end to high end (left => right) for finding the first value is greater than pivot.
3. In either scan, if anything is found, then we "swap it with pivot value", this is logical swap,because pivot value is cached with variable pivot, we can regard variable ptr as the current pivot value position.

UPDATE:

``````int PartitionData2(int * data, int low, int high){
int pivot = data[low];
int fromLow = low;
int fromHigh = high;
int ptr = low;

while(fromLow < fromHigh){
if(data[fromHigh] > pivot)          //'>=' ==> '>'
fromHigh--;
else{
data[ptr] =data[fromHigh] ;
ptr = fromHigh;

while(data[++fromLow] < pivot &&  //'<=' ==> '<'
fromLow != fromHigh);

data[ptr] = data[fromLow];
ptr = fromLow;
fromHigh--;                       //antti.huima's idea
}
}
data[ptr] = pivot;
return ptr;
}
``````

UPDATE2: I understand the reason why we need move element which equals to pivot, because if we don't, the two new partitions will be uneven, e.g. there should be one is much larger than another. it eventually go to O(n^2) case.

see this PDF

3

@Chang，当你说他的算法更快时，你的意思是说它有不同的渐近行为，或者只是说给定输入花费的时间更少？

@dsolimano，我的意思是给定输入的时间更少

@MikeDunlavey，我没有看到反汇编代码有太大区别。我只是怀疑这是由分支惩罚引起的。

## 1 答案

``````   while(data[fromLow] <= pivot && fromLow != fromHigh)
``````

2