'Algorithm&DataStructures'에 해당되는 글 38건

선택 정렬(Selection sorting) - Selection sorting

- 검색(searching) + 정렬(sorting) 이 함께 있는 구조이다

1. SelectionSorting.class

1) selection(int[] arry)

public static void selection(int[]arry){ //배열 크기만큼 회전 for(int i = 0;i<arry.length; i++){ int index = i; //첫 번째 다음 요소 부터 검색을 시작한다 for(int k = i+1; k<arry.length; k++){ //검색을 해서 가장작은 값을 찾으면 인덱스를 저장 if(arry[index] > arry[k]){ index = k; } } //가장 작은 값과 맨 앞의 값을 교환 swap(i,index,arry); print(arry); } }

- 정렬을 시작한다

- 버블 정렬과는 다르게 마지막 for을 다 마친 후에 저장된 인덱스 번호로 swap을 한다

2) swap(int i, int k, int[]arry), print(int[] arry)

public static void swap(int i, int k, int[]arry){ int temp; temp = arry[k]; arry[k] = arry[i]; arry[i] = temp; } public static void print(int[]arry){ for(int i = 0; i<arry.length; i++){ System.out.print(arry[i]+","); } System.out.println(); }  

3) main()

public static void main(String[]args){ int[] input = {2,3,10,1,-5}; selection(input); }  

버블정렬 - bubble sorting

- 회전을 하면서 앞뒤의 요소들을 비교한다

- 앞의 요소가 크다면 바로 뒤의 요소와 위치를 변경한다

1. BubbleSorting.class

1) bubble_sort()

public static void bubble_sort(int arry[]){ int n = arry.length; int k; //배열 크기만큼 회전을 한다 for(int i = 0; i<n; i++){ //배열보다 하나 작은 크기로 버블 정렬이 시작된다 for(int l = 0; l< n-1; l++){ k = l + 1; //앞뒤 요소를 비교, 앞이 크면 위치를 변경한다 if(arry[l] > arry[k]){ swap(l,k,arry); } } print(arry); } }

- 정렬하는 함수

2) swap()

public static void swap(int i, int k, int[]arry){ int temp; temp = arry[i]; arry[i] = arry[k]; arry[k] = temp; }  

- 앞의 요소가 더 크다면 위치를 뒤에 요소와 변경한다

3) print()

public static void print(int[]arry){ for(int i = 0; i<arry.length; i++){ System.out.print(arry[i]+","); } System.out.println(); }  

- 정렬 상태를 반영한다

4) main()

public static void main(String[]args){ int[] input = {4,5,1,2,7}; bubble_sort(input); }  

큐(queue) - 우선순위 큐(Priority queue)

- 큐에 들어있는 값 중 큰 순서대로 밖으로 나온다

1. PriorityQueue.class

1) 초기화

@SuppressWarnings("rawtypes") private Comparable[] pQueue; private int index = 0; public PriorityQueue(int size){ pQueue = new Comparable[size]; }

- SuppressWarning 이란 이클립스에게 해당 경고는 무시하라는 표시를 한다

- Comparable 인터페이스형 배열을 만든다

2) insertQueue(Comparable element)

public void insertQueue(Comparable element){ if(index == pQueue.length){ System.out.println("Queue is full"); return; } pQueue[index] = element; index++; }  

3) Comparable remove()

public Comparable remove(){ if(index == 0){ System.out.println("Queue is empty"); return null; } int maxIndex = 0; for(int i = 1; i<index; i++){ if(pQueue[i].compareTo(pQueue[maxIndex]) > 0){ maxIndex = i; } } Comparable result = pQueue[maxIndex]; System.out.println("removing:"+result); index--; pQueue[maxIndex] = pQueue[index]; pQueue[index] = null; return result; }  

- for문을 이용하여 각각의 요소들을 비교한다

- 가장큰 요소의 인덱스 번호를 max에 저장한 후 그 값을 리턴한다

4) toString(), main()

public String toString(){ String str = "["; for(int i=0; i < pQueue.length-1; i++){ str += pQueue[i]+","; } str += pQueue[pQueue.length-1] +"]"; return str; } public static void main(String[]args){ PriorityQueue pQueue = new PriorityQueue(5); pQueue.insertQueue(30); pQueue.insertQueue(5); pQueue.insertQueue(10); pQueue.insertQueue(1); pQueue.insertQueue(2); System.out.println(pQueue); pQueue.remove(); pQueue.remove(); pQueue.remove(); System.out.println(pQueue); }  

더블링크드리스트 데큐 - Deque using doubly linked list

- 데큐(deque)를 링크드 리스트로 구현한다

1. Node<T>.class

class Node<T>{ private T data; private Node<T> next; private Node<T> pre; public T getData() { return data; } public void setData(T data) { this.data = data; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } public Node<T> getPre() { return pre; } public void setPre(Node<T> pre) { this.pre = pre; } }

- doubly linked list 이기 때문에 pre, next 가 선언 되었다

2. DoubleLinkedListDeque<T>.class

1) 초기화

Node<T> front; Node<T> rear; int size = 0;  

- 링크드 리스트로 구현하기 때문에 삽입과 삭제되는 부분을 컨트롤할 front, rear가 필요하다

- size를 지정함으로 유연하게 deque를 컨트롤 한다

2) addFirst(E element), addLast(E element)

 public void addFront(T element){ Node<T> newNode = new Node<>(); newNode.setData(element); newNode.setNext(front); if(front != null){ front.setPre(newNode); } if(front == null){ rear = newNode; } front = newNode; size++; } public void addLast(T element){ Node<T> newNode = new Node<>(); newNode.setPre(rear); newNode.setData(element); if(rear != null){ rear.setNext(newNode); } if(rear == null){ front = newNode; } rear = newNode; size++; }  

- deque 이기 때문에 삽입이 자유롭다

3) removeFront(), removeLast()

 public void removeLast()throws Exception{ if(isNullCheck()){ throw new Exception("List is null"); }else{ Node<T> temp = rear.getPre(); if(temp != null){ temp.setNext(null); } if(temp == null){ front = null; } rear = temp; temp = null; size--; } } public void removeFront()throws Exception{ if(isNullCheck()){ throw new Exception("List is null"); }{ Node<T> temp = front.getNext(); if(temp != null){ temp.setPre(null); } if(temp == null){ rear = null; } front = temp; temp = null; size--; } }  

4) isNullCheck(), toString()

 public boolean isNullCheck(){ return(size == 0); } public String toString(){ Node<T> temp = front; String str = "{"; if(temp != null){ for(int i = 0; i<size-1; i++){ str += temp.getData()+","; temp = temp.getNext(); } str += temp.getData(); } str += "}"; return str; }  

- 큐가 비었는지 체크와 현재 상태를 출력하는 함수 이다

5) main()

 public static void main(String[]args){ DoubleLinkedListDeque<Integer> list = new DoubleLinkedListDeque<>(); try{ list.addFront(1); list.addFront(2); list.addFront(3); list.addLast(4); list.addLast(5); list.removeFront(); list.removeLast(); list.removeLast(); list.removeLast(); list.removeLast(); System.out.println(list); }catch(Exception e){ System.out.println(e.getMessage()); } }