배열 안에 있는 데이터를 일정한 규칙에 따라 오름차순 또는 내림차순으로 정리하는 것
정렬함으로써 탐색을 효과적으로 할 수 있고, 겹치는 데이터를 찾기 위해서도 필요
버블 정렬
인접한 두 데이터를 비교하여 큰 숫자를(오름차순시) 오른쪽으로 옮기는 것을 반복
시간복잡도 O(n^2)
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length - 1; i++) {
for(int j= 1 ; j < arr.length-i; j++) {
if(arr[j]<arr[j-1]) {
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}선택 정렬
오름차순으로 정렬시, 배열 전체를 비교해 가장 작은 값을 찾아 차곡차곡 정리하는 방법
시간 복잡도 O(n^2)
void selectionSort(int[] list) {
int indexMin, temp;
for (int i = 0; i < list.length - 1; i++) {
indexMin = i;
for (int j = i + 1; j < list.length; j++) {
if (list[j] < list[indexMin]) {
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}삽입 정렬
정렬된 원소들에 다음 원소의 위치를 파악해 삽입해나가는 정렬방법
시간 복잡도 O(n)
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){
int temp = arr[index];
int aux = index - 1;
while( (aux >= 0) && ( arr[aux] > temp ) ) {
arr[aux + 1] = arr[aux];
aux--;
}
arr[aux + 1] = temp;
}
}Share article
