Data Structures & Algorithms Multiple Choice Questions on “Odd-Even Sort”.
1. Odd-even sort is also known as ____________ Answer: c 2. Odd-even sort is a variation of ___________ 3. Auxiliary space requirement of odd-even sort is ___________ Answer: c 4. Which of the following sorting algorithm is NOT stable? Answer: a 5. Which of the following sorting algorithm is in place? Answer: a 6. Odd-even sort is a comparison based sort. Answer: a 7. Brick sort uses which of the following methods for sorting the input? Answer: d 8. What is the worst case time complexity of odd-even sort? Answer: c 9. What is the best case time complexity of odd-even sort? Answer: a 10. What is the average case time complexity of odd-even sort? Answer: c 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}. Answer: b 12. Which of the following function correctly represents odd-even sort? b) c) d) Answer: b
a) stupid sort
b) smart sort
c) brick sort
d) bogo sort
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.
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.
a) O(n)
b) O(log n)
c) O(1)
d) O(n2)
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.
a) Quick sort
b) Brick sort
c) Bubble sort
d) Merge sort
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.
a) brick sort
b) merge sort
C) counting sort
D) radix sort
Clarification: Brick sort is an in place sorting technique as it only requires constant auxiliary space for manipulating the input array.
a) true
b) false
Clarification: Odd-even sort compares the value of different elements in the array for sorting. Thus, it is a comparison based sort.
a) selection
b) partitioning
c) merging
d) exchanging
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.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
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.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
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.
a) O(n)
b) O(n log n)
c) O(n2)
d) O(log n)
Clarification: 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.
a) 3,3
b) 4,4
c) 3,4
d) 4,3
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.
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;
}
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;
}
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;
}
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;
}
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.