Programming Questions

  • Newest
  • Popular Tags
  • Ask A Question
  • 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 | interview, array, sort, dutch
    Answers
  • +
  • 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?
    Log in to write an answer.