원글 페이지 : 바로가기
버블 정렬 (Bubble Sort) 버블 정렬이란 인접한 두 원소를 비교하면서 크기가 작은 요소를 앞으로 이동시키고 큰 요소를 뒤로 이동시키면서 배열 정렬을 수행하는 방식의 알고리즘이다. public static int[] bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
} 시간 복잡도 배열의 원소들을 각 pass 마다 N-1, N-2, N-3, …번 비교해야 한다. 최악의 경우(오름차순으로 정렬해야 하는데 현재 내림차순으로 정렬되어 있는 경우) 모든 원소들을 서로 교환해야 한다. Total no. of passes : n-1 Total no. of comparisons : n * (n-1) / 2 따라서, 시간 복잡도는 O(N^2) 선택 정렬 (Selection Sort) 선택 정렬은 배열에서 최솟값을 맨 앞의 원소와 교환하고, 그 다음으로 작은 값을 찾아 두 번째 위치와 교환하는 과정을 반복하여 전체 배열이 정렬될 때까지 반복하는 알고리즘이다. static int[] selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[index]) {
index = j;
}
}
if (index != i) {
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
return arr;
} 시간 복잡도 N-1번의 사이클을 반복하고, 각 사이클 내에서 다른 원소들과 N-1, N-2, N-3, … 번의 비교를 하게 된다. Total no. of passes: n-1 Total no. of comparisons: n*(n-1)/2 따라서, 시간복잡도는 O(N^2) 삽입 정렬 (Insertion Sort) 삽입 정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분 배열과 비교하여, 적절한 위치에 삽입하는 방식으로 정렬을 수행한다. static int[] insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int position = i - 1;
while (position >= 0 && arr[position] > key) {
arr[position + 1] = arr[position];
position -= 1;
}
arr[position + 1] = key;
}
return arr;
} 시간복잡도 N-1개의 원소들에 대해서 각각 N-1, N-2, N-3, … 번의 비교를 반복한다. 따라서 시간 복잡도는 O(N^2) 선택 정렬과 삽입 정렬 선택 정렬과 삽입 정렬 중 어떤 게 더 나은지는 경우에 따라 다르다. 임의로 정렬된 배열 같은 평균적인 경우라면 두 정렬은 유사하게 수행된다. 거의 정렬된 데이터를 다룰거라고 가정한다면 삽입 정렬이 더 낫다. 대부분 역순으로 정렬된 데이터를 다룰 거라고 가정한다면 선택 정렬이 더 빠르다. 데이터가 어떻지 전혀 알 수 없다면 기본적으로 평균적인 경우이기 때문에 둘 다 같다. 출처 https://velog.io/@minji0801/%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%AC-vs-%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%AC-vs-%EC%82%BD%EC%9E%85%EC%A0%95%EB%A0%AC-%EC%B0%A8%EC%9D%B4-%EC%A0%9C%EB%8C%80%EB%A1%9C-%EC%95%8C%EA%B3%A0%EA%B0%80%EC%9E%90