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

«
»

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

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

Answer: c
Explanation: 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.
advertisement

2. Odd-even sort is a variation of ___________
a) Bubble sort
b) Selection sort
c) Insertion sort
d) Gnome sort
View Answer

Answer: a
Explanation: 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(n2)
View Answer

Answer: c
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

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

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

Answer: a
Explanation: 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
View Answer

Answer: d
Explanation: 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(n2)
d) O(log n)
View Answer

Answer: c
Explanation: 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(n2)
d) O(log n)
View Answer

Answer: a
Explanation: 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(n2)
d) O(log n)
View Answer

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

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
View Answer

Answer: b
Explanation: 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)

advertisement
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;
}
View Answer
Answer: b
Explanation: 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.
 
 

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn