Part2. 8-3 정렬 알고리즘 문제

평균 수행 시간이 O(n^2)인 알고리즘

• 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort)
• 각 요소가 다른 요소와 평균 한번 이상씩 비교를 하여 정렬 됨

 

삽입정렬

import java.util.Iterator;
import java.util.Scanner;
import java.io.*;
import OOP.Order;

public class Main {
    public static void main(String[] args) {

        int[] arr = {80, 50, 70, 10, 60, 20, 40, 30 };

        for (int i=1; i<arr.length; i++){   // 실수 : 인덱스이니까 i < arr.length 이다. i <= arr.length 아니다.
            int save = arr[i];
            int j = i;
            while((j > 0) && arr[j-1] > save){   // 실수 : arr[j-1] > save 조건을 안 썼다. 이 조건은 현재 시점에서 체크할 조건 , j>0 은 미래 시점에서 체크할 조건이다.
                arr[j] = arr[j-1];
                j -= 1;
            }
            arr[j] = save;
        }
    }
}

 

---

평균 수행 시간이 O(logN)인 알고리즘

• 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort)
• 한번 수행될 때마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우
• 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요함

 

힙정렬

힙의 실제 구현은 배열로 많이 한다

어떤 노드 : i , 부모 노드 : i / 2 , 왼쪽 자식 노드 : i * 2 , 오른쪽 자식 노드 : i * 2 + 1

힙에서의 삽입은 새로운 노드를 맨 마지막 인덱스에 추가하고 upHeap 을 한다.

힙에서의 삭제는 루트를 삭제하고 맨 마지막 노드를 루트 자리에 넣은 후 downHeap을 한다.

 

우선순위 큐를 구현할 때 힙을 사용한다.

 

 

밑에 코드에서 하는 힙 삭제에서는 

맨 마지막 노드를 tmp 에 저장해 두었다가  반복문 다 끝나고 맨 뒤에 넣는다

(루트를 삭제하고 맨 마지막 노드를 루트 자리에 넣은 후 downHeap 하는 방식과는 다르다.)

public class HeapSort {

	private int SIZE;
	private int heapArr[];
	
	public HeapSort()
	{
		SIZE = 0;
		heapArr = new int [50];
	}
	
    
	public void insertHeap(int input)          // input 변수를 매개변수로 입력 받고
	{
		int i = ++SIZE;
        
		//while(( i != 1) && ( input > heapArr[i/2])){   //max heap
        
		while(( i != 1) && ( input < heapArr[i/2])){     //min heap
			heapArr[i] = heapArr[i/2];
			i = i/2;
		}
		heapArr[i] = input;                    // 삽입정렬과 비슷한 수행을 한다.
	}
	
    
	public int getHeapSize()
	{
		return SIZE;
	}
	
    
	public int deleteHeap()                 // 매개변수 없이
	{
		int parent, child;
		int data, temp;
		data = heapArr[1]; 
		
		temp = heapArr[SIZE];               // SIZE 는 전역변수, 맨 마지막 노드를 save 한다.
		SIZE -= 1; 
		parent =1; child = 2;               // parent와 child는 index를 의미
		
		while(child <= SIZE){
			//if((child < HEAP_SIZE) && (heapArr[child] < heapArr[child+1])){ //max heap
            
			if((child < SIZE) && (heapArr[child] > heapArr[child+1])){ //min heap
				child++;                         // 오른쪽 자식의 값이 왼쪽 자식보다 더 작은 경우
			}
            
			//if(temp >= heapArr[child]) break;    //max heap
            
			if(temp <= heapArr[child]) break;      //min heap
            
			heapArr[parent] = heapArr[child];   // swap 하는 방법이 아닌 삽입정렬과 비슷한 수행
			parent = child;
			child *= 2;
		}
		
		heapArr[parent] = temp;             // 삽입정렬과 비슷한 수행을 한다. save한 거를 맨 마지막에 넣기
		return data;
	}
	
    
	public void printHeap(){
		//System.out.printf("\n Max Heap : ");
		System.out.printf("\n Min Heap : ");
		for(int i=1; i<=SIZE; i++)
			System.out.printf("[%d] ", heapArr[i]);
	}
    
	public static void main(String[] args) {
		HeapSort h = new HeapSort();
		h.insertHeap(80);
		h.insertHeap(50);
		h.insertHeap(70);
		h.insertHeap(10);
		h.insertHeap(60);
		h.insertHeap(20);
		
		h.printHeap();
	
		int n, data;
		n = h.getHeapSize();
		for(int i=1; i<=n; i++){    
			data = h.deleteHeap();  
			System.out.printf("\n 출력 : [%d]", data);
		}
	}
}