SortingAlgorithms-insertionSort-selection by min

SortingAlgorithms-insertionSort.java

//11 12 22 25 64
public class SortingAlgorithms {


      //Selection Sort (by minimum)
	  //la fiecare pas , gasim minimul in subsirul [i, n-1]
	  //si il punem pe pozitia i prin swap

	public static void selectionByMin(int[] arr) {

		 int n = arr.length;

		 for(int i = 0; i < n - 1; i++) {

		 	  int minIndex = i;

		 	  for(int j = i + 1; j < n; ++j) {

		 	  	       if(arr[ j ] < arr[minIndex]) {

		 	  	       	       minIndex = j;
		 	  	       }  
		 	  }

		 	  //swap arr[i] <----> arr[minIndex]

		 	  if(minIndex != i) {
		 	  	  int temp = arr[minIndex];
		 	  	  arr[minIndex] = arr[i];
		 	  	  arr[i] = temp;
		 	  }
		 }
	}

	public static void InsertionSort(int[] arr) {

		          //la fiecare pas i, luam elementul arr[i] si il inseram in pozitia corecta
		          //din subsirul sortat [0,...,01]
		//           int[] arr1 = {64, 25 12, 22, 11};
		 //                            key
		//           int[] arr1 = {10, 64, 12, 22, 11};
		//           int[] arr1 = {12, 25, 64, 22, 11};
		                                 //KEY

		          int n = arr.length;

		          for(int i = 1; i < n; i++) {

		          	  int key = arr[i];  //12

		          	  int j = i - 1;//1-1=0

		          	  //deplasam elementele mai mari decat KEY cu o pozitie la DREAPTA
		          	  while(j>=0 && arr[j] > key) {

		          	  	arr[j+1] = arr[j];//arr[0+1] = arr[1] = 64
		          	  	j--;

		          	  }

		          	  arr[j+1] = key;//j = j - 1 = 0-1 =-1//-1+1 = 0 ;arr[0] = 25
		          }
	}	


	public static void printArray(int[] arr) {
 

           System.out.print("[");

           for(int i = 0; i < arr.length; ++i) {

               System.out.print(arr[i]);

               if(i < arr.length-1) System.out.print(", ");
           }

           System.out.print("]");
	}


	public static void main(String[] args) {

           int[] arr1 = {64, 25, 12, 22, 11};
           //int[] arr2 = {11,12,22,25,64};

           System.out.println("Array initial: ");
           printArray( arr1 );

           InsertionSort(arr1);

           System.out.println("Array dupa Insertion Sort: ");
           printArray( arr1 );
	}

}

//complexitate O(n^2)

//pentru seturi mici de date: Bubblesort, selection by minimum, insertion sort

//pentru N mare quicksort , mergesort 

//1.backtracking; (permutari, submutimile, partitiile, problema damelor)

//2.divide et Impera 

//3.Greedy arr = [1, 3.4, 2, -3, 3.14]; a gasi un subsir de suma maximala

//4. Dynamic Programming (problema triunghiului, problema rucsacului)
//