Here I have the code for the sorting method: Selection sort. For the sorting met
ID: 3721666 • Letter: H
Question
Here I have the code for the sorting method: Selection sort.
For the sorting method, can someone compute a) the total primitive operations and b) the Big O?
SELECTION SORT:
public class SelectionSort
{
public static void main(String[] args)
{
int[] A = new int[] { 54, 26, 93, 17, 77, 31, 44, 55, 61 };
System.out.println("Original order: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
int test = selectionSort(A);
System.out.println("After sorting: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
}
private static int selectionSort(int[] A)
{
int N = A.length;
int total = 0;
for (int last = N-1; last >=1; last --)
{
int maxIndex = 0;
int count = 0;
for (int index = 1; index <= last; index++)
{
count += 1;
if (A[index] > A[maxIndex])
maxIndex = index;
}
total += count;
int temp = A[maxIndex];
A[maxIndex] = A[last];
A[last] = temp;
}
return total; }
}
Explanation / Answer
SelectionSort.java
public class SelectionSort
{
public static void main(String[] args)
{
int[] A = new int[] { 54, 26, 93, 17, 77, 31, 44, 55, 61 };
System.out.println("Original order: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
int total = selectionSort(A);
System.out.println("Total primitive operations: "+total);
System.out.println("After sorting: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
}
private static int selectionSort(int[] A)
{
int N = A.length;
int total = 0;
for (int last = N-1; last >=1; last --)
{
int maxIndex = 0;
int count = 0;
for (int index = 1; index <= last; index++)
{
count += 1;
if (A[index] > A[maxIndex])
maxIndex = index;
}
total += count;
int temp = A[maxIndex];
A[maxIndex] = A[last];
A[last] = temp;
}
return total; }
}
Output:
Original order:
54 26 93 17 77 31 44 55 61
Total primitive operations: 36
After sorting:
17 26 31 44 54 55 61 77 93
Big O: It has O(n2) time
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.