Programming Questions

• Popular Tags
• 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; } ```
• +
• 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])); ```
• +
• 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 ```
• +
• 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); } ```
• +
• 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?
• +
• 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```
• +
• 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?