aboutsummaryrefslogtreecommitdiff
path: root/sort_colours.c
diff options
context:
space:
mode:
Diffstat (limited to 'sort_colours.c')
-rw-r--r--sort_colours.c42
1 files changed, 42 insertions, 0 deletions
diff --git a/sort_colours.c b/sort_colours.c
new file mode 100644
index 0000000..f48230e
--- /dev/null
+++ b/sort_colours.c
@@ -0,0 +1,42 @@
+// 75. Sort Colors
+#include "leetcode.h"
+
+/*
+ * given an array 'nums' with 'n' objects coloured red, white, or blue, sort
+ * them in place so that objects of the same colour are adjacent with the
+ * colours in the order red, white and blue. we will use the integer 0,1,2 to
+ * represent the colour red, white, and blue respecitvely. you must solve this
+ * problem without the library's sort function.
+ */
+
+void sortColors(int *nums, int numsSize) {
+ int two_ptr = numsSize - 1, zero_ptr = 0, one_ptr = 0;
+ while (one_ptr <= two_ptr) {
+ if (!nums[one_ptr]) {
+ int tmp = nums[zero_ptr];
+ nums[zero_ptr] = nums[one_ptr];
+ nums[one_ptr] = tmp;
+ one_ptr++;
+ zero_ptr++;
+ } else if (nums[one_ptr] == 1)
+ one_ptr++;
+ else {
+ int tmp = nums[two_ptr];
+ nums[two_ptr] = nums[one_ptr];
+ nums[one_ptr] = tmp;
+ two_ptr--;
+ }
+ }
+}
+
+int main() {
+ int n1[] = {2, 0, 2, 1, 1, 0}, n2[] = {2, 0, 1};
+ sortColors(n1, ARRAY_SIZE(n1));
+ sortColors(n2, ARRAY_SIZE(n2));
+ for (int i = 0; i < ARRAY_SIZE(n1); i++)
+ printf("%d ", n1[i]);
+ printf("\n");
+ for (int i = 0; i < ARRAY_SIZE(n2); i++)
+ printf("%d ", n2[i]);
+ printf("\n");
+}