전체 글

선택 정렬은 0번 인덱스를 마지막번 인덱스까지 차례대로 비교해 가장 작은 값을 찾아 0번에 놓고, 1번 인덱스를 차례대로 비교해 그 중 가장 작은 값을 찾아 1번에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행하고 나면 최소값이 맨 앞에 오게 되므로 2회전에서는 맨 앞인 0번 인덱스를 빼고 정렬을 진행하면 된다. 선택 정렬의 성능 분석 공식은 T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)로 버블정렬과 동일하다. 5 3 1 4 2를 가지고 선택 정렬을 수행하는 과정은 위의 이미지와 같다. 최소값을 담아둘 임의의 변수 min값이 필요함을 알 수 있다. 자바로 작성하면 다음과 같다. public class Selection { public static v..

버블 정렬은 배열의 0번 인덱스와 1번 인덱스를 비교하고 1번 인덱스와 2번 인덱스를 비교하는 과정을 처음부터 마지막 인덱스까지 반복하여 진행한다. 즉 인접 인덱스를 비교하면서 정렬하는 방식이다. 1회전을 수행하고 나면 제일 큰 숫자가 맨 뒤에 위치하게 된다. 따라서 다음 회전에서는 마지막 인덱스-1까지만 고려한다. 버블 정렬의 성능 분석 공식은 S(n) + S(n-1) + … + S(2) = (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1 가 된다. 여기서의 S(n)은 인덱스 비교하는 시간 = 교환하는 시간이라고 한다. 식을 정리하면 O(n^2) 임을 알 수 있다. 위의 이미지에서는 5 3 1 4 2 의 자료를 정렬하는 과정을 보여주고 있다. 이를 자바 소스 코드로 작성하면 다음과 ..