🔷 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
탐색 키(search key)
: 자료를 구별하여 인식할 수 있는 키순차 검색(sequential search)
이진 검색(binary search)
인덱싱(indexing)
🔷 일렬로 되어 있는 자료를 순서대로 검색하는 방법
🔷 정렬되어 있지 않은 경우
O(n)
)public static boolean searchForNoSort(int key) {
for(int i = 0; i < arr.length; i++) {
if(arr[i]==key)
return true;
}
return false;
}
🔷 정렬되어 있는 경우
시간복잡도는 O(n)으로 같다.
🔷 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
❗ 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
public static boolean binarySearch(int key) {
int st = 0;
int ed = arr2.length-1;
while(st <= ed) {
int mid = (st+ed) / 2;
if(arr2[mid] == key)
return true;
else if(arr2[mid] > key) {
ed = mid-1;
}
else {
st = mid+1;
}
}
return false;
}
🌟 Arrays.binarySearch()로 구현이 이미 되어있다.
🔷 셀렉션 알고리즘
🔷 선택 과정
🔷 선택 정렬
💡 셀렉션 알고리즘을 전체 자료에 적용한 것
💡 O(n^2)
public static void selectionSort() {
int N = arr3.length;
// 한 사이클이 종료될 때마다 하나씩 정렬되므로 N-1번
// i번째의 자리를 정렬
for(int i = 0; i < N-1; i++) {
int minIdx = i; //i번째가 가장 작다고 초기화
for(int j = i+1; j<N; j++) {
if(arr3[j] < arr3[minIdx]) {
minIdx = j;
}
}
int tmp = arr3[i];
arr3[i] = arr3[minIdx];
arr3[minIdx] = tmp;
}
System.out.println(Arrays.toString(arr3));
}
🔷 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
❗ 제한 사항
💡 O(n + k): n은 배열의 길이, k는 정수의 최대값
🔷 정렬 과정
1) Data에서 각 항목들의 발생 횟수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 배열 counts에 저장한다.
2) 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 counts의 원소를 조정한다. (누적합
)
3) 정렬한 자료를 넣을 배열을 만들고 Data의 뒤에서 부터 확인한다. 확인한 값과 일치하는 count의 인덱스에 들어있는 값을 1 빼고 그 값에 해당하는 새로 만든 배열의 인덱스에 확인한 값을 넣는다.
🤷♂️ 왜 뒤에서부터 확인을 하죠?
카운팅 정렬의 특징인안정 정렬
을 위해서 뒤부터 확인함. 그래야 정렬이 보장됨.
💡
안정 정렬
같은 값을 가지는 복수의 원소들이 정렬 후에도 정렬 전과 같은 순서를 가지는 것
int nums[] = {8, 8, 12, 21 ,21 ,19, 3, 35, 60};
int N = nums.length;
// 1. 데이터 중 가장 큰 값을 알아야한다.
int K = -1;
for(int i = 0; i < N; i++) {
if(K < nums[i])
K = nums[i];
} // 가장 최대값을 찾는 for
int [] count = new int [K+1]; // 0~60: 61칸 짜리 count 배열 생성
// 2. 개수 카운팅
for(int i = 0; i < N; i++) {
// nums[i] 값을 인덱스로 하여 카운트를 증가
count[nums[i]]++;
}
// 3. 누적합 구하기 (들어갈 수 있는 위치를 결정하고 안정정렬을 가능하게 함)
for(int i = 1; i < count.length; i++) {
count[i] += count[i-1];
}
// 4. 새 배열을 만들고 원본 배열의 뒤에서부터 순회를 하며 정렬된 배열에 차곡차곡 저장한다.
int [] sortArr = new int[N];
for(int i = N-1; i >= 0; i--) {
// 지금 저장하고 싶은 값: nums[i]
// 저장 하고싶은 위치: count[nums[i]]-1 -> 하고나서 한번 더 count[nums[i]]--;
sortArr[--count[nums[i]]] = nums[i];
}
System.out.println(Arrays.toString(sortArr));
❗ 값 중 최대 값이 지나치게 크면 메모리 낭비가 발생할 수 있다. (배열이 상당히 길어짐)
그래서 값이 모여있고, 최대 값이 작은 경우에 사용을 추천