삽입 정렬(insertion sort)
자료 배열의모든 요소를 앞에서 부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위 치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정 한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 입력 자료가 역순인 경우 최악인 O(n2)이다. 입력 자료가 정렬된 경우 최선으로 O(n)이다. public class SortTest { @Test void insertion() { int[] array = new int[]{5,9,3,1,2,8,4,7,6}; // int[] array = new int[]{1,2,3,4..
2021. 7. 21.
선택정렬(Selection Sort)
단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 리스트를 정렬하려고 할 때 버블 정렬과 같은 O(n2)의 성능을 낸다. 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복한다. public class SortTest { @Test void select() { // int[] array = new int[]{5,9,3,1,2,8,4,7,6}; int[] array = new int[]{1,2,3,4,5,6,7,8,9}; // int[] array = new int[]{9,8,7,6,5,4,3,2,1}; int indexMin, temp; for (int i = 0; i < array.length - 1; i++) { indexMin = i; for (int j = i +..
2021. 7. 20.
버블 정렬(bubble sort)
비효율적이지만 코드가 단순하기 때문에 자주 사용된다 최악의 경우 역순으로 정렬되어 있는 리스트를 정렬하려고 할 때 O(n2)의 성능을 낸다. 순환할 때마다 하나의 원소만 변경하기때문이다. 이미 정렬되어 있는 경우 O(n)의 성능을 낸다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. public class SortTest { @Test void bubble() { int[] array = new int[]{5,9,3,1,2,8,4,7,6}; // int[] array = new int[]{1,2,3,4,5,6,7,8,9}; // int[] array = new int[]{9,8,7,6,5,4,3,2,1}; int tem..
2021. 7. 13.
