Quicksort In-Place

原地快数排序
The previous version of Quicksort was easy to understand, but it was not optimal. It required copying the numbers into other arrays, which takes up space and time. To make things faster, one can create an “in-place” version of Quicksort, where the numbers are all sorted within the array itself.
前面那个版本的快速排序很容易理解，但却不是最佳的。它需要将数字拷贝到其他数组，这需要花费空间和时间。为了更快速，可以建立一个“原地”版本的快排，数字在数组内部实现排序。

Challenge （任务）

Create an in-place version of Quicksort. You need to follow Lomuto Partitioningmethod.
建立一个原地版本的快排，你需要采用Lomuto Partitioning的方法。

Guideline （指引）

Instead of copying the array into multiple sub-arrays, use indices to keep track of the different sub-arrays. You can pass the indices to a modified partition method. The partition method should partition the sub-array and then return the index location where the pivot gets placed, so you can then call partition on each side of the pivot.

  • Always select the last element in the ‘sub-array’ as a pivot.
  • Partition the left side and then the right side of the sub-array.
  • Print out the whole array at the end of every partitioning method.

  • An array of length 1 or less will be considered sorted, and there is no need to sort or to print them.
    Since you cannot just create new sub-arrays for the elements, partition method will need to use another trick to keep track of which elements are greater and which are lower than the pivot.
    与原来将数组中的元素拷贝到几个子数组中不同，使用标记标识不同的子数组。你可以将标记传递给修改后的分区函数。分区函数需要分出子数组并返回基准的下标，然后你可以对基准两边继续调用分区操作。

  • 从始至终选择子数组中的最后一个元素为基准

  • 先对左边的进行分区然后对右边的分区
  • 每次分区后输出整个数组

  • 长度小于等于1的数组认为是有序的，无需排序或打印
    既然你不能另外新开子数组来存储元素，分区函数就需要另外一个技巧来标识哪些元素大于基准哪些元素小于基准。

    The In-place Trick （原地技巧）

  • If an element is lower than the pivot, you should swap it with a larger element on the left-side of the sub-array.

  • Greater elements should remain where they are.
  • At the end of the partitioning method, the pivot should be swapped with the first element of the right partition, consisting of all larger elements, of the sub-array.
  • To ensure that you don’t swap a small element with another small element, use an index to keep track of the small elements that have already been swapped into their “place”.
  • 如果元素小于基准，你需要将它与子数组左边的一个较大元素交换。
  • 较大的元素维持原地不变
  • 分区操作结束，基准需要与子数组中的右边分区（包含所有较大元素）的第一个元素交换
  • 为了确保你不会交换两个较小的元素，使用一个标记标识所有已经通过交换放在正确位置的较小元素
    Lomuto-partitioning

Input Format （输入格式）

There will be two lines of input:

  • n the size of the array
  • ar the numbers of the array
    两行
  • 数组大小n
  • 数组ar中的数

    Output Format （输出格式）

    Print the entire array on a new line at the end of every partitioning method.
    每行打印每次分区结束后的整个数组

    Constraints （约束条件）

    1<=n<=5000
    -10000<=x<=10000
    There are no duplicate numbers.
    没有重复的数

    Sample Input（输入样例）

7
1 3 9 8 2 7 5

Sample Output（输出样例）

1 3 2 5 9 7 8
1 2 3 5 9 7 8
1 2 3 5 7 8 9

Explanation （解释）

5 is initally selected as the pivot, and the array is partitioned as shown in the diagram. The left side is partitioned next with 2 as the pivot. Finally, the right side is partitioned with 8 as the pivot. The entire array is now sorted.
5是最初的基准，数组分区如图所示。接下来左边以2为基准，最后，右边以8为基准。此时整个数组排序结束。

Lomuto-partitioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int ar[5000]; int n;
void swap(int &a,int &b){
    int t=a;
    a=b;
    b=t;
}
int partition(int *ar,int p,int r){
    int x=ar[r];
    int i=p-1;
    for(int j=p;j<r;j++){
        if (ar[j]<x){
            i++;
            swap(ar[i],ar[j]);
        }
    }
    swap(ar[r],ar[++i]);
    extern int n;
        for(int i=0;i<n;++i){
            cout<<ar[i]<<" ";
        }
        cout<<endl;
    return i;
}
void quicksort(int *ar,int p,int r){
    if (p<r){
        int q=partition(ar,p,r);
        quicksort(ar,p,q-1);
        quicksort(ar,q+1,r);        
    }
}
int main() {
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>ar[i];
    }
    quicksort(ar,0,n-1);
    return 0;
}