Created
March 29, 2018 19:57
-
-
Save jianminchen/b4b7bd03d48e4ff26261afb77a1d3ec9 to your computer and use it in GitHub Desktop.
Pancake sort - review code with the peer
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
void flip(vector<int> &arr, int k) // first k + 1 | |
{ | |
for(int i = 0; i <= k; i++) | |
{ | |
int tmp = arr[i]; | |
arr[i] = arr[k]; | |
arr[k] = tmp; | |
k--; // code smell -> this kind of coding is "code smells", too tricky - write simple code | |
// hidden bugs are hard to find | |
// k + 1 element -> two pointers technique, meet middle | |
// begin/ end -> swap, begin++, end-- | |
} | |
} | |
vector<int> pancakeSort( const vector<int>& arr ) | |
{ | |
int cnt = 0; // readable code - using express the intent - count, cnt, size sz | |
int sz = arr.size(); | |
vector<int>save; | |
for(int i = 0; i < sz; i++) | |
save.push_back(arr[i]); | |
for(int times = 0; times < sz; times++) // here is the problem | |
{ | |
int pos = -1; // maxIndex | |
int mx = -1; // maxValue | |
for(int i = 0; i < sz - cnt; i++) | |
{ | |
int current = save[i]; | |
if(current > mx) | |
{ | |
mx = current; | |
pos = i; | |
} | |
} | |
cout << "pos is "<<pos <<" max is " << mx << endl; | |
flip(save, pos); // move max index to last position - cnt | |
flip(save, sz - cnt - 1); | |
cnt++; | |
} | |
return save; | |
} | |
int main() { // 1, 3, 1 | |
vector<int>vec; | |
vec.push_back(1); | |
vec.push_back(5); | |
vec.push_back(4); | |
vec.push_back(3); | |
vec.push_back(2); | |
return 0; | |
} | |
/* | |
[1, 5, 4, 3, 2] | |
sort the array, how to put 5 to last position in the array? | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment