Sort

package com.u.util.arithmetic.sort;

import java.util.Random;

public class MySort {
	
	public MySort()
	{
		
	}
	
	//bobble sort
	public static void test(int[] arr, int length)
	{
		length = arr.length;
		int temp = 0;
		for(int i = 0; i < length; i++)
		{
			for(int j = 0; j < i; j++)
			{
				if(arr[i] < arr[j])
				{
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}
	
	public static void _main(String[] args) {
		
		Random rand = new Random(System.currentTimeMillis());
		final int MAX = 100;
		int[] arr = new int[MAX];
		
		for(int i = 0; i < arr.length; i++)
		{
			arr[i] = rand.nextInt();
		}
		
		MySort.test(arr, arr.length);
		
		for(int i = 0; i < arr.length; i++)
		{
			System.out.println(arr[i]);
		}
	}
	
	public static void __main(String[] args) {
		/*
		 * quick sort
		 */
		int[] _arr = new int[]{5,7,2,9,4,6,3,1};
		for(int i: _arr)
		{
			System.out.print(i + " ");
		}
		System.out.println();
		
		(new MySort()).quickSort(_arr, 0, _arr.length - 1);
		
		for(int i: _arr)
		{
			System.out.print(i + " ");
		}
	}
	
	//quick sort Recursion
	public void quickSort(int[] arr, int low, int hight)
	{
		if(low < hight)
		{
			int middle = this.findMiddle(arr, low, hight);
			quickSort(arr, low, middle);
			quickSort(arr, middle + 1, hight);
		}
		else
			return;
	}
	
	public int getMiddle(int[] arr, int low, int hight)
	{
		int middle = 0;
		if(low < hight)
		{
			middle = (low + hight) / 2;
		}
		return middle;
	}
	
	public int findMiddle(int[] arr, int low, int hight)
	{
		/*
		int left = arr[low];
		int right = arr[hight];
		*/
		/*
		 * 5,7,2,9,4,6,3,1          f	f
		 * 1,7,2,9,4,6,3,5			f	t
		 * 1,5,2,9,4,6,3,7			t	f
		 * 1,3,2,9,4,6,5,7			f	
		 * 1,3,2,5,4,6,9,7
		 * 1,3,2,4,5,6,9,7
		 * 
		 * 1,5,2,7,4,6,3,9
		 */
		int left = low;
		int right = hight;
		int temp = 0;
		boolean flag = false;
		while(left < right)
		{
			if(arr[left] > arr[right])
			{
				flag = !flag;
				temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
				if(flag)
					left++;
				else
					right--;
			}
			else
				if(!flag) right--;
				else left++;
		}
		return left;
	}
	
	public static void main(String[] args) {
		int[] arr = new int[]{5,7,2,9,4,6,3,1};
		arr = new int[]{69, 0, 70, 6, 38, 38, 24, 56, 44, 26, 73, 77, 30, 45, 97, 65};
		(new MySort()).quickSort(arr, 0, arr.length - 1);
		for(int i: arr)
		{
			System.out.print(i + " ");
		}
	}
}