Believe into

* 이진 탐색 트리

package algo.bstree;

import java.util.ArrayList;
import java.util.List;

public class BSTree {

	public enum DIR {
		LEFT, RIGHT
	}

	public class Node {

		public int data;
		public Node left;
		public Node right;

		public Node(int data) {
			this.data = data;
			left = null;
			right = null;
		}
	}

	public Node root;

	public void insert(int data) {

		Node newNode = new Node(data);

		if (root == null) {
			root = newNode;
			return;
		}

		Node current = root;
		Node parent = null;

		while (true) {

			parent = current;

			if (current.data == data) {

				System.out.println("이미 있는 데이터 입니다 : " + data);
				return;

			} else if (current.data < data) {

				current = current.right;
				if (current == null) {
					parent.right = newNode;
					System.out.println("노드 삽입 : " + data);
					return;
				}

			} else {

				current = current.left;
				if (current == null) {
					parent.left = newNode;
					System.out.println("노드 삽입 : " + data);
					return;
				}

			}

		}
	}

	public void find(int data) {

		find(root, data);

	}

	private Node find(Node node, int data) {

		if (node == null) {
			System.out.println("찾는 데이터가 없습니다 : " + data);
			return null;
		}

		if (node.data == data) {
			System.out.println("찾았습니다 : " + data);
			return node;
		}

		if (node.data < data)
			return find(node.right, data);
		else
			return find(node.left, data);

	}

	public void delete(int data) {

		Node current = root;
		Node parent = root;
		DIR dir = null;

		if (current == null) {
			System.out.println("삭제할 데이터가 없습니다 : " + data);
			return;
		}

		while (current.data != data) {

			parent = current;

			if (current.data < data) {

				current = current.right;
				dir = DIR.RIGHT;

			} else {

				current = current.left;
				dir = DIR.LEFT;
			}

			if (current == null) {
				System.out.println("삭제할 데이터가 없습니다 : " + data);
				return;
			}

		}

		if (current.left == null && current.right == null) {

			// 삭제할 노드가 자식을 갖지 않는 경우

			if (current == root) {
				// 루트 노드밖에 없는 경우
				current = null;
				root = null;
			} else {
				if (dir == DIR.LEFT)
					parent.left = null;
				else
					parent.right = null;
			}

		} else if (current.right == null || current.left == null) {

			// 삭제할 노드가 자식을 한개만 갖는경우

			if (current == root) {
				// 루트 노드 인 경우
				root = current.right == null ? current.left : current.right;
			} else {

				if (dir == DIR.LEFT) {
					parent.left = current.right == null ? current.left : current.right;
				} else {
					parent.right = current.right == null ? current.left : current.right;
				}
			}

		} else {
			// 자식 노드가 둘다 있는 경우
			// current 노드가 자식을 둘다 갖는경우, Successor를 current에 Set해줘야한다.
			Node successor = getSuccessor(current);
			if (current == root) {

				root = successor;

			} else {

				if (dir == DIR.LEFT)
					parent.left = successor;
				else
					parent.right = successor;

			}

			successor.left = current.left;
		}

		if (root == null || root == current)
			System.out.println("루트 노드 삭제 : " + data);
		else
			System.out.println("노드 삭제 : " + data);

	}

	public Node getSuccessor(Node delNode) {

		// successor는 Right Sub Tree 중에서 가장 작은 값이다.

		Node successor = delNode.right;
		Node successorParent = delNode;

		while (successor.left != null) {
			successorParent = successor;
			successor = successor.left;
		}

		// successor가 Del Node의 오른쪽 자식과 같다면
		// sucessor의 right 트리는 그대로 따라 올라간다.
		if (delNode.right != successor) {
			successorParent.left = successor.right;
			successor.right = delNode.right;
		}

		return successor;
	}

	public void inOrder(Node node) {
		if (node != null) {
			inOrder(node.left);
			System.out.print(" " + node.data);
			inOrder(node.right);
		}
	}

	public void printPreety() {
		List<Node> list = new ArrayList<Node>();
		list.add(root);
		printTree(list, getHeight(root));
	}

	private int getHeight(Node head) {

		if (head == null) {
			return 0;
		} else {
			return 1 + Math.max(getHeight(head.left), getHeight(head.right));
		}
	}

	private void printTree(List<Node> levelNodes, int level) {

		List<Node> nodes = new ArrayList<Node>();

		// indentation for first node in given level
		printIndentForLevel(level);

		for (Node Node : levelNodes) {

			// print node data
			System.out.print(Node == null ? " " : Node.data);

			// spacing between nodes
			printSpacingBetweenNodes(level);

			// if its not a leaf node
			if (level > 1) {
				nodes.add(Node == null ? null : Node.left);
				nodes.add(Node == null ? null : Node.right);
			}
		}
		System.out.println();

		if (level > 1) {
			printTree(nodes, level - 1);
		}
	}

	private void printIndentForLevel(int level) {
		for (int i = (int) (Math.pow(2, level - 1)); i > 0; i--) {
			System.out.print(" ");
		}
	}

	private void printSpacingBetweenNodes(int level) {
		// spacing between nodes
		for (int i = (int) ((Math.pow(2, level - 1)) * 2) - 1; i > 0; i--) {
			System.out.print(" ");
		}
	}

}

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.binarytree.MyBinaryTree;
import algo.binarytree.MyBinaryTree.DIR;
import algo.binarytree.MyBinaryTree.MyBTNode;
import algo.bstree.BSTree;
import algo.radix.MyRadixSort;

public class Main {

	public static void main(String[] args) {

		BSTree tree = new BSTree();
		makeBinarySearchTree(tree);
		
		prettyPrintTree(tree);
		
		tree.find(4);
		
		tree.delete(2);
		prettyPrintTree(tree);
		
		tree.delete(4);
		prettyPrintTree(tree);
		
		tree.delete(10);
		prettyPrintTree(tree);
		
		tree.delete(1);
		prettyPrintTree(tree);
		
		tree.insert(9);
		prettyPrintTree(tree);
		
		tree.insert(1);
		prettyPrintTree(tree);
		
		tree.find(100);
		prettyPrintTree(tree);
		
		tree.insert(100);
		prettyPrintTree(tree);
		
		tree.delete(15);
		prettyPrintTree(tree);
		
		tree.delete(16);
		prettyPrintTree(tree);
		
		tree.delete(9);
		prettyPrintTree(tree);
		
		tree.delete(8);
		prettyPrintTree(tree);
		
		tree.delete(3);
		prettyPrintTree(tree);
		
	}
	
	public static void prettyPrintTree(BSTree tree) {
//		tree.inOrder(tree.root);
//		System.out.println("");
		System.out.println("---- 트리 출력 ----");
		tree.printPreety();
		System.out.println("");
	}
	
	public static void makeBinarySearchTree(BSTree tree) {
		
		tree.insert(3);
		tree.insert(8);
		tree.insert(1);
		tree.insert(4);
		tree.insert(6);
		tree.insert(2);
		tree.insert(10);
		tree.insert(9);
		tree.insert(20);
		tree.insert(25);
		tree.insert(15);
		tree.insert(16);
		
	}
	

}

**** 결과 ****


노드 삽입 : 8
노드 삽입 : 1
노드 삽입 : 4
노드 삽입 : 6
노드 삽입 : 2
노드 삽입 : 10
노드 삽입 : 9
노드 삽입 : 20
노드 삽입 : 25
노드 삽입 : 15
노드 삽입 : 16
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                        2               4               10               
                                            6       9       20       
                                                          15   25   
                                                           16     

찾았습니다 : 4
노드 삭제 : 2
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                                        4               10               
                                            6       9       20       
                                                          15   25   
                                                           16     

노드 삭제 : 4
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                                        6               10               
                                                    9       20       
                                                          15   25   
                                                           16     

노드 삭제 : 10
---- 트리 출력 ----
                3                               
        1               8               
                    6       15       
                          9   20   
                             16 25 

노드 삭제 : 1
---- 트리 출력 ----
                3                               
                        8               
                    6       15       
                          9   20   
                             16 25 

이미 있는 데이터 입니다 : 9
---- 트리 출력 ----
                3                               
                        8               
                    6       15       
                          9   20   
                             16 25 

노드 삽입 : 1
---- 트리 출력 ----
                3                               
        1               8               
                    6       15       
                          9   20   
                             16 25 

찾는 데이터가 없습니다 : 100
---- 트리 출력 ----
                3                               
        1               8               
                    6       15       
                          9   20   
                             16 25 

노드 삽입 : 100
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                                        6               15               
                                                    9       20       
                                                          16   25   
                                                               100 

노드 삭제 : 15
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                                        6               16               
                                                    9       20       
                                                              25   
                                                               100 

노드 삭제 : 16
---- 트리 출력 ----
                3                               
        1               8               
                    6       20       
                          9   25   
                               100 

노드 삭제 : 9
---- 트리 출력 ----
                3                               
        1               8               
                    6       20       
                              25   
                               100 

노드 삭제 : 8
---- 트리 출력 ----
        3               
    1       20       
          6   25   
               100 

노드 삭제 : 3
---- 트리 출력 ----
        6               
    1       20       
              25   
               100 

* 이진 트리

알고리즘

package algo.binarytree;

import algo.queue.MyQueue;

public class MyBinaryTree {

	public enum DIR{
		LEFT, RIGHT
	}

	public class MyBTNode{
		
		public int info;
		public MyBTNode left;
		public MyBTNode parent;
		public MyBTNode right;
		
		public MyBTNode(int info) {
			this.info = info;
		}
		
	}
	
	private MyBTNode root;
	private MyQueue<MyBTNode> queue;
	
	public MyBinaryTree() {
		queue = new MyQueue<>();
	}
	
	public MyBTNode getRoot() {
		return root;
	}
	
	public MyBTNode addRoot(int info) {
		root = new MyBTNode(info);
		return root;
	}
	
	public MyBTNode addNode(MyBTNode parent, int info, DIR dir) {
		
		MyBTNode newNode = new MyBTNode(info);
		newNode.parent = parent;
		
		if(dir == DIR.LEFT)
			parent.left = newNode;
		else
			parent.right = newNode;
		
		return newNode;
		
	}
	
	public void print(MyBTNode node) {
		System.out.println("방문 : " + node.info);
	}
	
	public void inOrder(MyBTNode node) {
		
		// TL -> ROOT -> TR
		if(node == null)
			return;
		
		inOrder(node.left);
		print(node);
		inOrder(node.right);
		
	}
	
	public void preOrder(MyBTNode node) {
		
		// ROOT -> TL - > TR
		
		if(node == null)
			return;
		
		print(node);
		preOrder(node.left);
		preOrder(node.right);
		
	}
	
	public void postOrder(MyBTNode node) {
		
		// TL - > TR -> ROOT
		
		if(node == null)
			return;
		
		postOrder(node.left);
		postOrder(node.right);
		print(node);
		
	}
	
	public void levelOrder() {
		
		queue.enqueue(root);
		print(root);
		
		MyBTNode node = null;
		while(!queue.isEmpty()) {
			
			node = queue.dequeue();
			
			if(node.left != null) {
				print(node.left);
				queue.enqueue(node.left);
			}
			
			if(node.right != null) {
				print(node.right);
				queue.enqueue(node.right);
			}
			
		}
		
	}
	
}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.binarytree.MyBinaryTree;
import algo.binarytree.MyBinaryTree.DIR;
import algo.binarytree.MyBinaryTree.MyBTNode;
import algo.radix.MyRadixSort;

public class Main {

	public static void main(String[] args) {

		MyBinaryTree tree = new MyBinaryTree();
		makeBinaryTree(tree);
		printBinaryTree(tree);
		
	}
	
	public static void makeBinaryTree(MyBinaryTree tree) {
		MyBTNode root = tree.addRoot(1);
			MyBTNode node3 = tree.addNode(root, 3, DIR.LEFT);
				tree.addNode(node3, 2, DIR.LEFT);
				tree.addNode(node3, 5, DIR.RIGHT);
			MyBTNode node7 = tree.addNode(root, 7, DIR.RIGHT);
				tree.addNode(node7, 8, DIR.RIGHT);
	}
	
	public static void makeBinaryTreeForLevelOrder(MyBinaryTree tree) {
		
		MyBTNode root = tree.addRoot(3);
			MyBTNode node1 = tree.addNode(root, 1, DIR.LEFT);
				MyBTNode node0 = tree.addNode(node1, 0, DIR.LEFT);
				MyBTNode node2 = tree.addNode(node1, 2, DIR.RIGHT);
					MyBTNode node7 = tree.addNode(node2, 7, DIR.LEFT);
					MyBTNode node8 = tree.addNode(node2, 8, DIR.RIGHT);
			MyBTNode node5 = tree.addNode(root, 5, DIR.RIGHT);
				MyBTNode node4 = tree.addNode(node5, 4, DIR.LEFT);
				MyBTNode node6 = tree.addNode(node5, 6, DIR.RIGHT);
		
	}
	
	public static void printBinaryTree(MyBinaryTree tree) {
		
		System.out.println("* IN ORDER");
		tree.inOrder(tree.getRoot());

		System.out.println("* PRE ORDER");
		tree.preOrder(tree.getRoot());
		
		System.out.println("* POST ORDER");
		tree.postOrder(tree.getRoot());
		
		makeBinaryTreeForLevelOrder(tree);
		
		System.out.println("* LEVEL ORDER");
		tree.levelOrder();
		
	}

}

<결과>
* IN ORDER
방문 : 2
방문 : 3
방문 : 5
방문 : 1
방문 : 7
방문 : 8
* PRE ORDER
방문 : 1
방문 : 3
방문 : 2
방문 : 5
방문 : 7
방문 : 8
* POST ORDER
방문 : 2
방문 : 5
방문 : 3
방문 : 8
방문 : 7
방문 : 1
* LEVEL ORDER
방문 : 3
방문 : 1
방문 : 5
방문 : 0
방문 : 2
방문 : 4
방문 : 6
방문 : 7
방문 : 8

* Radix Sort

* Counting Sort를 활용

package algo.radix;

import java.util.Arrays;

public class MyRadixSort {

	private int[] itemArr;
	private Integer[] sortedItemArr;
	private int[] countingArr;
	
	public void sort(int[] arr) {
		
		this.itemArr = arr;
		this.sortedItemArr = new Integer[itemArr.length];
		this.countingArr = new int[10];
		
		int maxItem = getMax();
		
		for(int i = 1 ; maxItem / i > 0 ; i*=10) {
			countSort(i);
		}
	}
	
	private void countSort(int div) {
		
		Arrays.fill(sortedItemArr, 0);
		Arrays.fill(countingArr, 0);
		
		printArr(itemArr, "시작 배열           -> ");
		
		//자릴수에 따라 카운팅 및 정렬
		int item = 0;
		for(int i = 0 ; i < itemArr.length ; i++) {
			item = itemArr[i] / div % 10;
			countingArr[item] = countingArr[item] + 1;
		}
		
		printArr(countingArr, "카운팅 배열        -> ");
		
		int sum = 0;
		for(int i = 0 ; i < countingArr.length ; i++) {
			sum += countingArr[i];
			countingArr[i] = sum;
		}
		
		System.out.println("* 정렬 시작");
		
		int targetIdx = 0;
		for(int i = itemArr.length - 1 ; i >= 0 ; i--) {
			
			item = itemArr[i] / div % 10;
			targetIdx = countingArr[item];
			sortedItemArr[targetIdx-1] = itemArr[i];
			countingArr[item] = countingArr[item] - 1;
			
			printArr(countingArr, "\t카운팅 누적 배열 \t-> ");
			printIntegerArr(sortedItemArr, "\t정렬된 배열1\t-> ");
			
		}
		
		for(int i = 0 ; i < sortedItemArr.length ; i++) {
			itemArr[i] = sortedItemArr[i];
		}
		
		printArr(itemArr, "\t정렬된 배열2\t-> ");

	}
	
	private int getMax() {
		
		int max = itemArr[0];
		for (int i = 0; i < itemArr.length; i++) {

			if (itemArr[i] > max)
				max = itemArr[i];

		}
		
		return max;
	}
	
	private void printArr(int[] targetArr, String msg) {

		System.out.print(msg);
		for (int i = 0; i < targetArr.length ; i++)
			System.out.print(targetArr[i] + " ");
		System.out.println();

	}
	
	private void printIntegerArr(Object[] targetArr, String msg) {

		System.out.print(msg);
		for (int i = 0; i < targetArr.length ; i++)
			System.out.print(targetArr[i] + " ");
		System.out.println();

	}
	
}

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.countingsort.MyCountingSort;
import algo.radix.MyRadixSort;

public class Main {

	public static void main(String[] args) {

		MyRadixSort algo = new MyRadixSort();
		algo.sort(new int[] {170, 45, 75, 90, 802, 24, 2, 66});
		
	}

}

[결과]
시작 배열           -> 170 45 75 90 802 24 2 66 
카운팅 배열        -> 2 0 2 0 1 2 1 0 0 0 
* 정렬 시작
	카운팅 누적 배열 	-> 2 2 4 4 5 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 0 0 0 0 66 
	카운팅 누적 배열 	-> 2 2 3 4 5 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 2 0 0 0 66 
	카운팅 누적 배열 	-> 2 2 3 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 2 24 0 0 66 
	카운팅 누적 배열 	-> 2 2 2 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 0 802 2 24 0 0 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 0 0 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 6 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 0 75 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 5 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 45 75 66 
	카운팅 누적 배열 	-> 0 2 2 4 4 5 7 8 8 8 
	정렬된 배열1	-> 170 90 802 2 24 45 75 66 
	정렬된 배열2	-> 170 90 802 2 24 45 75 66 
시작 배열           -> 170 90 802 2 24 45 75 66 
카운팅 배열        -> 2 0 1 0 1 0 1 2 0 1 
* 정렬 시작
	카운팅 누적 배열 	-> 2 2 3 3 4 4 4 7 7 8 
	정렬된 배열1	-> 0 0 0 0 66 0 0 0 
	카운팅 누적 배열 	-> 2 2 3 3 4 4 4 6 7 8 
	정렬된 배열1	-> 0 0 0 0 66 0 75 0 
	카운팅 누적 배열 	-> 2 2 3 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 0 0 45 66 0 75 0 
	카운팅 누적 배열 	-> 2 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 0 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 1 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 2 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 802 2 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 6 7 7 
	정렬된 배열1	-> 802 2 24 45 66 0 75 90 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 5 7 7 
	정렬된 배열1	-> 802 2 24 45 66 170 75 90 
	정렬된 배열2	-> 802 2 24 45 66 170 75 90 
시작 배열           -> 802 2 24 45 66 170 75 90 
카운팅 배열        -> 6 1 0 0 0 0 0 0 1 0 
* 정렬 시작
	카운팅 누적 배열 	-> 5 7 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 0 90 0 0 
	카운팅 누적 배열 	-> 4 7 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 75 90 0 0 
	카운팅 누적 배열 	-> 4 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 75 90 170 0 
	카운팅 누적 배열 	-> 3 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 66 75 90 170 0 
	카운팅 누적 배열 	-> 2 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 1 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 24 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 0 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 2 24 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 0 6 7 7 7 7 7 7 7 8 
	정렬된 배열1	-> 2 24 45 66 75 90 170 802 
	정렬된 배열2	-> 2 24 45 66 75 90 170 802 

* 계수정렬

* Non-Comparable Sort

* Stable Sort

* Sorting in linear time

* O(N)

* 뭔가 신박한 정렬 알고리즘, 어떻게 누적 카운팅으로 정렬할생각을 했을까..? 

알고리즘

package algo.countingsort;

public class MyCountingSort {

	private int[] itemArr;
	private Integer[] sortedItemArr;
	private int[] countingArr;
	
	public void sort(int[] arr, int max) {
		
		this.itemArr = arr;
		this.sortedItemArr = new Integer[arr.length];
		this.countingArr = new int[max + 1];
		
		printArr(itemArr, "시작 배열           -> ");
		
		//각 요소 counting
		int item = 0;
		for(int i = 0 ; i < itemArr.length ; i++) {
			item = itemArr[i];
			countingArr[item] = countingArr[item] + 1;
		}

		printArr(countingArr, "카운팅 배열        -> ");
		
		//counting 배열을 누적 배열로
		int sum = 0;
		for(int i = 0 ; i < countingArr.length ; i++) {
			sum += countingArr[i];
			countingArr[i] = sum;
		}
		
		printArr(countingArr, "카운팅 누적 배열 -> ");
		
		
		System.out.println("* 정렬 시작");
		
		int targetIdx = 0;
		for(int i = itemArr.length - 1 ; i >= 0 ; i--) {
			
			item = itemArr[i];
			targetIdx = countingArr[item];
			sortedItemArr[targetIdx-1] = item;
			countingArr[item] = countingArr[item] - 1;
			
			printArr(countingArr, "카운팅 누적 배열 -> ");
			printIntegerArr(sortedItemArr, "정렬된 배열        -> ");
			
		}
		
		//마지막부터 정렬
		
	}
	
	private void printArr(int[] targetArr, String msg) {

		System.out.print(msg);
		for (int i = 0; i < targetArr.length ; i++)
			System.out.print(targetArr[i] + " ");
		System.out.println();

	}
	
	private void printIntegerArr(Object[] targetArr, String msg) {

		System.out.print(msg);
		for (int i = 0; i < targetArr.length ; i++)
			System.out.print(targetArr[i] + " ");
		System.out.println();

	}
	
	
}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.countingsort.MyCountingSort;

public class Main {

	public static void main(String[] args) {

		MyCountingSort algo = new MyCountingSort();
		algo.sort(new int[] {2,5,3,0,2,3,0,3}, 5);
		
	}
}


<결과>
시작 배열           -> 2 5 3 0 2 3 0 3 
카운팅 배열        -> 2 0 2 3 0 1 
카운팅 누적 배열 -> 2 2 4 7 7 8 
* 정렬 시작
카운팅 누적 배열 -> 2 2 4 6 7 8 
정렬된 배열        -> null null null null null null 3 null 
카운팅 누적 배열 -> 1 2 4 6 7 8 
정렬된 배열        -> null 0 null null null null 3 null 
카운팅 누적 배열 -> 1 2 4 5 7 8 
정렬된 배열        -> null 0 null null null 3 3 null 
카운팅 누적 배열 -> 1 2 3 5 7 8 
정렬된 배열        -> null 0 null 2 null 3 3 null 
카운팅 누적 배열 -> 0 2 3 5 7 8 
정렬된 배열        -> 0 0 null 2 null 3 3 null 
카운팅 누적 배열 -> 0 2 3 4 7 8 
정렬된 배열        -> 0 0 null 2 3 3 3 null 
카운팅 누적 배열 -> 0 2 3 4 7 7 
정렬된 배열        -> 0 0 null 2 3 3 3 5 
카운팅 누적 배열 -> 0 2 2 4 7 7 
정렬된 배열        -> 0 0 2 2 3 3 3 5 

* 우선 순위 큐

* Heap을 사용하는 알고리즘이다

* insert, delete시 heapify만 해주면 끝

알고리즘

package algo.priorityqueue;

public class MyPriorityQueue {

	private int top;
	private int initialCapacity;
	private int capacity;
	private Integer[] array;
	
	public MyPriorityQueue() {
		
		top = -1;
		initialCapacity = 1;
		capacity = initialCapacity;
		array = new Integer[initialCapacity];
		
	}

	public Integer offer(Integer item) {
		
		if(isFull())
			reAllocate();
		
		top++;
		array[top] = item;

		System.out.println("OFFER : " + item);
		
		buildHeap();
		
		return item;
	}
	
	public Integer poll() {
		
		if (isEmpty())
			return null;

		Integer item = array[0];
		System.out.println("POLL : " + item);
		
		swap(0, top);
		printArr(" Swap    -->  ");

		array[top] = null;
		top--;
		
		buildHeap();
		
		return item;
	}
	
	private void reAllocate() {
		
		Integer[] newArr = new Integer[capacity * 2];
		for (int i = 0; i < array.length; i++) {
			newArr[i] = array[i]; 
		}
		array = newArr;
		capacity = capacity * 2;
	}
	
	
	private boolean isFull() {
		return top == capacity - 1;
	}
	
	public boolean isEmpty() {
		return top == -1;
	}
	
	private void buildHeap() {
		
		int arrSize = top + 1;

		for (int i = arrSize / 2 - 1; i >= 0; i--)
			heapify(arrSize, i);
		
		printArr(" BUILDED HEAP -->  ");
		
	}
	
	/**
	 * arrSize를 받는 이유는
	 * extract 연산을 할때 swap후 마지막 요소는 이미 정렬된 상태라 없는 취급을 해야 하므로 
	 */
	private void heapify(int arrSize, int arrIdx) {

		int largest = arrIdx;
		int left = arrIdx * 2 + 1;
		int right = arrIdx * 2 + 2;

		// 왼쪽, 오른쪽 자식중 큰것을 선택
		if (left < arrSize && array[largest] < array[left])
			largest = left;

		if (right < arrSize && array[largest] < array[right])
			largest = right;

		// 자식들이 부모보다 크다면 swap
		// 그리고 다시 자식을 상대로 heapify
		if (largest != arrIdx) {
			swap(largest, arrIdx);
			
			printArr(" Heapify -->  ");
			
			heapify(arrSize, largest);
		}

	}

	private void swap(int i, int j) {

		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;

	}

	private void printArr(String msg) {

		System.out.print(msg);
		for (int i = 0; i < top + 1; i++)
			System.out.print(array[i] + " ");
		System.out.println();

	}

}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.heap.MyHeapSort;
import algo.merge.MyMergeSort;
import algo.priorityqueue.MyPriorityQueue;
import algo.quick.MyQuickSort;

public class Main {

	public static void main(String[] args) {

		MyPriorityQueue queue = new MyPriorityQueue();
		queue.offer(1);
		queue.offer(3);
		queue.offer(5);
		queue.offer(2);
		queue.offer(11);
		queue.offer(7);
		queue.offer(99);
		queue.offer(1);
		queue.offer(-1);
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();
		queue.poll();

	}
}

<결과>

OFFER : 1
 BUILDED HEAP -->  1 
OFFER : 3
 Heapify -->  3 1 
 BUILDED HEAP -->  3 1 
OFFER : 5
 Heapify -->  5 1 3 
 BUILDED HEAP -->  5 1 3 
OFFER : 2
 Heapify -->  5 2 3 1 
 BUILDED HEAP -->  5 2 3 1 
OFFER : 11
 Heapify -->  5 11 3 1 2 
 Heapify -->  11 5 3 1 2 
 BUILDED HEAP -->  11 5 3 1 2 
OFFER : 7
 Heapify -->  11 5 7 1 2 3 
 BUILDED HEAP -->  11 5 7 1 2 3 
OFFER : 99
 Heapify -->  11 5 99 1 2 3 7 
 Heapify -->  99 5 11 1 2 3 7 
 BUILDED HEAP -->  99 5 11 1 2 3 7 
OFFER : 1
 BUILDED HEAP -->  99 5 11 1 2 3 7 1 
OFFER : -1
 BUILDED HEAP -->  99 5 11 1 2 3 7 1 -1 
POLL : 99
 Swap    -->  -1 5 11 1 2 3 7 1 99 
 Heapify -->  11 5 -1 1 2 3 7 1 
 Heapify -->  11 5 7 1 2 3 -1 1 
 BUILDED HEAP -->  11 5 7 1 2 3 -1 1 
POLL : 11
 Swap    -->  1 5 7 1 2 3 -1 11 
 Heapify -->  7 5 1 1 2 3 -1 
 Heapify -->  7 5 3 1 2 1 -1 
 BUILDED HEAP -->  7 5 3 1 2 1 -1 
POLL : 7
 Swap    -->  -1 5 3 1 2 1 7 
 Heapify -->  5 -1 3 1 2 1 
 Heapify -->  5 2 3 1 -1 1 
 BUILDED HEAP -->  5 2 3 1 -1 1 
POLL : 5
 Swap    -->  1 2 3 1 -1 5 
 Heapify -->  3 2 1 1 -1 
 BUILDED HEAP -->  3 2 1 1 -1 
POLL : 3
 Swap    -->  -1 2 1 1 3 
 Heapify -->  2 -1 1 1 
 Heapify -->  2 1 1 -1 
 BUILDED HEAP -->  2 1 1 -1 
POLL : 2
 Swap    -->  -1 1 1 2 
 Heapify -->  1 -1 1 
 BUILDED HEAP -->  1 -1 1 
POLL : 1
 Swap    -->  1 -1 1 
 BUILDED HEAP -->  1 -1 
POLL : 1
 Swap    -->  -1 1 
 BUILDED HEAP -->  -1 
POLL : -1
 Swap    -->  -1 
 BUILDED HEAP -->  

* 힙 소트

* O(NlogN)

* 힙에 대한 이해만 잘 하면 알고리즘은 쉬운 편이다

알고리즘

package algo.heap;

public class MyHeapSort {

	private Integer[] array;

	public void sort(Integer[] array) {

		this.array = array;

		printArr("\n연산 시작 --> ");

		heapSort();

		printArr("연산 끝 -->  ");

	}

	private void heapSort() {

		int arrSize = array.length;

		// Build Max Heap
		for (int i = array.length / 2 - 1; i >= 0; i--)
			heapify(arrSize, i);

		printArr("MAX HEAP -->  ");

		// extract연산 (정렬)
		for (int i = array.length - 1; i > 0; i--) {
			swap(0, i);
			
			printArr("Swap     -->  ");
			
			arrSize--;
			heapify(arrSize, 0);
		}

	}

	/**
	 * arrSize를 받는 이유는
	 * extract 연산을 할때 swap후 마지막 요소는 이미 정렬된 상태라 없는 취급을 해야 하므로 
	 */
	private void heapify(int arrSize, int arrIdx) {

		int largest = arrIdx;
		int left = arrIdx * 2 + 1;
		int right = arrIdx * 2 + 2;

		// 왼쪽, 오른쪽 자식중 큰것을 선택
		if (left < arrSize && array[largest] < array[left])
			largest = left;

		if (right < arrSize && array[largest] < array[right])
			largest = right;

		// 자식들이 부모보다 크다면 swap
		// 그리고 다시 자식을 상대로 heapify
		if (largest != arrIdx) {
			swap(largest, arrIdx);
			
			printArr(" Heapify -->  ");
			
			heapify(arrSize, largest);
		}

	}

	private void swap(int i, int j) {

		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;

	}

	private void printArr(String msg) {

		System.out.print(msg);
		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + " ");
		System.out.println();

	}

}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.heap.MyHeapSort;
import algo.merge.MyMergeSort;
import algo.quick.MyQuickSort;

public class Main {

	public static void main(String[] args) {

		MyHeapSort sort = new MyHeapSort();
		for(int i = 0 ; i < 1 ; i ++)
			sort.sort(getRandArr());

	}

	public static Integer[] getRandArr() {

		List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
		Collections.shuffle(arr);
		Collections.shuffle(arr);
		return (Integer[])arr.toArray();
		
	}

}

<결과>

연산 시작 --> 4 1 2 3 7 5 6 8 9 10 
 Heapify -->  4 1 2 3 10 5 6 8 9 7 
 Heapify -->  4 1 2 9 10 5 6 8 3 7 
 Heapify -->  4 1 6 9 10 5 2 8 3 7 
 Heapify -->  4 10 6 9 1 5 2 8 3 7 
 Heapify -->  4 10 6 9 7 5 2 8 3 1 
 Heapify -->  10 4 6 9 7 5 2 8 3 1 
 Heapify -->  10 9 6 4 7 5 2 8 3 1 
 Heapify -->  10 9 6 8 7 5 2 4 3 1 
MAX HEAP -->  10 9 6 8 7 5 2 4 3 1 
Swap     -->  1 9 6 8 7 5 2 4 3 10 
 Heapify -->  9 1 6 8 7 5 2 4 3 10 
 Heapify -->  9 8 6 1 7 5 2 4 3 10 
 Heapify -->  9 8 6 4 7 5 2 1 3 10 
Swap     -->  3 8 6 4 7 5 2 1 9 10 
 Heapify -->  8 3 6 4 7 5 2 1 9 10 
 Heapify -->  8 7 6 4 3 5 2 1 9 10 
Swap     -->  1 7 6 4 3 5 2 8 9 10 
 Heapify -->  7 1 6 4 3 5 2 8 9 10 
 Heapify -->  7 4 6 1 3 5 2 8 9 10 
Swap     -->  2 4 6 1 3 5 7 8 9 10 
 Heapify -->  6 4 2 1 3 5 7 8 9 10 
 Heapify -->  6 4 5 1 3 2 7 8 9 10 
Swap     -->  2 4 5 1 3 6 7 8 9 10 
 Heapify -->  5 4 2 1 3 6 7 8 9 10 
Swap     -->  3 4 2 1 5 6 7 8 9 10 
 Heapify -->  4 3 2 1 5 6 7 8 9 10 
Swap     -->  1 3 2 4 5 6 7 8 9 10 
 Heapify -->  3 1 2 4 5 6 7 8 9 10 
Swap     -->  2 1 3 4 5 6 7 8 9 10 
Swap     -->  1 2 3 4 5 6 7 8 9 10 
연산 끝 -->  1 2 3 4 5 6 7 8 9 10 

* 퀵 소트

* 최대한 Worst case를 줄이기 위해서 피봇을 랜덤으로 선택하는 부분이 포함되어있음

* 최악 O(N^2), 평균 O(NlogN)

알고리즘

package algo.quick;

import java.util.Random;

public class MyQuickSort {
	
	private Integer[] array;
	
	public void sort(Integer[] array) {
		
		this.array = array;
		
		printBeforeAfter("\n연산 시작 --> ");

		quickSort(0, array.length - 1);
		
		printBeforeAfter("연산 끝 -->  ");
		
	}
	
	private void quickSort(int start, int end) {
		
		if(start < end) {
			
			System.out.println("Quick Sort : " + "start = " + start + ", end = " + end);
			
			//피봇은 이미 정렬된것이므로, 밑에 quick sort는 피봇을 제외한채 진행되어야 한다.
			int pivot = partitioning(start, end);
			quickSort(start, pivot - 1);
			quickSort(pivot + 1, end);
			
		}
		
	}
	
	private void swap(int i, int j) {
		
		int temp = array[i];
		array[i] = array[j]; 
		array[j] = temp;
		
	}
	
	private int partitioning(int start, int end) {
		
		System.out.println("\tPartioning : " + "start = " + start + ", end = " + end);
		System.out.print("\t[부분 배열           ] ");
		
		printPartioning(start, end);
		
		int randPivotIdx = new Random().nextInt((end - start) + 1) + start;
		
		System.out.print("\t랜덤 피봇   = " + array[randPivotIdx]);
		System.out.println("\t랜덤 피봇과 끝부분(피봇) 교환");
		System.out.print("\t[교환 후 부분 배열] ");
		
		//랜덤으로 선택된 pivot을 마지막과 바꾼다.
		swap(randPivotIdx, end);
		
		printPartioning(start, end);
		
		int newPivot = start;
		
		//이제 마지막이 피봇이 되었다
		for(int i = start ; i < end ; i++) {
			
			if(array[i] < array[end]) {

				if(newPivot != i) {
					System.out.print("\t" + array[newPivot] + " <-- 교환  --> " + array[i]);
					swap(newPivot, i);	
					System.out.print("\t ==> ");
					printPartioning(start, end);
				}
				newPivot++;
			}
		}
		
		System.out.print("\t[정렬 후 부분 배열      ] ");
		printPartioning(start, end);
		
		swap(newPivot, end);

		System.out.println("\t파티션 기준 인덱스 = " + newPivot + ", 값 = " + array[newPivot]);
		System.out.print("\t[파티셔닝 후 부분 배열] ");
		printPartioning(start, end);
		
		return newPivot;
	}
	
	private void printPartioning(int start, int end) {

		for (int i = start; i <= end; i++)
			System.out.print(array[i] + " ");
		System.out.println();
		
	}

	private void printBeforeAfter(String msg) {
		
		System.out.println(msg);
		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + " ");
		System.out.println();
		
	}
	

}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.merge.MyMergeSort;
import algo.quick.MyQuickSort;

public class Main {

	public static void main(String[] args) {

		MyQuickSort sort = new MyQuickSort();
		for(int i = 0 ; i < 1 ; i ++)
			sort.sort(getRandArr());

	}

	public static Integer[] getRandArr() {

		List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
		Collections.shuffle(arr);
		Collections.shuffle(arr);
		return (Integer[])arr.toArray();
		
	}

}

<결과 추적>

연산 시작 --> 
9 5 8 4 10 7 2 1 3 6 
Quick Sort : start = 0, end = 9
	Partioning : start = 0, end = 9
	[부분 배열           ] 9 5 8 4 10 7 2 1 3 6 
	랜덤 피봇   = 4	랜덤 피봇과 끝부분(피봇) 교환
	[교환 후 부분 배열] 9 5 8 6 10 7 2 1 3 4 
	9 <-- 교환  --> 2	 ==> 2 5 8 6 10 7 9 1 3 4 
	5 <-- 교환  --> 1	 ==> 2 1 8 6 10 7 9 5 3 4 
	8 <-- 교환  --> 3	 ==> 2 1 3 6 10 7 9 5 8 4 
	[정렬 후 부분 배열      ] 2 1 3 6 10 7 9 5 8 4 
	파티션 기준 인덱스 = 3, 값 = 4
	[파티셔닝 후 부분 배열] 2 1 3 4 10 7 9 5 8 6 
Quick Sort : start = 0, end = 2
	Partioning : start = 0, end = 2
	[부분 배열           ] 2 1 3 
	랜덤 피봇   = 3	랜덤 피봇과 끝부분(피봇) 교환
	[교환 후 부분 배열] 2 1 3 
	[정렬 후 부분 배열      ] 2 1 3 
	파티션 기준 인덱스 = 2, 값 = 3
	[파티셔닝 후 부분 배열] 2 1 3 
Quick Sort : start = 0, end = 1
	Partioning : start = 0, end = 1
	[부분 배열           ] 2 1 
	랜덤 피봇   = 1	랜덤 피봇과 끝부분(피봇) 교환
	[교환 후 부분 배열] 2 1 
	[정렬 후 부분 배열      ] 2 1 
	파티션 기준 인덱스 = 0, 값 = 1
	[파티셔닝 후 부분 배열] 1 2 
Quick Sort : start = 4, end = 9
	Partioning : start = 4, end = 9
	[부분 배열           ] 10 7 9 5 8 6 
	랜덤 피봇   = 10	랜덤 피봇과 끝부분(피봇) 교환
	[교환 후 부분 배열] 6 7 9 5 8 10 
	[정렬 후 부분 배열      ] 6 7 9 5 8 10 
	파티션 기준 인덱스 = 9, 값 = 10
	[파티셔닝 후 부분 배열] 6 7 9 5 8 10 
Quick Sort : start = 4, end = 8
	Partioning : start = 4, end = 8
	[부분 배열           ] 6 7 9 5 8 
	랜덤 피봇   = 7	랜덤 피봇과 끝부분(피봇) 교환
	[교환 후 부분 배열] 6 8 9 5 7 
	8 <-- 교환  --> 5	 ==> 6 5 9 8 7 
	[정렬 후 부분 배열      ] 6 5 9 8 7 
	파티션 기준 인덱스 = 6, 값 = 7
	[파티셔닝 후 부분 배열] 6 5 7 8 9 
Quick Sort : start = 4, end = 5
	Partioning : start = 4, end = 5
	[부분 배열           ] 6 5 
	랜덤 피봇   = 5	랜덤 피봇과 끝부분(피봇) 교환
	[교환 후 부분 배열] 6 5 
	[정렬 후 부분 배열      ] 6 5 
	파티션 기준 인덱스 = 4, 값 = 5
	[파티셔닝 후 부분 배열] 5 6 
Quick Sort : start = 7, end = 8
	Partioning : start = 7, end = 8
	[부분 배열           ] 8 9 
	랜덤 피봇   = 9	랜덤 피봇과 끝부분(피봇) 교환
	[교환 후 부분 배열] 8 9 
	[정렬 후 부분 배열      ] 8 9 
	파티션 기준 인덱스 = 8, 값 = 9
	[파티셔닝 후 부분 배열] 8 9 
연산 끝 -->  
1 2 3 4 5 6 7 8 9 10 

* 합병 정렬

* O(NlogN)

* 테스트부분을 알겠지만, 나누어서 정복한다 (Divide and conquer)의 전형적인 예라고 할 수 있겠다.

* 이 알고리즘이 잘 이해가 가지 않는 사람이라면, 테스트 부분의 결과부분을 유심히 살펴보세요, 각 단계별로 모든 상태를 프린트 해놨습니다.

package algo.merge;

public class MyMergeSort {
	
	private Integer[] array;
	
	public void sort(Integer[] array) {
		
		this.array = array;
		
		printBeforeAfter("\n연산 시작 --> ");

		mergeSort(0, array.length - 1);
		
		printBeforeAfter("연산 끝 -->  ");
		
	}
	
	private void mergeSort(int start, int end) {
		
		//중간 인덱스 계산
		int mid = (start + end) / 2;
		
		if(start < end) {
			
			System.out.println("MERGE SORT : " + "START = " + start + ", MID = " + mid + ", END = " + end);
			
			mergeSort(start, mid);
			mergeSort(mid + 1,  end);
			merge(start, mid, end);
			
		}
		
	}
	
	private void merge(int start, int mid, int end) {

		printMergeInfoPrint(start, mid, end);
		
		int s = start;
		int m = mid + 1;
		
		//필요한 만큼만 새로운 배열 할당
		Integer[] temp = new Integer[end - start + 1];
		int t = 0;
		
		//한개의 부분 배열이 끝날때까지 루프
		while(s <= mid && m <= end) {
			
			if(array[s] < array[m])
				temp[t++] = array[s++];
			else
				temp[t++] = array[m++];
			
		}
		
		//둘중에 아직 안끝난 루프를 실행해준다
		//아직 안끝난 부분은 당연히 앞부분보다 클것이므로 그냥 루프로 돌려주면 끝
		while(s <= mid) temp[t++] = array[s++];
		while(m <= end) temp[t++] = array[m++];
		
		for(int i = 0 ; i < temp.length ; i++)
			array[i + start] = temp[i];
		
		printMergeAfterPrint(temp);
		
	}
	
	private void printMergeInfoPrint(int start, int mid, int end) {
		
		System.out.println("MERGE : " + "START = " + start + ", MID = " + mid + ", END = " + end);
		
		System.out.print("[MERGE 부분 배열  1] ");
		for (int i = start; i <= mid; i++)
			System.out.print(array[i] + " ");
		
		System.out.println();
		
		System.out.print("[MERGE 부분 배열  2] ");
		for (int i = mid + 1; i <= end; i++)
			System.out.print(array[i] + " ");
		
		System.out.println();
		
	}
	
	private void printMergeAfterPrint(Integer[] temp) {
		
		System.out.print("[MERGE 결과] ");
		for(int i = 0 ; i < temp.length ; i++)
			System.out.print(temp[i] + " ");
		System.out.println();
		
	}
	
	private void printBeforeAfter(String msg) {
		
		System.out.println(msg);
		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + " ");
		System.out.println();
		
	}
}

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.merge.MyMergeSort;

public class Main {

	public static void main(String[] args) {

		MyMergeSort sort = new MyMergeSort();
		for(int i = 0 ; i < 1 ; i ++)
			sort.sort(getRandArr());

	}

	public static Integer[] getRandArr() {

		List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
		Collections.shuffle(arr);
		Collections.shuffle(arr);
		return (Integer[])arr.toArray();
		
	}

}

<결과>


연산 시작 --> 
3 5 7 8 10 9 6 2 4 1 
MERGE SORT : START = 0, MID = 4, END = 9
MERGE SORT : START = 0, MID = 2, END = 4
MERGE SORT : START = 0, MID = 1, END = 2
MERGE SORT : START = 0, MID = 0, END = 1
MERGE : START = 0, MID = 0, END = 1
[MERGE 부분 배열  1] 3 
[MERGE 부분 배열  2] 5 
[MERGE 결과] 3 5 
MERGE : START = 0, MID = 1, END = 2
[MERGE 부분 배열  1] 3 5 
[MERGE 부분 배열  2] 7 
[MERGE 결과] 3 5 7 
MERGE SORT : START = 3, MID = 3, END = 4
MERGE : START = 3, MID = 3, END = 4
[MERGE 부분 배열  1] 8 
[MERGE 부분 배열  2] 10 
[MERGE 결과] 8 10 
MERGE : START = 0, MID = 2, END = 4
[MERGE 부분 배열  1] 3 5 7 
[MERGE 부분 배열  2] 8 10 
[MERGE 결과] 3 5 7 8 10 
MERGE SORT : START = 5, MID = 7, END = 9
MERGE SORT : START = 5, MID = 6, END = 7
MERGE SORT : START = 5, MID = 5, END = 6
MERGE : START = 5, MID = 5, END = 6
[MERGE 부분 배열  1] 9 
[MERGE 부분 배열  2] 6 
[MERGE 결과] 6 9 
MERGE : START = 5, MID = 6, END = 7
[MERGE 부분 배열  1] 6 9 
[MERGE 부분 배열  2] 2 
[MERGE 결과] 2 6 9 
MERGE SORT : START = 8, MID = 8, END = 9
MERGE : START = 8, MID = 8, END = 9
[MERGE 부분 배열  1] 4 
[MERGE 부분 배열  2] 1 
[MERGE 결과] 1 4 
MERGE : START = 5, MID = 7, END = 9
[MERGE 부분 배열  1] 2 6 9 
[MERGE 부분 배열  2] 1 4 
[MERGE 결과] 1 2 4 6 9 
MERGE : START = 0, MID = 4, END = 9
[MERGE 부분 배열  1] 3 5 7 8 10 
[MERGE 부분 배열  2] 1 2 4 6 9 
[MERGE 결과] 1 2 3 4 5 6 7 8 9 10 
연산 끝 -->  
1 2 3 4 5 6 7 8 9 10 

* 삽입 정렬

* O(N^2)

* 특정상황, 즉 거의 정렬된 상태에서의 효율성은 다른 알고리즘보다 괜찮다.

알고리즘

package algo.insertion;

public class MyInsertionSort {

	public void sort(Integer[] array) {

		System.out.print("\n연산 시작 --> ");
		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + " ");
		System.out.println();

		int temp = 0;
		int j = 0;
		
		for (int i = 0; i < array.length - 1; i++) {

			System.out.println(" * "+ (i + 1) + "회전 시작");
			
			j = i;
			while (j >= 0 && array[j] > array[j + 1]) {

				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
				j--;
				
				for (int k = 0; k < array.length; k++)
					System.out.print(array[k] + " ");
				System.out.println(" J = " + j);

			}
			
			System.out.println(" * " + (i + 1) + "회전 끝");

		}
		
		System.out.print("연산 끝 -->  ");

		for (int i = 0; i < array.length; i++)
			System.out.print(array[i] + " ");
		System.out.println();

	}

}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.insertion.MyInsertionSort;

public class Main {

	public static void main(String[] args) {

		MyInsertionSort sort = new MyInsertionSort();
		for(int i = 0 ; i < 1 ; i ++)
			sort.sort(getRandArr());

	}

	public static Integer[] getRandArr() {

		List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
		Collections.shuffle(arr);
		Collections.shuffle(arr);
		return (Integer[])arr.toArray();
		
	}

}
<정렬>

연산 시작 --> 5 3 7 1 2 8 9 10 6 4 
 * 1회전 시작
3 5 7 1 2 8 9 10 6 4  J = -1
 * 1회전 끝
 * 2회전 시작
 * 2회전 끝
 * 3회전 시작
3 5 1 7 2 8 9 10 6 4  J = 1
3 1 5 7 2 8 9 10 6 4  J = 0
1 3 5 7 2 8 9 10 6 4  J = -1
 * 3회전 끝
 * 4회전 시작
1 3 5 2 7 8 9 10 6 4  J = 2
1 3 2 5 7 8 9 10 6 4  J = 1
1 2 3 5 7 8 9 10 6 4  J = 0
 * 4회전 끝
 * 5회전 시작
 * 5회전 끝
 * 6회전 시작
 * 6회전 끝
 * 7회전 시작
 * 7회전 끝
 * 8회전 시작
1 2 3 5 7 8 9 6 10 4  J = 6
1 2 3 5 7 8 6 9 10 4  J = 5
1 2 3 5 7 6 8 9 10 4  J = 4
1 2 3 5 6 7 8 9 10 4  J = 3
 * 8회전 끝
 * 9회전 시작
1 2 3 5 6 7 8 9 4 10  J = 7
1 2 3 5 6 7 8 4 9 10  J = 6
1 2 3 5 6 7 4 8 9 10  J = 5
1 2 3 5 6 4 7 8 9 10  J = 4
1 2 3 5 4 6 7 8 9 10  J = 3
1 2 3 4 5 6 7 8 9 10  J = 2
 * 9회전 끝
연산 끝 -->  1 2 3 4 5 6 7 8 9 10 

* 버블 소트

* O(N^2)

package algo.bubble;

public class MyBubbleSort {

	public void sort(Integer[] array) {

		for(int i = 0 ; i < array.length ; i++)
			System.out.print(array[i] + " ");
		System.out.print(" -->  ");
		

		int temp = 0;
		
		for (int i = 0 ; i < array.length - 1 ; i++) {

			for (int j = 0 ; j < array.length - 1 - i; j++) {

				if(array[j] > array[j + 1]) {
				
					temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
					
				}
				
			}

		}

		for(int i = 0 ; i < array.length ; i++)
			System.out.print(array[i] + " ");
		System.out.println();

	}

}

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.bubble.MyBubbleSort;

public class Main {

	public static void main(String[] args) {

		MyBubbleSort sort = new MyBubbleSort();
		for(int i = 0 ; i < 10 ; i ++)
			sort.sort(getRandArr());

	}

	public static Integer[] getRandArr() {

		List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
		Collections.shuffle(arr);
		Collections.shuffle(arr);
		return (Integer[])arr.toArray();
		
	}

}

<결과>
1 10 3 5 8 4 2 7 9 6  -->  1 2 3 4 5 6 7 8 9 10 
2 8 1 10 9 7 4 6 3 5  -->  1 2 3 4 5 6 7 8 9 10 
7 2 5 1 3 4 6 8 9 10  -->  1 2 3 4 5 6 7 8 9 10 
7 8 10 3 2 9 4 1 5 6  -->  1 2 3 4 5 6 7 8 9 10 
7 8 1 4 10 5 3 6 9 2  -->  1 2 3 4 5 6 7 8 9 10 
2 8 5 9 10 6 7 3 4 1  -->  1 2 3 4 5 6 7 8 9 10 
3 9 8 7 10 1 5 6 4 2  -->  1 2 3 4 5 6 7 8 9 10 
10 6 4 2 9 7 1 8 3 5  -->  1 2 3 4 5 6 7 8 9 10 
5 7 9 10 1 6 2 8 4 3  -->  1 2 3 4 5 6 7 8 9 10 
10 8 1 9 6 5 3 7 4 2  -->  1 2 3 4 5 6 7 8 9 10