Sorting

 bubblesort


package com.demo.test;


import java.lang.reflect.Array;

import java.util.Arrays;


public class TestBubbleSort {


public static void main(String[] args) {

int[] arr= {65,35,26,13,23,12,91};

System.out.println("Given array :");

System.out.println(Arrays.toString(arr));

bubbleSort(arr);

System.out.println("sorted array");

System.out.println(Arrays.toString(arr));


}

private static void improvedbubbleSort(int[] arr) {

int n=arr.length;

int swapcount=0;

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

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

//swapping data

if(arr[j-1]>arr[j]) {

int temp=arr[j];

arr[j]=arr[j-1];

arr[j-1]=temp;

swapcount++;

}

}

System.out.println("iteration "+(i+1)+" Swapcount : "+swapcount);

System.out.println(Arrays.toString(arr));

if(swapcount==0) {

break;

}

swapcount=0;

}


private static void bubbleSort(int[] arr) {

int n=arr.length;

int swapcount=0;

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

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

//swapping data

if(arr[j-1]>arr[j]) {

int temp=arr[j];

arr[j]=arr[j-1];

arr[j-1]=temp;

swapcount++;

}

}

System.out.println("iteration "+(i+1)+" Swapcount : "+swapcount);

System.out.println(Arrays.toString(arr));

if(swapcount==0) {

break;

}

swapcount=0;

}

}


}




---------------------------------------------------------------------------------------------------------------------------------------

//insertion sort



package com.demo.test;


import java.util.Arrays;


public class TestInsertionSort {


public static void main(String[] args) {

int[] arr= {65,35,26,14,23,12,91};

System.out.println("before sorting");

System.out.println(Arrays.toString(arr));

insertionsort(arr);

System.out.println("After sorting");

System.out.println(Arrays.toString(arr));


}


private static void insertionsort(int[] arr) {

int n=arr.length;

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

//place j at the end of sorted portion of the array

int j=i-1;

int key=arr[i];

while(j>=0 && arr[j]>key) {

//shift values one location 0n the right side 

arr[j+1]=arr[j];

j--;

}

arr[j+1]=key;

System.out.println("iteration : "+i);

System.out.println(Arrays.toString(arr));

}

}


}


-------------------------------------------------------------------------------------------------------------

//mergesort



package com.demo.test;


import java.util.Arrays;


public class TestMergeArray {

public static void merge(int[] arr1,int[] arr2,int[] arr3) {

int i=0,j=0,k=0;

while(i<arr1.length && j<arr2.length) {

if(arr1[i]<arr2[j]) {

arr3[k]=arr1[i];

i++;

k++;

}else {

arr3[k]=arr2[j];

j++;

k++;

}

}

//copy remaining part of arr1 into arr3

while(i<arr1.length) {

arr3[k]=arr1[i];

i++;

k++;

}

//copy remaining part of arr2 into arr3

while(j<arr2.length) {

arr3[k]=arr2[j];

j++;

k++;

}

}


public static void main(String[] args) {

int[] arr1= {3,4,10,15,17,18,30,34,35,37};

int[] arr2= {2,10,12,14,16,17,20,21,25,27};

int[] arr3=new int[arr1.length+arr2.length];

merge(arr1,arr2,arr3);

System.out.println(Arrays.toString(arr3));


}


}


----------------------------------------------------------------------------------------------------------------------------


package com.demo.test;


import java.util.Arrays;


public class TestQuickSort {


public static void main(String[] args) {

int[] arr= {13,18,27,2,19,25};

System.out.println("Before sorting");

System.out.println(Arrays.toString(arr));

int n=arr.length-1;

quicksort(arr,0,n);

System.out.println("After sorting");

System.out.println(Arrays.toString(arr));


}


private static void quicksort(int[] arr, int first, int last) {

int pivot=first;

int i=first;

int j=last;

//minimum size od array should be 2

if(first<last) {

while(i<j) {

while(arr[i]<=arr[pivot] && i<last) {

i++;

}

while(j>pivot && arr[j]>arr[pivot] ) {

j--;

}

if(i<j) {

//swap i and j

int temp=arr[i];

arr[i]=arr[j];

arr[j]=temp;

}

}

//swap pivot with j

int temp=arr[pivot];

arr[pivot]=arr[j];

arr[j]=temp;

System.out.println("pivot : "+arr[j] +"-----"+j);

System.out.println(Arrays.toString(arr));

quicksort(arr, first, j-1);

quicksort(arr, j+1, last);

}

}


}


--------------------------------------------------------------------------------------------------------------------------------------


//selectionsort


package com.demo.test;


import java.util.Arrays;


public class TestSelectionSort {

public static void main(String[] args) {

int[] arr= {23,4,1,5,20,36,78,3,7};

System.out.println("Before sorting");

System.out.println(Arrays.toString(arr));

selectionsort(arr);

System.out.println("After sorting");

System.out.println(Arrays.toString(arr));

}


private static void selectionsort(int[] arr) {

   //i gives the begining of unsorted part

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

{

int min_idx=i;

//find the index position of minimum number in unsorted part of array

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

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

min_idx=j;

}

}

//swap 2 elements

int temp=arr[i];

arr[i]=arr[min_idx];

arr[min_idx]=temp;

System.out.println("Minimum number "+arr[i]+"==="+arr[min_idx]);

System.out.println(Arrays.toString(arr));

}

}


}


-----------------------------------------------------------------------------------------------------------

//heapsort



package com.demo.test;


import java.util.Arrays;


public class TestHeapSort {


public static void main(String[] args) {

int[] arr= {1,12,9,5,6,10};

System.out.println("Before sorting");

System.out.println(Arrays.toString(arr));

heapsort(arr);

System.out.println("After sorting");

System.out.println(Arrays.toString(arr));


}


private static void heapsort(int[] arr) {

int n=arr.length;

//converts entire tree in to max heap --->heapify the tree

for(int i=(n/2)-1;i>=0;i--) {

heapify(arr,n,i);

}

//displaying maxheap

System.out.println(Arrays.toString(arr));

//swap first value with last value

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

int temp=arr[0];

arr[0]=arr[i];

arr[i]=temp;

heapify(arr,i,0);

System.out.println("Sorted "+i);

System.out.println(Arrays.toString(arr));

}

}


//it will convert a tree whose parent is at i th index position

private static void heapify(int[] arr, int n, int i) {

//find largest among parent left and right

int largest=i;

int left=2*i+1;

int right=2*i+2;

//compare left and parent , if left is with in bound

if(left<n && arr[left]>arr[largest]) {

largest=left;

}

if(right<n && arr[right]>arr[largest]) {

largest=right;

}

//swap if the parent is not largest

if(largest!=i) {

int temp=arr[i];

arr[i]=arr[largest];

arr[largest]=temp;

heapify(arr,n,largest);

}

}


}













---------------------------------------------------------------------------------------------------------------------------------


//countsort



package com.demo.test;


import java.util.Arrays;


public class TestCountSort {

public static void main(String[] args) {

int[] arr= {4,2,2,8,3,3,1};

System.out.println("Before sort");

System.out.println(Arrays.toString(arr));

int[] sorteddata=countingSort(arr);

System.out.println("After sort");

System.out.println(Arrays.toString(sorteddata));

}


private static int[] countingSort(int[] arr) {

//find max

int max=findmax(arr);

//create a array of size max+1

int[] counter=new int[max+1];

//find occurences of every number

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

//int idx=arr[i];

//counter[idx]++;

counter[arr[i]]++;

}

System.out.println("couter array");

System.out.println(Arrays.toString(counter));

//find cumulative sum

for(int i=1;i<counter.length;i++) {

counter[i]=counter[i]+counter[i-1];

}

System.out.println("cummulative sum couter array");

System.out.println(Arrays.toString(counter));

//create a output array

int[] output=new int[arr.length];

//fill the values in output array

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

/*int idx=arr[i];

int pos=counter[idx]-1;

counter[idx]--;

output[pos]=arr[i]*/

output[counter[arr[i]]-1]=arr[i];

counter[arr[i]]--;

}

return output;

}


private static int findmax(int[] arr) {

int max=arr[0];

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

if(max<arr[i]) {

max=arr[i];

}

}

return max;

}


}


-------------------------------------------------------------------------------------------------------------------------------------



Comments

Post a Comment

Popular posts from this blog

Abtsract class

 import java.util.Scanner; abstract class Book {     String title;     abstract void setTitle(String s);     String getTitle() {         return title;     } } class MyBook extends Book {     @Override     void setTitle(String s) {         this.title = s;      } } public class Main {     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         String title = scanner.nextLine();          MyBook new_novel = new MyBook();         new_novel.setTitle(title);          System.out.println("The title is: " + new_novel.getTitle());     } }
Read more

LinkedList

 singlelinkedlist package com.demo.linkedlist; public class SinglyLinkedList { class Node{ int data; Node next; public Node(int data) { super(); this.data = data; this.next=null; } }    Node head; public SinglyLinkedList() { head=null; } //add newnode at the end public void addNode(int val){ //to create a new node Node newnode=new Node(val); //if list is empty, then add at the begining if(head==null) { head=newnode; }else { Node temp=head; while(temp.next!=null) { temp=temp.next; } temp.next=newnode; } } public int searchbyvalue(int val) { if(head==null) { System.out.println("List is empty"); }else { Node temp=head; int pos=0; while(temp!=null && temp.data!=val) { temp=temp.next; pos++; } if(temp!=null) { return pos; } } return -1; } public void addByPosition(int val,int pos) { if(head==null &...
Read more