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
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.
2. Odd-even sort is a variation of ___________
a) Bubble sort
b) Selection sort
c) Insertion sort
d) Gnome sort
View Answer
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
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
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
Explanation: 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
View Answer
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
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
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
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
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.
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
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)
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: 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.
- Check Programming Books
- Practice Computer Science MCQs
- Check Design and Analysis of Algorithms Books
- Check Computer Science Books
- Practice Programming MCQs