Category: Sort

public class QuickSort {

	public static void main(String[] args) {
		
		int arr[] = {1,12,9,14,16,80,33,3,4,7,60,2};
		
		System.out.println("printing an array");
		printArray(arr);
		
		quickSort(arr,0,arr.length-1);
		
		System.out.println("printing a sorted array");
		printArray(arr);
		
		
	}

	static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

	static void quickSort(int arr[], int lowIndex, int highIndex){
		
		if(lowIndex<highIndex){
			
		
			
			int midIndex = partition(arr,lowIndex,highIndex);
			System.out.println("partition array lowIndex::"+lowIndex+", highIndex::"+highIndex);
			printArray(arr);
			
			
			quickSort(arr,lowIndex,midIndex-1);
			quickSort(arr,midIndex+1,highIndex);
			
			
		
			
			
			
		}
		
	}
	
	static int partition(int arr[],int lowIndex, int highIndex){
		int pivot = arr[highIndex];
		
		int i = lowIndex-1;
		
		for(int j=lowIndex;j<=highIndex-1;j++){
			if(arr[j]<pivot){
				i++;
				swap(arr,i,j);
			}
		}

		swap(arr,i+1,highIndex);
		return i+1;
	}
	
	static void swap(int arr[], int i, int j){
		int temp = arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
}

public class MergeSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		 int arr[] = { 12, 11, 13, 5, 6, 7,99,87,0,2,103 };
		 
		 System.out.println("printing an array :::");
		 printArray(arr);
		 
		 sort(arr,0,arr.length-1);
		 
		 System.out.println("printing a sorted array :::");
		 printArray(arr);
	}

	
	static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
	
	public static void sort(int arr[], int startIndex, int endIndex){
		
		if(startIndex==endIndex)
			return;
		int midIndex = (startIndex+endIndex)/2;
		
		sort(arr,startIndex, midIndex);
		sort(arr,midIndex+1,endIndex);
		
		merge(arr, startIndex, midIndex, endIndex);
		
	}
	
	public static void merge(int arr[], int startIndex, int midIndex, int endIndex ){
		
		int size1 = midIndex-startIndex+1;
		int size2 = endIndex-midIndex;
		int firstPart[] = new int[size1];
		int secondPart[] = new int[size2];
		
		System.out.println("startIndex::"+startIndex+", midIndex::"+midIndex+", endIndex::"+endIndex);
		System.out.println("size1 ::"+size1);
		System.out.println("size2 ::"+size2);
		
		
		int i=0,j=0,k=0;
		
		//copy data into the array
		for(i=0;i<size1;i++){
			firstPart[i] = arr[startIndex+i];
		}

		for(j=0;j<size2;j++){
			secondPart[j]=arr[j+midIndex+1];
		}
		
		i=0;
		j=0;
		k=startIndex;
		
		System.out.println("firstPart::");
		printArray(firstPart);
		System.out.println("secondPart::");
		printArray(secondPart);
		
		
		while(i<size1 && j<size2){
			
			if(firstPart[i]<secondPart[j]){
				arr[k]=firstPart[i];
				i++;
				k++;
			} else if(firstPart[i]>=secondPart[j]){
				arr[k]=secondPart[j];
				j++;
				k++;
			}
			
		}
		
		while(i<size1){
			arr[k] = firstPart[i];
			i++;
			k++;
		}
		
		while(j<size2){
			arr[k]=secondPart[j];
			j++;
			k++;
		}
		
		System.out.println("Merget Array::");
		printArray(arr);
		
	}
}

public class InsertionSort {

	public static void main(String[] args) {
	
		int arr [] = {1,11,2,8,19,4,3,9}; 
		
		int temp;
		for(int i = 1; i < arr.length;i++){
			
			int j = i-1;
			while(j>=0 && arr[j]>arr[j+1]){
				temp = arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
				j--;
			}
			
		}
		
		printArray(arr);

	}

	public static void printArray(int arr[]){
		for(int k=0;k<arr.length;k++)
			System.out.println(arr[k]);
	}
}

import java.util.ArrayList;

public class SelectionSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {21,12,14,1,26,34,67,45,0};
		
		int minimum,temp;
		for(int i=0;i<arr.length;i++){
			minimum = i;
			for(int j=i+1;j<arr.length;j++){
				if(arr[j]<arr[minimum]){
					minimum = j;
				}
			}
			
			temp = arr[i];
			arr[i] = arr[minimum];
			arr[minimum]=temp;
		}
		
		System.out.println("Sorted array::");
		printArray(arr);
	}
	
	public static void printArray(int arr[]){
		for(int i=0;i<arr.length;i++)
			System.out.println(arr[i]);
	}
}

public class BubbleSort {

	public static void main(String[] args) {

		int arr[] = {21,12,14,1,26,34,67,45,0};
		int temp;
		for(int i=0;i<arr.length;i++){
			
			for(int j=0;j<(arr.length-i-1);j++){
				
				if(arr[j]>arr[j+1]){
					temp = arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
		}
	
		printArray(arr);
		
	}

	public static void printArray(int array[]){
		
		System.out.println("Printing sorted array ::");
		for(int i=0;i<array.length;i++)
			System.out.println(array[i]);
		
	}
}