Sorting/Searching

Question 1

What is Selection sorting?

Time/Space complexity

Answer 1

Sort by finding the smallest value and placing it at the first index. Move to the next index and find the next lowest value. Keep iterating until reaching end of the array.
Time Complexity: O(n^2)
Space: O(1)

Question 2

Implement Selection

Answer 2

void selectionSort(int[] a) 
	{
		int min = Integer.MAX_VALUE;
		int tmpL = -1;
		for (int i = 0; i < a.length;i++)
		{
			for (int j = i; j < a.length;j++)
			{
				if (min > a[j])
				{
					min = a[j];
					tmpL = j;
				}	
			}

			int tmp = a[i];
			a[tmpL] = tmp;
			a[i] = min;
			min = Integer.MAX_VALUE;
		}
	}

Question 3

What is Insertion sort?

Answer 3

Loop for 2 elements in the array. Find the minimum between the two. Increase the searchable array size by 1. Look for the minimum and move it to the first index, shifting other values to the right. Continue until process complete.
Time: O(n^2)
Space: O (1)

Question 4

Implement insertion

Answer 4

void insertionSort(int[] a)
	{
		for (int i = 1; i < a.length; i++)
		{
			int key = a[i];
			int j = i -1;
			while(j >= 0 &amp;&amp; a[j] > key)
			{
				a[j+1] = a[j];
				j = j-1;
			}
			a[j+1] = key;

	}
}

Question 5

Merge Sort

Answer 5

Merge sort uses divide and conquer to sort an array. It divides an array into two. It recursively divides the subarrays into 2 again and sorts them.
Time(Onlogn)
Space(n)

Question 6

What is Binary Search?

Answer 6

Search a sorted array by dividing into 1/2. Compare the middle with the value, if value is greater, perform binary search on right subarray. If lesser, perform Binary search on left subarray.

Question 7

Implement BinarySearch iteratively

Answer 7

int bSearchIter(int val, int[] arr)
	{
		int start = 0;
		int end = arr.length-1;
		int mid = (end + start) /2;
		while (start <= end)
		{
			mid = (start +end)/2;
			if (arr[mid] < val)
			{
				start = mid+1;
			}
			else if (arr[mid] > val)
			{
				end = mid-1;
			}
			else
			{
				return mid;
			}

	}
	return -1;
}

Question 8

Implement Binary Search Recursively

Answer 8

int bSearch(int val, int[] arr, int start, int end) 
	{
		if (start > end ) return -1;
		int mid =(end+start)/2;
		if (arr[mid] == val) return mid;

		else if (arr[mid] < val)
		{
			return bSearch(val,arr, mid+1,end);
		}
		else if (arr[mid] > val)
		{
			return bSearch(val, arr, 0, mid-1);
		}
		return -1;
	}