Odd-Even Sort – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Odd-Even Sort”.

1. Odd-even sort is a comparison based sort.
A) true
B) false

Explanation: For sorting, odd-even sort compares the values of different elements in the sequence. As a result, it’s a comparison-based kind.

2. Brick sort uses which of the following methods for sorting the input?
A) selection
B) partitioning
C) merging
D) exchanging

Explanation: The method of swapping is used in brick sort, as it swaps out the elements that are out of order. There are two stages to this swapping: odd phase and even phase.

3. What is the worst case time complexity of odd-even sort?
A) O(n)
B) O(n log n)
C) O(n2)
D) O(log n)

Explanation: When the input array is reverse sorted, the worst case complexity is observed. This is the same as the bubble sort’s worst case complexity.

4. What is the best case time complexity of odd-even sort?
A) O(n)
B) O(n log n)
C) O(n2)
D) O(log n)

Explanation: When the input array is already sorted, the best case complexity is observed. This is the same as the bubble sort’s best case difficulty.

5. What is the average case time complexity of odd-even sort?
A) O(n)
B) O(n log n)
C) O(n2)
D) O(log n)

Explanation: Odd-even sort, on average, takes O(n2) time because it applies bubble sort to the elements in two stages before they are sorted.

6. How many odd and even phases are required respectively to sort the given array using odd-even sort.arr={3,2,3,8,5,6,2,1}.
A) 3,3
B) 4,4
C) 3,4
D) 4,3

Explanation: The odd-even kind is used. Bubble sort the list in two steps until it is sorted. To sort the array, a total of eight phases will be needed. One of these four phases will be odd, while the other four will be even.

7. Which of the following function correctly represents odd-even sort?
A)

void oddEvenSort(int arr[], int n)
{
	bool Sorted = false; 
        while (!Sorted)
	{
		Sorted = true;
	        for (int i=1; i<n-2; i=i+2)
		{
			if (arr[i] > arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
                for (int i=0; i<n-2; i=i+2)
		{
			if (arr[i] > arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
	}
	return;
}

B)

void oddEvenSort(int arr[], int n)
{
	bool Sorted = false; 
        while (!Sorted)
	{
		Sorted = true;
	        for (int i=1; i<n-1; i=i+2)
		{
			if (arr[i] > arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
                for (int i=0; i<n-1; i=i+2)
		{
			if (arr[i] > arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
	}
	return;
}

C)

void oddEvenSort(int arr[], int n)
{
	bool Sorted = false; 
        while (!Sorted)
	{
		Sorted = true;
	        for (int i=1; i<n-1; i=i+2)
		{
			if (arr[i] < arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = true;
			}
		}
                for (int i=0; i<n-1; i=i+2)
		{
			if (arr[i] < arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = true;
			}
		}
	}
	return;
}

D)

void oddEvenSort(int arr[], int n)
{
	bool Sorted = false; 
        while (!Sorted)
	{
		Sorted = true;
	        for (int i=1; i<n-1; i=i+1)
		{
			if (arr[i] < arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
                for (int i=0; i<n-1; i=i+1)
		{
			if (arr[i] < arr[i+1])
			{
				swap(arr[i], arr[i+1]);
				Sorted = false;
			}
		}
	}
	return;
}


Explanation: Bubble sort is applied in two steps, odd and even, before the array is sorted. Bubble sort is applied to odd indexed elements in the odd phase and even indexed elements in the even phase.

8. Odd-even sort is also known as ____________
A) stupid sort
B) smart sort
C) brick sort
D) bogo sort

Explanation: The odd-even kind is also known as a brick kind. Habermann proposed this algorithm in 1972, and it was originally designed for parallel computation of local interconnection.

9. Odd-even sort is a variation of ___________
A) Bubble sort
B) Selection sort
C) Insertion sort
D) Gnome sort

Explanation: Bubble sort is quite similar to odd-even sort. It operates by sorting bubbles in two phases: odd and even. Bubble sort is used on odd indexed elements in the odd phase and on even indexed elements in the even phase.

10. Auxiliary space requirement of odd-even sort is ___________
A) O(n)
B) O(log n)
C) O(1)
D) O(n2)

Explanation: The input array itself is manipulated in the odd-even form. As a result, sorting does not necessitate any additional space. As a result, it necessitates constant auxiliary space.

11. Which of the following sorting algorithm is NOT stable?
A) Quick sort
B) Brick sort
C) Bubble sort
D) Merge sort

Explanation: The only algorithm that isn’t stable among the options is fast type. The brick sort, like the bubble sort, is a reliable sorting method.

12. Which of the following sorting algorithm is in place?
A) brick sort
B) merge sort
C) counting sort
D) radix sort

Explanation: Since it only needs constant auxiliary space for manipulating the input list, brick sort is an in place sorting technique.

An odd–even sort, also known as brick sort[1][self-published source] or parity sort, is a relatively simple sorting algorithm designed for use on parallel processors with local interconnections. It’s a contrast sort that shares a lot of characteristics with bubble sort. It works by comparing all odd/even indexed pairs of adjacent elements in the list and switching the elements if one pair is in the wrong order (the first is larger than the second). This is repeated for even/odd indexed pairs in the next step (of adjacent elements). Then, once the list is sorted, it alternates between odd/even and even/odd measures.



Leave a Reply

Your email address will not be published. Required fields are marked *