Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 29, 2018 19:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/b4b7bd03d48e4ff26261afb77a1d3ec9 to your computer and use it in GitHub Desktop.
Save jianminchen/b4b7bd03d48e4ff26261afb77a1d3ec9 to your computer and use it in GitHub Desktop.
Pancake sort - review code with the peer
#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