The power of swapping pairs in an array

We can start with the partition operation in quick sort. The in put array is not sorted, given an pivotal, we are ask to put the element in this array smaller than this pivotal to the left part and equal or larger values to the left, we can return the number of smaller elements to help to do the next partitions, or equivalently, the first index i nums[i] >= pivotal, you can test your code here.

int partitionArray(vector<int> &nums, int pivotal) {
for (int i = 0, int p = 0; i < nums.size(); i++) {
if (nums[i] < pivotal) {
swap(nums[i], nums[p]);
p++;
}
}
        return (p);
}

Dutch national flag problem

This is a slightly improved usage of swapping. The problem is equivalent to sorting an array has only values from 0, 1, 2. Test your solution here 75. Sort Colors.

void sortColors(vector<int>& nums) {
int len = nums.size();

for (int i = 0, j = 0, k = len - 1; i <= k; i++) {
if (nums[i] == 0) {
swap(nums[i], nums[j]);
j++;
} else if (nums[i] == 2) {
swap(nums[i], nums[k]);
k--;
i--;
}
}
}

41. First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Like the Dutch flag problem, the possible values in this array is limited, we can use the idea of bucket sort and get a linear time complicity related to the size of array. In addition we can so this without using extra space as large as the original array by swapping in original array.

I want to comment on the to_swap function, we want to do swap for bucket if the target element is not in correct position, as we know that if we have exact values from 1 to n, we must be able to do this swap every time, but the input has possible missing positive, so if the target position is already the correct value, we know that there is something redundant and we continue with the next element.

int firstMissingPositive(vector<int>& nums) {
int len = nums.size(), index, val, res = 1;

for(int i = 0; i < len; i++) {
index = i;
        while(to_swap(nums, index)) {
val = nums[index];
swap(nums[index], nums[val - 1]);
}
}

for(int i = 0; i < len; i++) {
cout<<nums[i]<<endl;
if (nums[i] == res) {
res++;
}
}

return(res);
}

bool to_swap(vector<int> &nums, int i) {
if (nums[i] <= 0) {
return(false);
} else if (nums[i] > nums.size()) {
return(false);
}
        int index = nums[i];

if (nums[index - 1] == index){
return(false);
} else {
return(true);
}
}

Sort colors II

Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, … k.

We can conqueror this problem using the idea of bucket sort too, but the swapping is a little more involved. I’v consider it as a complex example of swapping array elements. You can test the coder here.

void sortColors2(vector<int> &colors, int k) {
vector<vector<int>> indices =
get_starting_indices(colors, k);

vector<int> start_indices = indices[0];
vector<int> end_indices = indices[1];

for (int i = 0; i < colors.size(); ++i) {
int index = i;
while(!isvalid(colors, start_indices, end_indices, index)) {
int color = colors[index];
int new_index = start_indices[color];

/*
* If the target is valid, we need to skip to the next
* target.
*/
if (isvalid(colors, start_indices,
end_indices, new_index)) {
if (start_indices[color] < end_indices[color]) {
start_indices[color]++;
} else {
break;
}
} else {
swap(colors[index], colors[new_index]);
}

/*
* for print intermediate steps
for (int j = 0; j < colors.size(); j++) {
cout<<colors[j]<< ",";
}
cout<<endl;
*/
}
}
}

/*
* find the starting index of each color when using bucket sort.
* ending index is the prefix sum of counts - 1
*/
vector<vector<int>>
get_starting_indices(vector<int> &colors, int k){
//assert(k > 0);
vector<vector<int>> indices;
vector<int> start (k + 1, 0);
vector<int> end (k + 1, 0);

for (int i = 0; i < colors.size(); ++i) {
end[colors[i]]++;
}

for (int i = 2; i <= k; i++) {
end[i] += end[i - 1];
}
        for (int i = 1; i <= k; i++) {
end[i]--;
}

for (int i = 2; i <= k; i++) {
start[i] = end[i - 1] + 1;
}
        indices.push_back(start);
indices.push_back(end);

return (indices);
}

bool isvalid(vector<int> &colors, vector<int> &start_indices,
vector<int> &end_indices, int i) {
int color = colors[i];
return (i >= start_indices[color] &&
i <= end_indices[color]);
}

Let’s see the swapping operations in this method:

If the input is [3,2,2,1,2,1,4], and we have colors from 1 to 4,

the starting position should be

[0, 0, 2, 5, 6], be creaful here we use the color value as index, so the first element in the starting position array is useless.

3,2,2,1,2,1,4
1,2,2,1,2,3,4,
1,2,2,1,2,3,4,
1,1,2,2,2,3,4,
1,1,2,2,2,3,4,
[1,1,2,2,2,3,4]

Another more complex example

[3,2,3,3,4,3,3,2,4,4,1,2,1,1,1,3,4,3,4,2], 4

4,2,3,3,4,3,3,2,3,4,1,2,1,1,1,3,4,3,4,2,
3,2,3,3,4,3,3,2,3,4,1,2,1,1,1,4,4,3,4,2,
3,2,3,3,4,3,3,2,3,4,1,2,1,1,1,4,4,3,4,2,
4,2,3,3,4,3,3,2,3,3,1,2,1,1,1,4,4,3,4,2,
4,2,3,3,4,3,3,2,3,3,1,2,1,1,1,4,4,3,4,2,
4,2,3,3,4,3,3,2,3,3,1,2,1,1,1,4,4,3,4,2,
3,2,3,3,4,3,3,2,3,3,1,2,1,1,1,4,4,4,4,2,
3,2,3,3,4,3,3,2,3,3,1,2,1,1,1,4,4,4,4,2,
1,2,3,3,4,3,3,2,3,3,3,2,1,1,1,4,4,4,4,2,
1,4,3,3,2,3,3,2,3,3,3,2,1,1,1,4,4,4,4,2,
1,4,3,3,2,3,3,2,3,3,3,2,1,1,1,4,4,4,4,2,
1,4,3,3,2,3,3,2,3,3,3,2,1,1,1,4,4,4,4,2,
1,2,3,3,2,3,3,2,3,3,3,2,1,1,1,4,4,4,4,4,
1,2,3,3,2,3,3,2,3,3,3,2,1,1,1,4,4,4,4,4,
1,3,3,3,2,2,3,2,3,3,3,2,1,1,1,4,4,4,4,4,
1,3,3,3,2,2,3,2,3,3,3,2,1,1,1,4,4,4,4,4,
1,2,3,3,2,2,3,2,3,3,3,3,1,1,1,4,4,4,4,4,
1,2,3,3,2,2,3,2,3,3,3,3,1,1,1,4,4,4,4,4,
1,3,3,3,2,2,2,2,3,3,3,3,1,1,1,4,4,4,4,4,
1,3,3,3,2,2,2,2,3,3,3,3,1,1,1,4,4,4,4,4,
1,1,3,3,2,2,2,2,3,3,3,3,3,1,1,4,4,4,4,4,
1,1,3,3,2,2,2,2,3,3,3,3,3,1,1,4,4,4,4,4,
1,1,1,3,2,2,2,2,3,3,3,3,3,3,1,4,4,4,4,4,
1,1,1,3,2,2,2,2,3,3,3,3,3,3,1,4,4,4,4,4,
1,1,1,1,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,...

Sort colors II revisited, as we already have the partition function for quick sort, if the range is fixed, we can do the quick sort much faster, for example

we can use k / 2 as the first pivotal and then k/4 for the pivotal of the first half and 3/4 for the pivotal of the second half. We could use floats for these pivotal, but integers will be OK as we can utilize the binary representation to iterate from 1 to k easily. One way to create these pivotal is

vector<int> construct_pivotals(int k) {
//assert(k > 2)
vector<int> res;
int power = 1;
int next = power*2;

while (power < k) {
for(int i = k; i > 0; i--) {
if (i % power == 0 && (!(i % next == 0))) {
res.push_back(i);
}
}
power = power * 2;
next = next * 2;
}

return (res);
}

For example, if k = 25, the pivotals are

25,23,21,19,17,15,13,11,9,7,5,3,1,22,18,14,10,6,2,20,12,4,24,8,16,

I haven’t figured out how to combined this order with the return of patition positions. So I tried to get the pivotals and patitions are the same time, the basic idea is from the segmentation tree of range of colors [1, k], we split the range to [1, k/2] [k /2 ,k], etc, and we record the partion positions at the same time, so we can transversal the segmentation tree by level, and the end condition is that the range interval has the same starting and ending values.

Let see the partitions operation for relative longer example:

[10,6,4,10,1,5,8,1,3,6,4,10,1,7,9,7,7,5,9,8,2,6,7,2,10], 10

The segmentation tree intervals are

Partion range:[1,10]
Partion range:[1,5]
Partion range:[6,10]
Partion range:[1,3]
Partion range:[4,5]
Partion range:[6,8]
Partion range:[9,10]
Partion range:[1,2]
Partion range:[3,3]
Partion range:[4,4]
Partion range:[5,5]
Partion range:[6,7]
Partion range:[8,8]
Partion range:[9,9]
Partion range:[10,10]

The corresponding partition operations are recorded here

Partion range:[1,10]
pivotal:5
Partion position:[0,25]
Partions postion:10
4,1,5,1,3,4,1,5,2,2,10,10,8,7,9,7,7,10,9,8,6,6,7,6,10,
Partion range:[1,5]
pivotal:3
Partion position:[0,10]
Partions postion:6
1,1,3,1,2,2,4,5,5,4,10,10,8,7,9,7,7,10,9,8,6,6,7,6,10,
Partion range:[6,10]
pivotal:8
Partion position:[10,25]
Partions postion:19
1,1,3,1,2,2,4,5,5,4,8,7,7,7,8,6,6,7,6,9,10,10,10,9,10,
Partion range:[1,3]
pivotal:2
Partion position:[0,6]
Partions postion:5
1,1,1,2,2,3,4,5,5,4,8,7,7,7,8,6,6,7,6,9,10,10,10,9,10,
Partion range:[4,5]
pivotal:4
Partion position:[6,10]
Partions postion:8
1,1,1,2,2,3,4,4,5,5,8,7,7,7,8,6,6,7,6,9,10,10,10,9,10,
Partion range:[6,8]
pivotal:7
Partion position:[10,19]
Partions postion:17
1,1,1,2,2,3,4,4,5,5,7,7,7,6,6,7,6,8,8,9,10,10,10,9,10,
Partion range:[9,10]
pivotal:9
Partion position:[19,25]
Partions postion:21
1,1,1,2,2,3,4,4,5,5,7,7,7,6,6,7,6,8,8,9,9,10,10,10,10,
Partion range:[1,2]
pivotal:1
Partion position:[0,5]
Partions postion:3
1,1,1,2,2,3,4,4,5,5,7,7,7,6,6,7,6,8,8,9,9,10,10

On implementation, need to be cleaned, but you can test it here, the running time is 200ms comparing to 800ms with the swapping approaches mentioned earlier.


int partition(vector<int> &nums, int pivotal, int start, int end) {
int i, p;
for (i = start, p = start; i < end; i++) {
if (nums[i] <= pivotal) {
swap(nums[i], nums[p]);
p++;
}
}
return (p);
}
void sortColors2(vector<int> &colors, int k) {
int p, pos;
    pair<int, int> left, right, r_left, r_right;

pair<int, int> interval(0, colors.size());
queue <pair<int, int>> intervals, tmp_intervals;
intervals.push(interval);

pair<int, int> range(1, k);
queue <pair<int, int>> ranges, tmp_ranges;
ranges.push(range);

while(!intervals.empty()){
while(!intervals.empty()){
pair<int, int> cur = intervals.front();
pair<int, int> cur_range = ranges.front();

p = cur_range.first +
(cur_range.second - cur_range.first) / 2;
            intervals.pop();
ranges.pop();

pos = partition(colors, p, cur.first, cur.second);
            left.first = cur.first;
left.second = pos;
right.first = pos;
right.second = cur.second;

r_left.first = cur_range.first;
r_left.second = p;
r_right.first = p + 1;
r_right.second = cur_range.second;


tmp_intervals.push(left);
tmp_intervals.push(right);
            tmp_ranges.push(r_left);
tmp_ranges.push(r_right);
}
            swap(intervals, tmp_intervals);
swap(ranges, tmp_ranges);

if (ranges.front().first == ranges.front().second) {
break;
}
}
}

Comment,

One universal approach using swapping to reorder the array is like this

int Reorder_by_swapping(vector<int>& nums) {
for(int i = 0; i < nums.size(; i++) {
index = i;
while(to_swap(nums, index)) {
target = find_target(index);
swap(nums[index], nums[target]);
}
}
}

The key function to abstract and implement is the to swap function and the find_target function.