Author |
Topic: single traversal (Read 754 times) |
|
darklord
Newbie
Posts: 10
|
 |
single traversal
« on: Apr 9th, 2009, 5:48am » |
 Quote  Modify
|
gn: an array of only 1's and 0's how to separate them such that 0's in left and 1's in rite.in a single traversal.with out using extra space.in o(n)
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: single traversal
« Reply #2 on: Apr 9th, 2009, 6:10am » |
Quote Modify
|
Actually, since this statement of the problem doesn't require a stable sort, it's much simpler: initialize two pointers/indexes to the start and end of the array. Scan towards the center, swapping pairs of misplaced 1's and 0's. When the two meet, you're done.
Edit to add code:
#include <vector>
using namespace std;
enum binary { zero = 0, one = 1 };
void sort(vector<binary> arr) {
int first = 0, last = arr.size() - 1;
while (first < last) {
while (first < last && arr[first] == binary::zero) ++first;
while (first < last && arr[last] == binary::one) --last;
if (first < last) {
binary temp = arr[first]; arr[first] = arr[last]; arr[last] = temp;
}
}
}
--SMQ
|
| « Last Edit: Apr 9th, 2009, 6:31am by SMQ » |
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: single traversal
« Reply #3 on: Apr 9th, 2009, 6:23am » |
Quote Modify
|
Well, I'm sure it's been asked before. The trouble is finding it. Besides, that thread does mention the solution that works here, because nearly everyone ignored the stable sort requirement in that thread.
|
| « Last Edit: Apr 9th, 2009, 6:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print