gnirut
1
If you know before hand that the array contains only 0 and 1, there is a very simple way to sort this array. Step 1. Iterate through the array and count the number of 0s in a variable M. Let the size of the array be N Step 2. Write 0 M times starting from index 0 Step 3. Write 1 (N-M) times starting from index M You have your sorted array. To extend this technique to sort an array that contains only 0, 1 and 2, do the same except that you maintain 2 counters - one to count 0s and one to count 1s. Step 1. Iterate through the array and count the number of 0s in a variable P; and the number of 1s in a variable Q. Let N be the size of the array Step 2. Write 0 P times, starting from index 0 Step 3. Write 1 Q times, starting from index P Step 4. Write 2 N-(P+Q) times, starting from index (P+Q) You have your sorted array
rama
1
If you know that the array contains only 0 and 1, you can sort the array as follows: Step 1. Run the first pass of quick sort (the partition phase) Step 2. You will have the sorted array To extend it to 3 numbers, the above algorithm can be used: Step 1. Run the first pass of quick sort (the partition phase). The gives you 2 partitions around the pivot - the left side and the right side Step 2. One side is sorted - either the right side or the left side Step 3. Use the number in the pivot to decide which side is partitioned. If pivot = 1 or 2, the left side needs to be sorted. If pivot = 0, the right side needs to be sorted Step 4. Switch to the partition that is not sorted, and apply the partition phase of quick sort again