Programming Questions

Dutch national flag sorting problem

Hey all,
I recently came upon an interview question called the Dutch national flag problem that required me to sort an array of 1's, 2's, and 3's in order while only traversing the array once. So for example if the array were

a = [1,3,3,2,1]then after iterating through the array only once I should get

a = [1,1,2,3,3]How can I write an algorithm to search and sort through the array only once without using any other data structures?

codetimer
posted this question on 1/21/14 **|**

3

The key here is that the elements are from 1 to 3. What you have to do is run through the array once, moving all the 1's to the front and 3's to the back. During this, the 2's will essentially file into the middle, leaving the entire array sorted. If the elements were from 1 to 4, this would not be possible.
I'm not exactly fluent in Javascript, so this could probably look a lot better, but here goes...

function dutchFlag4(arr){ var a = 0; while(a<arr.length){ if(arr[a]===1){ if(a != 0){ for(b=a-1;b>=0;b--){ arr[b+1] = arr[b]; } } arr[0] = 1; a++; }else if(arr[a]===2){ a++; }else if(arr[a]===3){ if(a != arr.length-1){ for(b=a+1;b<arr.length;b++){ arr[b-1] = arr[b]; } } arr[arr.length-1] = 3; /* If we used the same code here as we did for the check for 1, the value for arr[a+1] would be pushed to arr[a], and then would not be checked when we increment a. Therefore, we do not increment a here unless we verify that the rest of arr is properly sorted (that is, it only contains 3's). The following code checks that. */ var flag = 0; for(b=a;b<arr.length;b++){ if(arr[b] != 3){ flag = 1; break; } } if(flag === 0) a++; } } return arr; }

spellbee2

answered on 01/22/14

2

Assuming you can use push, splice, and unshift:

function dutch(arr){ for(var i = 0; i < arr.length; i++){ if(arr[i] == 3){ arr.splice(i,1); arr.push(3); } if(arr[i] == 1){ arr.splice(i,1); arr.unshift(1); } } return arr; } console.log(dutch([1,2,3,2,3,1,1,3]));

MBarton

answered on 01/24/14

1

Here's a pretty clean solution, which is essentially like one iteration of quicksort, where the pivot is 2, and where we partition into three regions: 1, 2 and 3:

def dutch(arr): i = 0 j = 0 k = 0 r = 0 n = len(arr) while ( r != n): # | 1 | 2 | 3 | ???? | # i j k r n if arr[r] == 3: r +=1 elif arr[r] == 2: arr[k],arr[r] = arr[r],arr[k] k +=1 r +=1 elif arr[r] == 1: arr[k],arr[r] = arr[r],arr[k] r+=1 arr[k],arr[j] = arr[j],arr[k] k+=1 j+=1 return

relational

answered on 02/19/14

1

This is probably too obvious:

function dutchFlag1(arr){ var result = arr.sort(); return result; }So maybe:

function dutchFlag2(arr){ var first = []; var sec = []; var third = []; for(i=0;i<arr.length;i++){ if(arr[i]===1){ first.push(arr[i]); }else if(arr[i]===2){ sec.push(arr[i]); }else if(arr[i]===3){ third.push(arr[i]); }else{ return -1; } } return first.concat(sec,third); }

vagon

answered on 01/21/14

1

Thanks for the answer vagon, but what if the question asks for only one data structure (in this case one array) to be used rather than creating 3 seperate arrays?

codetimer

answered on 01/21/14

0

To display code include the following tags:

def dutchAlgo(input): input=map(int,input.split(" ")) a,b,c=0,0,(len(input)-1) d=0 while True: d+=1 if input[a]==2: while True: if input[c]!=2: input[c],input[a]=input[a],input[c];c-=1;break if c==a: break else : c-=1 if input[a]==0: while True: print d if input[b]!=0 and b <=a : input[b],input[a]=input[a],input[b] b+=1 break else: b+=1 if b > a : break if a >= c : break a+=1 print input

arpitpattewar

answered on 05/20/15

0

Why not do the same with a string and split to an array then?

function dutchFlag3(arr){ var result = ""; var first = ""; var sec = ""; var third = ""; for(i=0;i<arr.length;i++){ if(arr[i]===1){ first += "1,"; }else if(arr[i]===2){ sec += "2,"; }else if(arr[i]===3){ third += "3,"; }else{ return -1; } } third = third.slice(0,third.length-1); result = first + sec + third; return result.split(","); }Or does the returned array count as another data structure?

vagon

answered on 01/21/14

Log in to write an answer.