Here I have the code for each of the 4 different sorting methods: Insertion sort
ID: 3721663 • Letter: H
Question
Here I have the code for each of the 4 different sorting methods: Insertion sort, Selection sort, Bubble sort, and Quicksort.
For each of the sorting methods, can someone compute a) the total primitive operations and b) the Big O?
INSERTION SORT:
public class InsertionSort {
public static void main(String[] args) {
int[] A = new int[] { 54, 26, 93, 17, 77, 31, 44, 55, 91 };
System.out.println("Original order: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
insertionSort(A);
System.out.println("After sorting: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
}
private static void insertionSort(int[] A)
{
int N = A.length;
int total = 0;
for (int index = 1; index <= N - 1; index++)
{
int unSortedValue = A[index];
int scan = index;
int count = 1;
while (scan > 0 && A[scan -1] > unSortedValue)
{
A[scan] = A[scan - 1];
scan--;
if (scan > 0)
count += 1;
}
total += count;
A[scan] = unSortedValue;
}
int test = 0;
}
}
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; }
}
BUBBLE SORT:
public static void bubbleSort(int array[])
{
int lastPos; // Marks the last element to compare
int index; // Index of an element to compare
int temp; // Used to swap to elements
// The outer loop positions lastPos at the last element
// to compare during each pass through the array. Initially
// lastPos is the index of the last element in the array.
// During each iteration, it is decreased by one.
for (lastPos = array.length - 1; lastPos >= 0; lastPos--)
{
// The inner loop steps through the array, comparing
// each element with its neighbor. All of the elements
// from index 0 thrugh lastPos are involved in the
// comparison. If two elements are out of order, they
// are swapped.
for (index = 0; index <= lastPos - 1; index++)
{
// Compare an element with its neighbor.
if (array[index] > array[index+1])
{
// Swap the two elements.
temp = array[index];
array[index] = array[index + 1];
array[index + 1] = temp;
}
}
}
QUICK SORT:
import java.util.Arrays;
public class QuickSort
{
public static void main(String[] args)
{
// Create an int array with test values.
int[] A = { 15, 35, 20, 10, 25 };
// Display the array's contents.
System.out.println("Original order: " + Arrays.toString(A));
// Sort the array.
QuickSorter.quickSort(A);
System.out.println();
System.out.println("After sorting: " + Arrays.toString(A));
}
import java.util.*;
import java.util.Arrays;
public class QuickSorter
{
public static void quickSort(int array[])
{
doQuickSort(array, 0, array.length - 1);
}
private static void doQuickSort(int array[], int start, int end)
{
int pivotPoint;
if (start < end)
{
int beforePivotPoint[] = Arrays.copyOfRange(array, start, end+1);
System.out.println(Arrays.toString( beforePivotPoint ) );
pivotPoint = partition(array, start, end);
System.out.println("Pivot Point " + array[pivotPoint] );
doQuickSort(array, start, pivotPoint - 1);
doQuickSort(array, pivotPoint + 1, end);
}
}
private static int partition(int A[], int start, int end)
{
int pivotValue = A[start];
int endOfLeftList = start;
for (int scan = start + 1; scan <= end; scan ++)
{
if (A[scan] < pivotValue)
{
endOfLeftList ++;
swap(A, endOfLeftList, scan);
}
}
swap(A, start, endOfLeftList);
System.out.println("Eoll: " + endOfLeftList);
return endOfLeftList;
}
private static void swap(int[] A, int a, int b)
{
int temp;
temp = A[a];
A[a] = A[b];
A[b] = temp;
}
Explanation / Answer
Solution:
Below is the table which shows the number of comparisons and the Big-O time of the mentioned algorithm.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Algorithm Comparisons Big-O Bubble Sort n^2 O(n^2) Quicksort n log n O(n log n) Insertion sort n^2 O(n^2) Selection sort n^2 O(n^2)Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.