# Data Structures: Question Set – 13

#### What is bubble sort?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

#### What is the bubble sort’s time complexity?

Bubble sort has an O(n2) time complexity, where n is the number of elements in the array. Because of this, it is a poor algorithm for huge arrays.

#### How does bubble sort work?

A bubble sort compares nearby elements by continuously iterating across the input array. Two adjacent items are switched if they are out of order (the first is greater than the second). This procedure is repeated until no further swaps are required, at which point the array is said to have sorted.

#### Can you give an illustration of bubble sort?

A bubble sort example utilising the input array [33, 22, 55, 44, 11] is provided below:

Pass 1:

33 and 22 are out of order so swap them: [33, 22, 55, 44, 11]

22 and 55 are in order so don’t swap: [33, 22, 55, 44, 11]

55 and 44 are out of order so swap them: [33, 22, 44, 55, 11]

55 and 11 are out of order so swap them: [33, 22, 44, 11, 55]

Pass 2:

33 and 22 are out of order so swap them: [22, 33, 44, 11, 55]

33 and 44 are in order so don’t swap: [22, 33, 44, 11, 55]

44 and 11 are out of order so swap them: [22, 33, 11, 44, 55]

Pass 3:

22 and 33 are in order so don’t swap: [22, 33, 11, 44, 55]

33 and 11 are out of order so swap them: [22, 11, 33, 44, 55]

Pass 4:

22 and 11 are out of order so swap them: [11, 22, 33, 44, 55]

#### What are some bubble sort’s benefits and drawbacks?

The simplicity and simplicity of use of bubble sort are advantages. Its drawbacks include the fact that it is inefficient for big arrays and that n2 swaps are always performed, even when the array is already sorted.

#### What does insertion sort mean?

A simple sorting technique called insertion sort involves iterating through an array and inserting each element in the right place within a subarray that has been sorted.

#### What is the insertion sort’s time complexity?

Insertion sort has an O(n2) time complexity, where n is the array’s size in elements. Nonetheless, insertion sort can outperform other algorithms for small or nearly sorted arrays.

#### How does the insertion sort operate?

Insertion sort divides the input array into two sections: one that is sorted and the other that is not. The unsorted portion initially just contains the remaining elements after the first element is sorted. Insertion sort chooses the first element from the unsorted section and places it in the sorted part’s proper location after each iteration. The array gets sorted completely once this operation is finished.

#### Can you give an illustration of an insertion sort?

An illustration of insertion sort using the input array [64, 25, 12, 22, 11] is provided below:

Pass 1: Since only the first element is present in the sorted segment and is already in the correct location, no further action is required. The additional components are found in the unsorted portion.

Pass 2: The unsorted part’s first element is 25. This is placed into the sorted section at the appropriate location to produce [25, 64, 12, 22, 11]. The first two elements are now in the sorted part, and the other elements are in the unsorted part.

Pass 3: The unsorted part’s first element, which is 12, is 12. This is added into the sorted section at the appropriate location to produce [12, 25, 64, 22, 11]. The first three elements are now in the sorted part, and the rest are in the unsorted part.

Pass 4: The unsorted part’s first element is 22. This is added into the sorted section at the appropriate location to produce [12, 22, 25, 64, 11]. The first four elements are now in the sorted part, and the final element is in the unsorted part.

Pass 5: The unsorted part’s initial element, 11, is present. This is added into the sorted section at the appropriate location to produce [11, 12, 22, 25, 64]. Now that the array is all sorted.

#### What are some insertion sort’s benefits and drawbacks?

The simplicity and convenience of the use of insertion sort, as well as its effectiveness for small or nearly sorted arrays, are its benefits. Its inefficiency for big arrays and the need to move elements in the sorted segment to make room for new elements are drawbacks.