250+ TOP MCQs on Odd-Even Sort and Answers

Data Structures & Algorithms Multiple Choice Questions on “Odd-Even Sort”.

1. Odd-even sort is also known as ____________
a) stupid sort
b) smart sort
c) brick sort
d) bogo sort

Answer: c
Clarification: Odd-even sort is also known by the name of a brick sort. This algorithm was first proposed by Habermann in 1972 and was initially invented for parallel computation of local interconnection.

2. Odd-even sort is a variation of ___________
a) Bubble sort
b) Selection sort
c) Insertion sort
d) Gnome sort
Answer: a
Clarification: Odd-even sort is very similar to bubble sort. It works by applying bubble sort in two phases I.e odd phase and even phase. In odd phase bubble sort is applied on odd indexed elements and in even phase bubble sort is applied on even indexed elements.

3. Auxiliary space requirement of odd-even sort is ___________
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)

Answer: c
Clarification: In odd-even sort manipulation is done on the input array itself. So no extra space is required to perform sorting. Thus it requires constant auxiliary space.

4. Which of the following sorting algorithm is NOT stable?
a) Quick sort
b) Brick sort
c) Bubble sort
d) Merge sort

Answer: a
Clarification: Out of the given options quick sort is the only algorithm which is not stable. Brick sort like bubble sort is a stable sorting algorithm.

5. Which of the following sorting algorithm is in place?
a) brick sort
b) merge sort
C) counting sort
D) radix sort

Answer: a
Clarification: Brick sort is an in place sorting technique as it only requires constant auxiliary space for manipulating the input array.

6. Odd-even sort is a comparison based sort.
a) true
b) false

Answer: a
Clarification: Odd-even sort compares the value of different elements in the array for sorting. Thus, it is a comparison based sort.

7. Brick sort uses which of the following methods for sorting the input?
a) selection
b) partitioning
c) merging
d) exchanging

Answer: d
Clarification: Brick sort uses the method of exchanging as it swaps the elements which are out of order. This swapping is done in two phases i.e. odd phase and even phase.

8. What is the worst case time complexity of odd-even sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: Worst case complexity is observed when the input array is reverse sorted. This is the same as the worst case complexity of bubble sort.

9. What is the best case time complexity of odd-even sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: a
Clarification: Best case complexity is observed when the input array is already sorted. This is the same as the best case complexity of bubble sort.

10. What is the average case time complexity of odd-even sort?
a) O(n)
b) O(n log n)
c) O(n²)
d) O(log n)

Answer: c
Clarification: Odd-even sort takes O(n²) time on average as it keeps on applying bubble sort on the elements in two phases until they are sorted.

11. 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

Answer: b
Clarification: Odd-even sort applies bubble sort in two phases until the array gets sorted. So here 8 phases will be required in totality to sort the array. Out of these 4 phases will be odd phase and the other 4 will be even phase.

12. 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;
}

Answer: b
Clarification: We apply bubble sort in two phases i.e. odd and even phase until the array gets sorted. In odd phase bubble sort is applied to odd indexed elements and in even phase bubble sort is applied to even indexed elements.