버블정렬, 삽입정렬, 선택정렬

버블정렬

• 처음부터 끝까지 길이가 N인 배열에 대해서 순회하면서 가장 큰값을 맨 뒤로 옮겨주는 방식으로
  두 인접한 원소를 비교하여 순서가 맞지않다면 교환하여 정렬하는 방법

• O(n^2)

void bubble_sort(int[] arr)
{
	boolean swaped = false;
    for (int i = 0; i < arr.length; i++)
    {
    	for (int j = 0; j < arr.length - i - 1; j++)
        {
        	if (arr[j] > arr[j+1]){
            	swaped = true;
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
		}
	}
	if (!swaped)
		return;
	}
}

삽입정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

• O(n^2)

void insertion_sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int pivot = arr[i];
        int idx = i-1;
        while (idx >= 0 && pivot < arr[idx]) {
            arr[idx + 1] = arr[idx];
            idx--;
        }
        arr[idx + 1] = pivot;
    }
}

선택정렬

• N개의 자료 배열 요소에 대해서 최소값을 찾은 후 맨 앞(패스)에 위치한 값과 교환한다. 이후 맨앞을 제외한 배열에대해 반복하여 정렬한다

void insertion_sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int pivot = arr[i];
        int idx = i-1;
        while (idx >= 0 && pivot < arr[idx]) {
            arr[idx + 1] = arr[idx];
            idx--;
        }
        arr[idx + 1] = pivot;
    }
}