치악산 복숭아

삽입 정렬 배열을 정렬된 부분과 정렬이 안된 부분으로 나눈다. 정렬이 안 된 부분의 첫 번째 요소를 정렬된 부분의 적절한 위치에 삽입하여 정렬하는 과정을 반복한다. 수행 방법 정렬은 배열의 두번째 인덱스부터 시작한다. 현재 위치의 요소값을 저장해놓은 뒤 왼쪽의 요소값과 비교하면서 삽입한다. 수행 시간: O(n^2) Best: 1+1+1+…(n-1): θ(n) Average: θ(n^2) Worst: 1+2+…+(n-1): θ(n^2) 특징 값들이 거의 정렬되어 있을때 빠르게 실행 추가 공간 불필요 입력 크기가 크지 않고 거의 정렬되어 있을 때 적절 코드 구현 더보기 public class Sort { public void insertionSort(int[] a) { int i, j, temp; for (..

버블 정렬 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(bubble) 정렬이라고 함 수행 방법 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬됨 수행 시간: θ(n^2) 첫 for 루프는 n-1번 반복 두번째 for 루프는 각각 i-1, i-2, …, 2, 1번 반복 원소 교환은 상수 시간 작업 코드 구현 더보기 public class Sort { public void bubbleSort(int[] a) { int size = a.length; for (int i = size - 1; i > 0; ..

선택 정렬(selection sort) 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬 수행 방법 각 루프마다 최소 원소를 찾는다 최소 원소와 맨 왼쪽 원소를 교환한다 맨 왼쪽 원소를 제외한다 하나의 원소만 남을 때까지 위의 루프를 반복 수행 시간: O(n2) • for 루프는 n-1번 반복 • 가장 큰(또는 작은) 수를 찾기 위한 비교횟수: n(n-1)/2 • 숫자 사이의 자리 교환은 상수 시간 작업 특성 • 모든 입력에 대해 동일한 θ(n^2) 알고리즘 • 입력 크기가 작고 요소들간의 교환 비용이 큰 경우 적절한 알고리즘 코드 구현 더보기 public class Sort { //최댓값을 오른쪽으로 public void selectionSort(int[] a) { i..