Searching and Sorting Algorithms For Interview

Searching and Sorting Algorithms: Selection Sort

1. Introduction

As the name suggests, the selection sorting algorithm helps in sorting the array with the intuition of selecting the elements and placing them at their right position. The selection sorting algorithm involves traversing through the entire array and picking the smallest element first.

This is then swapped with the element on the 0th index of the array. The array is traversed once again to find the second smallest element which is then swapped with the element on the 1st index of the array. This goes on till the entire array is sorted.  

Example array to be sorted -> [14,33,27,10,35,19,42,44]

 

2. Algorithm 

Begin selectionSort(arr, size_of_arr)

for i=0 to i = size_of_arr-1:

smallest_idx = i 

for j = i+1 to j = size_of_arr-1:

if(arr[j]<arr[smallest_idx]) smallest_idx = j

end for

smallest_ele = arr[smallest_idx]

arr[smallest_idx] = arr[i]

arr[i] = smallest_ele

end for 

End

 

Time Complexity - O(N^2)

Space Complexity - O(1)

 

Searching and Sorting Algorithms: Bubble Sort

1. Introduction

Bubble Sort is another sorting algorithm that involves swapping adjacent elements after comparing them. It is like forming a bubble around a pair of elements, comparing them, and then arranging them in ascending order. This is the easiest algorithm to learn and apply. 

Example array to sort -> [50,25,5,20,10]

 

2. Algorithm 

Begin bubbleSort(arr, size_of_arr)

i := size_of_arr - 1

while (i>=1) do:

j:=0

while(j<i) do:

if(arr[j] <arr[j+1])

temp_ele:=arr[j]

arr[j]:=arr[j+1]

arr[j+1]:=temp

end if

j++

end while

i++

end while

end 

Time Complexity - O(n^2)

Space Complexity - O(1)

 

Searching and Sorting Algorithms: Insertion Sort

1. Introduction

The insertion sort as the name suggests is a sorting technique which is used to insert the elements at the right position. You pick an element and find its correct place in the array then you move on to the next element and do the same till there are no elements left. 

Example of array to be sorted = [9,4,5,1,3]

 

2. Algorithm

Begin insertionSort( arr)

for j = 2 to arr.size

key_ele = arr[j]

i:=j-1

while (i>0 and arr[i] >key_ele) 

arr[i+1] = arr[i]

i:i-1

end while

arr[i+1] = key_ele

end for

End

Time Complexity - O(N^2)

Space Complexity - O(1)

Searching and Sorting Algorithms: Counting Sort

1. Introduction

Counting sort as the name suggests is a sorting technique that counts the frequency of every unique element in the array and this frequency is used in mapping to an index of a temporary array taken for sorting.

2. Algorithm 

Begin countingSort(arr, k)

n = arr.size()

create array B[n] and C[k+1]

for i=0 to i=k

C[i]=0

end For

for i=1 to i = n 

C[A[i]] ++

end for

for i =1 to i = k 

C[i] = C[i] + C[i-1]

end for

for i=n to i = 1 

B[C[A[i]]] = A[i]

C[A[i]}--

end for

End

 

Time Complexity = O(N+K)

Space Complexity = O(N+K)

 

Searching and Sorting Algorithms: Heap Sort 

1. Introduction

Heapsort is another simple, easy, and effective sorting algorithm that uses heaps and priority queues. This is an algorithm that can be performed in-place. Example array to be sorted -> [12,6,10,5,1,9]

 

2. Algorithm 

Begin sort(arr)

buildHeap(arr)

for i = n-1 to i = 1:

swap(arr[0],arr[i])

heapify(arr,0,i)

end for

End

 

Begin buildHeap(arrr)

for i = |_ n/2 _| to i = 0: 

heapify(arr,i,n)

end for

End

 

Begin heapify(arr, index, max)

left = 2*index + 1

right = 2*index + 2

if( left<max and arr[left] > arr[index) then 

largest_idx = left 

else largest_idx = index

if(right<max and arr[right]>arr[largest_idx]) then 

largest_idx = right 

if(largest_idx != index) then 

swap(A[i], A[largest_idx])

heapify(arr, largest_idx, max)

End

 

Time Complexity = O(nlogn) 

Space Complexity = O(1) 

 

Practice Problems with Sorting Algorithms

Given below are practice problems specially prepared by team Coding Ninjas for you to ace in your coding interviews. All problems are available in 

Sort by kth bit	Sort an array in wave form	Sort an array according to the count of set bits	Relative sorting	Sort a half-sorted array
Binary array sorting	Minimum number of swaps required to sort an array	Quicksort on linked list	Count inversion	Insertion sort in linked list
Sort linked list	Sort linked list of 0’s, 1’s and 2’s	Build heap	Convert min-heap to max-heap	Convert BST to min-heap
Kth largest element in the unsorted array	Kth largest number	Kth largest sum contiguous subarray	Minimum k product	Kth smallest element
K most frequent words	Minimum and maximum cost to buy N candies	Gary and multiplication	Max game	Last stone weight
Fourth largest element in the array	String transformation	Running median	Minimum character deletion	Sorted matrix

 

Connect n ropes with minimum cost

Frequently Asked Questions

What algorithms are you able to implement during the interview using any programming language?

Every algorithm can be implemented during the coding interview using any programming language. Algorithms are not language-specific.

How do you ace the coding interview?

To ace the coding interview, you need to ensure you are well versed with the basic concepts and have practiced enough. You can take up the newly launched guided paths course on CodeStudio which will be a triumph card for you to ace your next coding interview.

Which sorting algorithms are asked in interviews?

Sorting algorithms like the bubble sort, selection sort, insertion sort, counting sort, merge sort and heap sort can be asked in your coding and technical interview.

What are the three types of sorting?

The three types of sorting can include bubble sort, insertion sort and selection sort.

What is the fastest sorting algorithm?

Quicksort is the fastest sorting algorithm.

Conclusion

Now that you have read the entire blog, you are aware that you can use this blog as your revision notes or a practice handbook during the Coding Interviews.

Make sure you have understood the intuition behind the algorithm and you know how the algorithm works. After that practice, this can’t be stressed enough, practice as much as you can and there will be nothing that can stop you from acing your next coding interview!