3.4 Another simple sort is the odd-even sort. The idea is to repeatedly make two
ID: 3744166 • Letter: 3
Question
3.4 Another simple sort is the odd-even sort. The idea is to repeatedly make two passes through the array. On the first pass you look at all the pairs of items,a[j] and a[j+1], where j is odd (j = 1, 3, 5, ...). If their key values are out of order, you swap them. On the second pass you do the same for all the even values (j = 2, 4, 6, ...). You do these two passes repeatedly until the array is sorted. Replace the bubbleSort() method in bubbleSort.java (Listing 3.1) with an oddEvenSort() method. Make sure it works for varying amounts of data. You’ll need to figure out how many times to do the two passes.
The odd-even sort is actually useful in a multiprocessing environment, where a separate processor can operate on each odd pair simultaneously and then on each even pair. Because the odd pairs are independent of each other, each pair can be checked—and swapped, if necessary—by a different processor. This makes for a very fast sort.
Explanation / Answer
Answer
3.4)
Please find my implementation.
Please let me know in case of any issue.
public class OddEvenSort {
// A function to sort the algorithm using Odd Even sort
static void oddEvenSort(int arr[], int n)
{
boolean isSorted = false; // Initially array is unsorted
while (!isSorted)
{
isSorted = true;
// Perform Bubble sort on odd indexed element
for (int i=1; i<=n-2; i=i+2)
{
if (arr[i] > arr[i+1])
{
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
isSorted = false;
}
}
// Perform Bubble sort on even indexed element
for (int i=0; i<=n-2; i=i+2)
{
if (arr[i] > arr[i+1])
{
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
isSorted = false;
}
}
}
}
// A utility function ot print an array of size n
static void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String[] args) {
int arr[] = {34, 2, 10, -9};
int n = 4;
oddEvenSort(arr, n);
printArray(arr, n);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.