Quicksort 2 - Sorting

In the previous challenge, you wrote a partition method to split an array into two sub-arrays, one containing smaller elements and one containing larger elements than a given number. This means you ‘sorted’ half the array with respect to the other half. Can you repeatedly use partition to sort an entire array?
在前面的任务里，你写了一个将数组分成两个子数组的分区函数，这两个子数组其中一个里的所有元素都小于一个给定的数，另一个则大于该数。这意味着相对于另一半，你“排序”了一半的数组。你能重复利用分区来排序整个数组吗？

Guideline （指引）

In Insertion Sort, you simply went through each element in order and inserted it into a sorted sub-array. In this challenge, you cannot focus on one element at a time, but instead must deal with whole sub-arrays, with a strategy known as “divide and conquer”.

When partition is called on an array, two parts of the array get ‘sorted’ with respect to each other. If partition is then called on each sub-array, the array will now be split into four parts. This process can be repeated until the sub-arrays are small. Notice that when partition is called on just one of the numbers, they end up being sorted.

Can you repeatedly call partition so that the entire array ends up sorted?
在插入排序中，你只需简单的地按序检查每一个元素然后将其插入到已排序的子数组中。在本次任务中，你不能仅仅每次只关注一个元素，相反地必须使用“分治”的策略来处理整个子数组。

当对一个数组进行分区操作时，数组的两部分对彼此来说已经“有序”了。如果对于每个子数组再进行分区操作，原数组将分成四部分。这个过程可以一直重复直到子数组变得很小。请注意这一点：当仅对其中的一个数进行分区操作时，这些数其实已经有序了。

你能重复调用分区函数使得最终整个数组有序吗？

In this challenge, print your array every time your partitioning method finishes, i.e. whenever two subarrays, along with the pivot, is merged together.

The first element in a sub-array should be used as a pivot.
Partition the left side before partitioning the right side.
The pivot should be placed between sub-arrays while merging them.
Array of length 1 or less will be considered sorted, and there is no need to sort or to print them.
在本次任务中，每次分区结束后打印你的数组。

子数组中的第一个元素作为基准。
先对左边的分区，再对后边的分区。
基准应在合并左右两个子数组时放与两者之间。
数组长度小于等于1的视为有序，不需排序或打印

Note （注意）

Please maintain the original order of the elements in the left and right partitions while partitioning around a pivot element.

For example: Partition about the first element for the array A[]={5, 8, 1, 3, 7, 9, 2} will be {1, 3, 2, 5, 8, 7, 9}
当围绕基准元素分区时，请保持左右分区中元素原先的前后顺序。
例如：对数组A[]={5, 8, 1, 3, 7, 9, 2} 的第一个元素进行分区的结果该是{1, 3, 2, 5, 8, 7, 9}

Input Format （输入格式）

There will be two lines of input:

  • n the size of the array
  • ar the n numbers of the array
    两行：
    -数组大小n
    -数组中的n个元素

    Output Format （输出格式）

    Print every partitioned sub-array on a new line.
    每次分区后的结果在新的一行输出

    Constraints （约束条件）

    1<=n<1000
    -1000<=x<=1000
    Each number is unique.

Sample Input（输入样例）

7
5 8 1 3 7 9 2

Sample Output（输出样例）

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

Explanation （解释）

This is a diagram of Quicksort operating on the sample array:
下面是样例的一个快排示意图

quick-sort diagram

Task （任务）

The method quickSort takes in a parameter, ar, an unsorted array. Use the Quicksort algorithm to sort the entire array.
函数quickSort有一个未排序的数组ar作参数。使用快排算法对数组排序

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
39
40
41
42
43
44
45
46
47
int partition(vector <int> &arr,int p,int r){
    vector <int> left,right;
    int x=arr[p];
    for (int j=p+1;j<=r;j++){
        if (arr[j]<x){
           left.push_back(arr[j]);
        }else{
            right.push_back(arr[j]);
        }
    }
    for(int i=0;i<left.size();i++){
        arr[i+p]=left[i];
    }
    int q=p+left.size();
    arr[q]=x;
    for(int i=0;i<right.size();i++){
        arr[i+q+1]=right[i];
    }        
    return q;
}
void quickSort(vector <int> &arr,int p,int r) {
    if (p<r){
        int q=partition(arr,p,r);                 
        quickSort(arr,p,q-1);
        quickSort(arr,q+1,r);
        //print sub-array
        for(int i=p;i<=r;i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
    }
}

int main()
{
    int n;
    cin >> n;

    vector <int> arr(n);
    for(int i = 0; i < (int)n; ++i) {
        cin >> arr[i];
    }

    quickSort(arr,0,n-1);

    return 0;
}

总结：

分成left,right,equal三部分会很清楚，但实际排序时没必要建立left,right数组，完全可以实现就地(in-place)排序,否则如上面的代码显示的一个浪费O(n)的空间，另外还要额外合并的时间(merge),而就地排序这两个问题都可以解决
代码如下：

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
39
40
41
42
43
#include <vector>
#include <iostream>

using namespace std;
void swap(int &a,int &b){
    int t=a;
    a=b;
    b=t;
}
int partition(vector <int> &arr,int p,int r){
    int x=arr[p];
    int i=p;
    for (int j=p+1;j<=r;j++){
        if (arr[j]<x){
           i++;
           swap(arr[i],arr[j]);
        }
    }
    swap(arr[p],arr[i]);       
    return i;
}
void quickSort(vector <int> &arr,int p,int r) {
    if (p<r){
        int q=partition(arr,p,r);                 
        quickSort(arr,p,q-1);
        quickSort(arr,q+1,r);
    }
}

int main()
{
    int n;
    cin >> n;
    vector <int> arr(n);
    for(int i = 0; i < (int)n; ++i) {
        cin >> arr[i];
    }
    quickSort(arr,0,n-1);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}