[Sorting] sorting 코드 정리(Java)

    기본적인 sorting 내용 몇개를 정리하여 공유한다 (사실 임시저장 글에 남아있는게 보기 싫어서...)
추후 python ver도 업로드 하도록 하겠다!

import java.util.Arrays;

public class Sort {

	public static void main(String[] args) {
		// 정렬하고자 하는 배열
		int[] arr = {10,23,21,22,22,1,4,6,9,23,2,0,7,41,13};
		bubbleSort(arr);
		selectionSort(arr);
		insertionSort(arr);
		QuickSort(arr);
		MergeSort(arr);
		HeapSort(arr);
	}
	
	// ==================================================================
	// 거품정렬
	// -> 서로 인접한 두개 대소비교를 반복
	// -> 맨 뒷쪽부터 차곡차곡 완성됨
	private static void bubbleSort(int[] arr) {
		for(int i=0; i<arr.length; i++) {
			for(int j=1; j<arr.length-i; j++) {
				if(arr[j-1] > arr[j]) {
					swap(arr, j-1 , j);
				}
			}
		}
		System.out.println("버블 : " + Arrays.toString(arr));
	}

	// ==================================================================
	// 선택정렬
	// -> 배열에서 최소값 찾아서 차례대로 맨 앞에서부터 교체
	private static void selectionSort(int[] arr) {
		for(int i=0; i<arr.length-1; i++) {
			int minIndex = i;
			for(int j=i+1; j<arr.length; j++) {
				if(arr[j] <arr[minIndex]) {
					minIndex = j;
				}
			}
			swap(arr, minIndex, i);
		}
		System.out.println("선택 : " + Arrays.toString(arr));
	}

	// ==================================================================
	// 삽입정렬
	// -> 현재의 값을 저장해두고, 자기 앞을 쭉 보면서 자기보다 작은값 바로 뒤에 집어넣음
	// -> 중간에 값들은 계속 한칸씩 뒤로 끌어당김
	private static void insertionSort(int[] arr) {
		for(int index=1; index<arr.length; index++) { // index는 두번째부터
			int temp = arr[index]; // 현재의 값 미리 저장(덮어쓰여지기 때문에)
			int prev = index-1; // 이전의 위치
			// 이전인덱스가 음이 아니고, 이전값이 현재값보다 크면
			while( prev>=0 && arr[prev] > temp ) {
				arr[prev+1] = arr[prev]; //한칸씩 쭉 땡긴다.
				prev--;
			}
			arr[prev+1] = temp;
		}
		System.out.println("삽입 : " + Arrays.toString(arr));
	}

	// ==================================================================
	// 퀵정렬
	// -> 기본적으로 재귀방식, 피벗 정해서 계속 sorting.
	// -> 피벗을 중심으로, 큰파트, 작은파트가 결정 -> 반복
	private static void QuickSort(int[] arr) {
		qSort(arr, 0, arr.length-1);
		System.out.println(" 퀵 : " + Arrays.toString(arr));
	}
	// 재귀 파트
	private static void qSort(int[] arr, int left, int right) {
		if(left >= right) return;
		
		// mid값을 찾으면서 swap
		int mid = partition(arr, left, right);
		qSort(arr, left, mid-1);
		qSort(arr, mid, right);
	}
	// 파티션 파트
	private static int partition(int[] arr, int left, int right) {
		int pivot = arr[(left+right)/2];
		while(left<=right) {
			while(arr[left]<pivot) left++;
			while(pivot<arr[right]) right--;
			// 처음으로 만나는, 순서 못맞춘 두놈
			if(left<=right) { // 스왑함
				swap(arr, left, right);
				left++;
				right--;
			}
		}
		// 피벗만큼은 자리 확정
		return left;
	}	
	// ==================================================================
	// 병합정렬
	// 끝까지 분기를 먼저 하고 merge 하는 방식
	// merge시에 합쳐짐.
	private static void MergeSort(int[] arr) {
		mSort(arr, 0, arr.length-1);
		System.out.println("병합 : " + Arrays.toString(arr));
	}
	// 재귀 파트
	private static void mSort(int[] arr, int left, int right) {
		if(right-left<2) return; // 배열 크기가 2보다 작은 경우
				
		int mid = (left+right)/2;
		
		mSort(arr, left, mid);
		mSort(arr, mid+1, right);
		merge(arr, left, mid, right);	
	}
	
	// 합치는 파트
	private static void merge(int[] arr, int left, int mid, int right) {
            int[] temp = new int[right - left];
            int t = 0, l = left, h = mid;

        while (l < mid && h < right) {
       		if (arr[l] < arr[h]) {
        		temp[t++] = arr[l++];
        	} else {
        		temp[t++] = arr[h++];
        	}
        }

        while (l < mid) {
        	temp[t++] = arr[l++];
        }

        while (h < right) {
        	temp[t++] = arr[h++];
        }

        for (int i = left; i < right; i++) {
        	arr[i] = temp[i - left];
        }
	}
	
	// ==================================================================
	// 힙정렬
	private static void HeapSort(int[] arr) {
		int n = arr.length;
		
		// Init, max heap
		for(int i=n/2-1 ; i>=0; i--) {
			heapify(arr, n, i);
		}
		
		for(int i=n-1 ; i>0; i--) {
			swap(arr, 0, i);
			heapify(arr, i, 0);
		}
		
		System.out.println(" 힙 : " + Arrays.toString(arr));
	}
	
	private static void heapify(int[] arr, int n, int i) {
		int p = i;
		int left = i*2 + 1;
		int right = i*2 + 2;
		
		if(left<n && arr[p] < arr[left]) {
			p = left;
		}
		if(right<n && arr[p] < arr[right]) {
			p = right;
		}
		if(i!=p) {
			swap(arr, p, i);
			heapify(arr, n, p);
		}
	}

	// ==================================================================
	private static void swap(int[] arr,int a,int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	
}