Capgemini interview question

1.Sorting Algorithm like Bubble, Insertion and Selection Sort.

Interview Answer

Anonymous

22 Sept 2024

I gave them brief description : Bubble Sort: Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order (i.e., if the current element is greater than the next element). The process continues until no more swaps are needed. Time Complexity: Best-case: O(n) (when the list is already sorted) Average-case: O(n^2) Worst-case: O(n^2) Bubble Sort is not efficient for large lists due to its quadratic time complexity. Insertion Sort: Insertion Sort builds the final sorted array one item at a time. It iterates through the list, considering each element as a “key” and inserting it into its correct position among the already sorted elements. The key is compared with the elements before it and shifted until it finds its proper place. Time Complexity: Best-case: O(n) (when the list is already sorted) Average-case: O(n^2) Worst-case: O(n^2) Insertion Sort is efficient for small lists or nearly sorted lists. Selection Sort: Selection Sort repeatedly selects the smallest (or largest) element from the unsorted part of the list and places it at the beginning (or end) of the sorted portion. It divides the list into two parts: the sorted part and the unsorted part. In each iteration, it finds the minimum (or maximum) element from the unsorted part and swaps it with the first (or last) element of the sorted part. Time Complexity: Best-case: O(n^2) Average-case: O(n^2) Worst-case: O(n^2) Selection Sort has a fixed number of swaps, making it useful when memory writes are costly.