How to sort all elements in an array such that all negative numbers are first, and then positive numbers.

    int ar[] = {-2,3,4,-5,6,9,-1,-5};
    int i = 0;
    int j = sizeof(ar) / sizeof(ar[0]) - 1;
    while(i <= j)
    {
        while(ar[i] < 0) { i++; }
        while(ar[j] >= 0) { j--; }

        if (i < j) {
            std::swap(ar[i], ar[j]);
        }
    }

So this code is pretty simple. First we are creating an array of numbers, some negative, some positive, not in any order. Second we determine two index values, one at the beginning of the array and one at the end of the array. Then, as long as the starting index is less than or equal to the ending index, we loop.

After this we basically find the two indices to swap. We do two while loops. While the element in ar[i] is less than 0, which means it’s negative, increase i by 1. We stop once ar[i] is not negative. Then we do another loop where ar[j] is greater than or equal to zero, which means it is positive, and we keep doing this until a number that is not positive is found.

Finally, we just swap the values once we have found one that is positive and one that is negative. The final if statement if (i < j) is to make sure that we don’t swap it incorrectly after i is incremented by 1.

This is just a simple leetcode style question I found the solution to so I wanted to share it. The time complexity should be O(N).

What is C K&R Syntax?

Okay I just want to start out and say that this is outdated. The only reason why I am posting about this is because I find the history of technology very interesting and I want to share what I’ve read up on.

Alright so, if you’re a programmer you’re probably aware of multiple types of syntax. With Python we have:

def MyFunction:
    print("Hello World")

MyFunction()

In Java we have:

public static void main(String[] args)
{
    Chicken();
}

void Chicken()
{
    System.out.println("Hello World");
}

In standard C/C++ we have:

int main(void)
{
    printf("Hello World");
    return 0;
}

But in the old days we had something called K & R syntax in C. It looked like this:

int Chicken(a, b, c)
int a;
float b;
char c;
{
   return 0;
}

What’s interesting about this is that some modern compilers still support this syntax but will scream at you and tell you to not do it. However there’s some important things to note here. Look at the following code block.

int Chicken(a,b,c)
int a;
int b;
{

}

If you notice, I never declared the data type for c. By default, the compiler will use integer data types for anything that is undeclared. So the entire concept behind K & R syntax is that you define the function name, and it’s inputs. Then, you define the types of inputs afterwards. It’s very different from what I was taught in university. I just wanted to share this. Hopefully someone finds this interesting. 🙂

Implementing Binary Search in C++ Practice

So this is something we have all learned in a basic Computer Science course. However, I just wanted to write down a super simple implementation of Binary Search for people who are interested. As you should already know, Binary Search can only be done on a sorted array. This function will only give you the index of the target in the given array. When first calling it, pass 0 for left ptr and array.size() – 1 for the right ptr.

int binarySearch(vector<int>& array, int target, int leftPtr, int rightPtr)
{
   int middle_index = (leftPtr + rightPtr) / 2;
   int potentialMatch = array[middle_index];
   if (target == potentialMatch)
   {
      return middle_index;
   }
   else if (target > potentialMatch)
   {
      return binarySearch(array, target, middle_index + 1, rightPtr);
   }
   else
   {
      return binarySearch(array, target, leftPtr, middle_index - 1);
   }
}