Answer to Question #186433 in Java | JSP | JSF for Haider

Question

Using a random number generator, create an array of 1000 integers. Apply bubble sort, insertion sort, selection sort, quick sort, and merge sort on that array. Calculate the execution time of sorting algorithms on the array. Write a report on the performance of these sorting algorithms based on your experimentation.

Answer 1

public class ArraySortTester {


	public static void main(String[] args) {
		int[] array = new int[1000];
		System.out.println("Unsorted array: ");
		for (int i = 0; i < array.length; i++) {
			array[i] = (int) (Math.random() * 100);
			System.out.print(array[i] + " ");
		}
		int arrayTwo[] = array.clone();
		int arrayThree[] = array.clone();
		int arrayFour[] = array.clone();
		int arrayFive[] = array.clone();
		System.out.println("Timing of Bubble sort for array: ");
		long time = System.currentTimeMillis();
		bubble(array);
		System.out.println(System.currentTimeMillis() - time);
		System.out.println();
		System.out.println("Timing of Insertion sort for array: ");
		long timeTwo = System.currentTimeMillis();
		insertionSort(arrayTwo);
		System.out.println(System.currentTimeMillis() - timeTwo);
		System.out.println();
		System.out.println("Timing of Selection sort for array: ");
		long timeThree = System.currentTimeMillis();
		selectionSort(arrayThree);
		System.out.println(System.currentTimeMillis() - timeThree);
		System.out.println();
		System.out.println("Timing of Selection sort for array: ");
		long timeFour = System.currentTimeMillis();
		quickSort(arrayFour, 0, 999);
		System.out.println(System.currentTimeMillis() - timeFour);
		System.out.println();
		System.out.println("Timing of Selection sort for array: ");
		long timeFive = System.currentTimeMillis();
		mergeSort(arrayFive, 0, 999);
		System.out.println(System.currentTimeMillis() - timeFive);
	}


	public static void bubble(int[] unsorted) {
		int temp;
		boolean sorted = false;
		int length = unsorted.length;


		while (!sorted) {
			sorted = true;


			for (int i = 0; i < length - 1; i++) {
				if (unsorted[i] > unsorted[i + 1]) {
					temp = unsorted[i];
					unsorted[i] = unsorted[i + 1];
					unsorted[i + 1] = temp;
					sorted = false;
				}
			}
		}
	}


	public static void insertionSort(int arr[]) {
		int n = arr.length;
		for (int i = 1; i < n; ++i) {
			int key = arr[i];
			int j = i - 1;
			while (j >= 0 && arr[j] > key) {
				arr[j + 1] = arr[j];
				j = j - 1;
			}
			arr[j + 1] = key;
		}
	}


	public static void selectionSort(int[] nums) {
		for (int i = 0; i < nums.length; i++) {


			int min = i;
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[j] < nums[min]) {
					min = j;
				}
			}
			int swap = nums[i];
			nums[i] = nums[min];
			nums[min] = swap;
		}
	}


	public static int partition(int a[], int beg, int end) {


		int left, right, temp, loc, flag;
		loc = left = beg;
		right = end;
		flag = 0;
		while (flag != 1) {
			while ((a[loc] <= a[right]) && (loc != right))
				right--;
			if (loc == right)
				flag = 1;
			else if (a[loc] > a[right]) {
				temp = a[loc];
				a[loc] = a[right];
				a[right] = temp;
				loc = right;
			}
			if (flag != 1) {
				while ((a[loc] >= a[left]) && (loc != left))
					left++;
				if (loc == left)
					flag = 1;
				else if (a[loc] < a[left]) {
					temp = a[loc];
					a[loc] = a[left];
					a[left] = temp;
					loc = left;
				}
			}
		}
		return loc;
	}


	public static void quickSort(int a[], int beg, int end) {


		int loc;
		if (beg < end) {
			loc = partition(a, beg, end);
			quickSort(a, beg, loc - 1);
			quickSort(a, loc + 1, end);
		}
	}


	public static void mergeSort(int[] array, int low, int high) {
		if (high <= low)
			return;


		int mid = (low + high) / 2;
		mergeSort(array, low, mid);
		mergeSort(array, mid + 1, high);
		merge(array, low, mid, high);
	}


	public static void merge(int[] array, int low, int mid, int high) {
		// Creating temporary subarrays
		int leftArray[] = new int[mid - low + 1];
		int rightArray[] = new int[high - mid];


		// Copying our subarrays into temporaries
		for (int i = 0; i < leftArray.length; i++)
			leftArray[i] = array[low + i];
		for (int i = 0; i < rightArray.length; i++)
			rightArray[i] = array[mid + i + 1];


		int leftIndex = 0;
		int rightIndex = 0;


		for (int i = low; i < high + 1; i++) {
			if (leftIndex < leftArray.length && rightIndex < rightArray.length) {
				if (leftArray[leftIndex] < rightArray[rightIndex]) {
					array[i] = leftArray[leftIndex];
					leftIndex++;
				} else {
					array[i] = rightArray[rightIndex];
					rightIndex++;
				}
			} else if (leftIndex < leftArray.length) {
				array[i] = leftArray[leftIndex];
				leftIndex++;
			} else if (rightIndex < rightArray.length) {
				array[i] = rightArray[rightIndex];
				rightIndex++;
			}
		}
	}
}