[Java] 정렬 알고리즘

1. 선택 정렬(Selection Sort)

1) 전체 배열에서 가장 작은 요소를 찾고 그 요소를 배열의 첫 번째 요소와 교환
2) 두 번째 요소와 마지막 요소 중 가장 작은 요소를 찾은 후 두 번째 요소와 교환
3) 과정 반복

public class SelectionSort {

	public static void main(String[] args) {
		int [] arr = {6, 2, 64, 39, 21, 78, 55};
		int i;
		
		System.out.print("정렬 전 배열 : ");
		for(i = 0; i < arr.length; i ++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		
		selectionSort(arr);
		
		System.out.print("정렬 후 배열 : ");
		for(i = 0; i < arr.length; i ++) {
			System.out.print(arr[i] + " ");
		}
	
		
	}

	private static void selectionSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if(arr[i] > arr[j]) { 
                  //arr[i]와 arr[j(i+1)] 값을 비교한다. 
                  //arr[i]가 arr[j] 값보다 클 경우 요소의 위치를 서로 바꿔준다.
					int temp; 
					temp = arr[i];//temp에 arr[i]값을 넣어준다.
					arr[i] = arr[j];//arr[i]보다 더 작은 arr[j]값을 arr[i]에 넣어준다. 
					arr[j] = temp;//temp에 저장된 arr[i]값을 arr[j]에 넣으면서 두 숫자의 자리를 교환
				}
			}
		}
	}

}

2. 삽입 정렬

삽입 정렬(Insertion Sort)
1) 정렬된 부분과 정렬이 안 된 부분으로 나눈다.
2) 정렬이 안 된 부분의 첫 번째 요소를 정렬된 부분의 요소들과 비교
3) 정렬된 부분의 적절한 위치에 삽입하여 정렬하는 과정 반복
유튜브 추천 영상 : 인설션소트 삽입정렬 5분만에 이해하기 - Gunny

public class InsertionSort {

	public static void main(String[] args) {

		int[] arr = { 9, 5, 25, 70, 60, 30, 1, 8 };
		System.out.println("정렬 전 배열 : ");
		for (int i : arr) {
			System.out.print(i + " ");
		}
		System.out.println();

		insertionSort(arr);

		System.out.println("정렬 후 배열 : ");
		for (int i : arr) {
			System.out.print(i + " ");
		}
		System.out.println();

	}

	private static void insertionSort(int[] arr) {
		for (int i = 1; i < arr.length; i++) {
			int element = arr[i];//삽입할 요소 arr[i]를 저장
			int j = i - 1;//삽입할 요소 arr[i]의 바로 전 요소인 arr[i-1]값과 비교하기 위해 j를 i-1로 저장


			//arr[i]를 삽입할 위치를 찾는다
			while (j >= 0 && arr[j] > element) { //j가 0보다 크고 arr[i]의 값이 arr[j]보다 크면
				arr[j + 1] = arr[j];//arr[j]를 오른쪽으로 한 자리 이동
				j = j - 1;//arr[j]의 앞 요소와 비교하기 위해 j-1 
				//만약 j의 값이 0보다 작으면 첫 번째 요소와 비교한 것이기 때문에 while문 종료
			}
			//arr[i]값을 찾은 위치에 삽입
			arr[j + 1] = element;//while문에서 j-1을 했기 때문에 다시 +1 
			
		}
	}

}

3. 힙 정렬(Heap Sort)

자료 구조를 이용하여 정렬하는 알고리즘
1) 주어진 배열에 대해 힙을 구성
2) (남은) 힙에서 루트 노드(최댓값)을 제거