Recently I started learning about Different Data structure algorithms.
Here I would like to share some results and Java code developed.
Even though I chose to compare simple algorithms, someone could find the code very useful.
It’s obvious from the graph that the Quick Sort much faster. However, if you have sorted data. Insertion sort is faster for a small number of integers. (<10,000)
The following result of having 95% (486400) sorted integers from 512000.
Using Insertion Sort:
98% sorted: time 1.58s
Unsorted: 20.24s.
Quick Sort:
99% sorted: time 0.0160s
Unsorted: 0.0235s
Which makes Insertion sort 12.3 times faster than using insertion sort on the unsorted data.
The conclusion is that Insertion sort become faster but still slower then Quick sort O(nlogn) time. For large data. But if the number of integers is small then quick sort is slower.
The Java code I would like to share allows you easily enter the number of integers to sort. As well as #of times to test and percentage of data being sorted in the beginning.
P.S I also found out the Interesting fact that QuickSort was developed in 1959 by Tony Hoare while trying to sort the words of Russian sentences.
I want to apologize for clearness of the code ahead of time; didn’t have time to clean it up.
package differentalgorithms;
import java.util.Scanner;
/**
*
* @author Vlad Samonin
*/
public class DifferentAlgorithms {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int size = 10; //Specifying Size of array to test
int numberOfSorted = 0;
int TimesToCheck = 10;
// Create a single shared Scanner for keyboard input
Scanner scanner = new Scanner( System.in );
System.out.println("Enter the number of integers to be sorted:");
String StringSize = scanner.nextLine();
size = Integer.parseInt(StringSize);
System.out.println("Enter the Percentage (%) of sorted elements in the begining: For Example 90" );
String SortedIntegers = scanner.nextLine();
numberOfSorted = (int) (Integer.parseInt(SortedIntegers)*0.01*size); //Calculating the numbers to be sorted
System.out.println("The #integers already sorted in the begining: "+numberOfSorted );
System.out.println("How many time you would like to check your result: ");
String NumberOfCheck = scanner.nextLine();
TimesToCheck = Integer.parseInt(NumberOfCheck); //Calculating the numbers to be sorted
int [] NewArray = new int [size];
int [] NewArray2 = new int [size];
long AverageResult=0;
long SecondAverageResult = 0; //Needed to Calculate time it takes for 2nd Array to be sorted
DifferentAlgorithms2 EngAlgorithms = new DifferentAlgorithms2();
//running 10 times the algorithm to get more acurate result.
for (int i =0; i<TimesToCheck; i++)
{
//NewArray = creatingRandomArray(size);
NewArray = creatingAlmostSortedArray(size,numberOfSorted);
//EngAlgorithms.printArray(NewArray);
System.arraycopy( NewArray, 0, NewArray2, 0, NewArray.length ); //making 2nd copy of the array
AverageResult+= EngAlgorithms.insertionsort(NewArray);
EngAlgorithms.StartTimer();
EngAlgorithms.QUICKsort(NewArray2);
SecondAverageResult += EngAlgorithms.TotalTimer();
}
float finalResult = (float)AverageResult/10000; //Converting to seconds and finding average number
float finalResult2 = (float)SecondAverageResult/10000;
String InsertionTime = String.format ("%.4f", finalResult);
String QuickSortingTime = String.format ("%.4f", finalResult2);
System.out.println("The final result of Insertion Sort is: " +InsertionTime + " s");
System.out.println("The final result of Quick Sort is: " +QuickSortingTime + " s");
}
public static int [] creatingAlmostSortedArray (int size, int numberOfSorted)
{
int randomNum = 0;
int minimum = 0;
int maximum = 800;
int count = 0;
int arr[] = new int [size];
for (int i=0; i<numberOfSorted; i++) //Generating Sorted Numbers;
{
count += minimum + (int)(Math.random() * maximum);
arr[i]= count;
}
//This part generates random integers for rest of the array
for (int i=size-1; i>numberOfSorted-1 ;i--)
{
//Creating random number
randomNum = minimum + (int)(Math.random() * maximum);
//Creating an array of integers
arr[i]= randomNum;
}
return arr;
}
public static int [] creatingRandomArray (int size)
{
int randomNum = 0;
int minimum = 0;
int maximum = 9999999;
int arr[] = new int [size];
for (int i=0; i<size ;i++)
{
//Creating random number
randomNum = minimum + (int)(Math.random() * maximum);
//Creating an array of integers
arr[i]= randomNum;
}
return arr;
}
}
// Java program for implementation of Insertion Sort
class DifferentAlgorithms2
{
/*Function to sort array using insertion sort*/
private long startTime;
private long totalTime;
private int array[]; //used only for quick sort
private int length;
public long insertionsort(int arr[])
{ // The basic Insertion Sort Taken from https://www.geeksforgeeks.org/insertion-sort/
int n = arr.length;
StartTimer();
for (int i=1; i<n; ++i)
{
int key = arr[i];
int j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
TotalTimer();
//System.out.println("The total time for Insertion Sort is " + totalTime + " ms");
return totalTime;
}
//Quick Sort Taken from
public void QUICKsort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
//http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void StartTimer()
{
startTime = System.currentTimeMillis();
}
public long TotalTimer()
{
totalTime = System.currentTimeMillis() - startTime;
return totalTime;
}
/* A utility function to print array of size n*/
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
}
Comments (0)