알고리즘_정렬
1. 선택정렬
- 각 루프마다
- 최대 원소를 찾는다
- 최대 원소와 맨 오른쪽 원소를 교환한다.
- 맨 오른쪽 원소를 제외한다.
-
하나의 원소만 남을때까지 루프를 반복
- 시간복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n2)
- 최악, 평균, 최선의 경우에도 n(n-1)/2 번의 연산을 수행하므로 O(n2) 이다.
package study;
import java.util.Arrays;
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {3,5,4,8,6,1,7,9,2};
System.out.println("정렬 전 : " + Arrays.toString(arr));
SelectionSort sort = new SelectionSort();
sort.selectSortMin(arr);
System.out.println("정렬 후 : " + Arrays.toString(arr));
}
public void selectSortMin(int[] arr) {
int min;
int tmp;
for (int i = 0; i < arr.length; i++) {
min = i;
for (int j = i+1; j < arr.length; j++) {
if(arr[min] > arr[j]) {
min = j;
}
}
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
public void selectSortMax(int[] arr) {
int max;
int tmp;
for (int i = arr.length-1; i > 0; i--) {
max = i;
for (int j = i-1; j >= 0; j--) {
if(arr[max] < arr[j]) {
max = j;
}
}
tmp = arr[i];
arr[i] = arr[max];
arr[max] = tmp;
}
}
}
2. 버블정렬
- 각 루프마다
- 연속된 두개 원소를 비교한 후 큰 값을 뒤로 넘긴다.(오름차순 기준)
- 마지막 번째에 도착한 원소가 가장 큰값이 된다.
- 맨 오른쪽(마지막 번째) 원소를 제외한다.
- 하나의 원소만 남을때까지 루프를 반복
- 시간복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n2)
- 최악, 평균, 최선의 경우에도 n(n-1)/2 번의 연산을 수행하므로 O(n2) 이다.
package study;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {3,5,4,8,6,1,7,9,2};
System.out.println("정렬 전 : " + Arrays.toString(arr));
BubbleSort bs = new BubbleSort();
bs.bubbleSort(arr);
System.out.println("정렬 후 : " + Arrays.toString(arr));
}
public void bubbleSort(int[] arr) {
for (int i = arr.length-1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if(arr[j] > arr[j+1]) {
int tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
}
}
}
삽입정렬
- 맨 처음 원소는 정렬된 상태로 본다.
- 각 루프마다
- 자신의 앞 원소들을 비교하면서 자신이 들어가야 할 자리를 찾아 들어간다
- 본인의 자리를 찾았다면 그 사이에 값을 넣기 위해, 기존의 원소들을 한칸씩 옮겨야 한다.
- 이러한 번거러움을 줄이기 위해 뒤에서부터 탐색하는 방향으로 한다.
- 시간복잡도 : T(n) = (n-1) + (n-2) + … + 2 + 1 = O(n2)
- 최선의 경우는 O(n) 의 연산을 가진다.
package study;
import java.util.Arrays;
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {3,5,4,8,6,1,7,9,2};
System.out.println("정렬 전 : " + Arrays.toString(arr));
InsertionSort is = new InsertionSort();
is.insertionSort(arr);
System.out.println("정렬 후 : " + Arrays.toString(arr));
}
public void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if(arr[j-1] > arr[j]) {
int tmp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = tmp;
}
}
}
}
}
마치며
-
평소에 코딩테스트 문제를 풀때에 아무런 고민 없이 자바에서 제공하는 라이브러리(Arrays.sort())를 이용하여 정렬을 했었다. 그 라이브러리는 어떤 정렬 알고리즘으로 구현이 됐는지 전혀 모른채… (알아보니 이중 퀵 소트 라던데, 다음에 이 정렬에 대해 알아보는 포스트를 작성 해야겠다.)
-
그리하여 오늘은 기본적인 정렬 알고리즘에 대해서 공부해보았다. 각각의 정렬 알고리즘은 어떻게 동작하는지 알아보고, 코드로 직접 구현해보는 것(막상 직접 손으로 구현하라고 했을때 시간이 꽤 걸렸다ㅠ)이 중요한 것 같다. 특히 삽입정렬은 원소를 특정위치에 집어 넣을때 기존 원소들을 한칸씩 뒤로 미루는 작업을 해야하는것.