📖 List 2
📌 선택 정렬 (Selection Sort)
✅ 셀렉션 알고리즘 (Selection Algorithm)
- 저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법
- 최소값, 최대값, 혹은 중간 값을 찾는 알고리즘을 의미하기도 함.
✅ 선택 과정
-
정렬 알고리즘을 이용하여 자료 정렬하기
-
원하는 순서에 있는 원소 가져오기
✅ 아래는 k번째로 작은 원소를 찾는 알고리즘
-
최소값 찾기 -> k번 반복
-
1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동시키고, 배열의 k번째를 반환한다.
-
k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 한다.
Select(int[] nums, int k) {
for i from 1 to k {
minIndex = i;
for j from i+1 to n {
if nums[minIndex] > nums[j] {
minIndex = j;
}
}
swap(nums[i], nums[minIndex]);
}
return nums[k];
}- 이걸 N으로 일반화하면 그게 선택 정렬임
✅ 선택 정렬 (Selection Sort)
- 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
- 앞서 살펴본 셀렉션 알고리즘을 전체 자료에 적용한 것이다. (k -> n)
- 1 pass 마다 가장 작은 값이 제일 앞으로 온다.
- 정렬 과정
- 주어진 리스트 중에서 최소값을 찾는다.
- 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
- 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.
- 시간 복잡도
- O(N^2)
- 1pass : n-1 비교 ... n-1pass : 1회
✅ 정렬 과정
-
주어진 리스트에서 최소값을 찾는다.
-
리스트의 맨 앞에 위치한 값과 교환한다.
-
미정렬 리스트에서 최소값을 찾는다.
-
리스트의 맨 앞에 위치한 값과 교환한다.
-
미정렬 리스트에서 최소값을 찾는다.
-
리스트의 맨 앞에 위치한 값과 교환한다.
-
미정렬 리스트에서 최소값을 찾는다.
-
리스트의 맨 앞에 위치한 값과 교환한다.
- 미정렬 원소가 하나 남았을 때 마지막 원소가 알아서 가장 큰 값이므로 정렬 완료
✅ 알고리즘
SelectionSort(int[] nums, int N) {
for i from 0 to n-1 {
a[i], ..., a[n-1] 원소 중 최소값 a[k] 찾음
a[i]와 a[k] 교환
}
}✅ 선택 정렬
SelectionSort(int[] nums, int N) {
for i from 0 to N-1 {
minIdx <- i;
for f from i+1 to N {
if(nums[minIdx] > nums[j]) {
minIdx <- j;
}
}
swap(nums[i], nums[minIdx]);
}
}public class 선택정렬 {
// O(N^2)
public static void main(String[] args) {
int arr[] = {7, 1, 8, 66, 15, 34, 80, 3, 44, 65};
for(int i=0; i<arr.length-1; i++) {
int minIdx = i;
for(int j=i+1; j<arr.length; j++) {
if(arr[minIdx] > arr[j])
minIdx = j;
}
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
System.out.println(Arrays.toString(arr));
}
}✅ 정렬 알고리즘 비교
| 알고리즘 | 평균 수행시간 | 최악 수행시간 | 알고리즘 기법 | 비고 |
|---|---|---|---|---|
| 버블 정렬 | O(n^2) | O(n^2) | 비교와 교환 | 코딩이 가장 손쉽다. |
| 선택 정렬 | O(n^2) | O(n^2) | 비교와 교환 | 교환의 회수가 버블, 삽입정렬보다 작다. |
| 카운팅 정렬 | O(n+k) | O(n+k) | 비교환 방식 | n이 비교적 작을 때만 가능하다. |
| 삽입 정렬 | O(n^2) | O(n^2) | 비교와 교환 | n의 개수가 작을 때 효과적 |
| 병합 정렬 | O(nlogn) | O(nlogn) | 분할 정복 | 연결리스트의 경우 가장 효율적인 방식 |
| 퀵 정렬 | O(nlogn) | O(n^2) | 분할 정복 | 최악의 경우 O(n^2)이지만, 평균적으로는 가장 빠르다. |
📌 검색 (Search)
✅ 검색
-
저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
-
목적하는 탐색 키를 가진 항목을 찾는 것
- 탐색 키 (search key) : 자료를 구별하여 인식할 수 있는 키
-
검색 종류
- 순차 검색 (sequential search)
- 이진 검색 (binary search)
- 인덱싱 (Indexing)
✅ 순차 검색 (Sequential Search)
-
일렬로 되어 있는 자료를 순서대로 검색하는 방법
- 가장 간단하고 직관적인 검색 방법
- 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함
- 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격히 증가하여 비효율적
-
2가지 경우
- 정렬되어 있지 않은 경우
- 정렬되어 있는 경우
✅ 정렬 X 검색 과정
-
첫 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾는다.
-
키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환한다.
-
자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패
- 찾고자 하는 원소의 순서에 따라 비교회수가 결정됨
-
첫 번째 원소를 찾을 때는 1번 비교, 두 번째 원소를 찾을 때는 2번 비교
-
정렬되지 않은 자료에서의 순차 검색의 평균 비교 회수
- (1/n)*(1+2+3+...+n) = (n+1)/2
-
시간 복잡도 : O(N)
-
// a : 1차원 배열, n : 배열 크기, key : 찾고 싶은 값
sequentialSearch(int[] a, int n, int key)
i <- 0
while(i<n and a[i]!=key)
i <- i+1;
if(i<n)
return i;
else
return -1;public class 순차검색_정렬X {
// O(N)
public static void main(String[] args) {
int arr[] = {7, 1, 8, 66, 15, 34, 80, 3, 44, 65};
int result = sequentialSearch(arr, 77);
if(result == 1)
System.out.println("Find Success");
else
System.out.println("Find Fail");
}
public static int sequentialSearch(int[] arr, int key) {
int i = 0;
while(i < arr.length && arr[i] != key) {
i++;
}
if(i < arr.length)
return 1;
return -1;
}
}✅ 정렬 되어 있는 경우
- 검색 과정
- 자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정하자.
- 자료를 순차적으로 검색하면서 키 값을 비교하여, 원소의 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료한다.
import java.util.Arrays;
public class 순차검색_정렬O {
// O(N)
public static void main(String[] args) {
int arr[] = {7, 1, 8, 66, 15, 34, 80, 3, 44, 65};
Arrays.sort(arr);
int result = sequentialSearch(arr, 3);
if(result == 1)
System.out.println("Find Success");
else
System.out.println("Find Fail");
}
public static int sequentialSearch(int[] arr, int key) {
int i = 0;
while(arr[i] < key)
i++;
if(arr[i] == key)
return 1;
return -1;
}
}✅ 이진 검색 (Binary Search)
-
자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
- 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색 수행
-
이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.
-
시간 복잡도 : O(logN) (굉장히 빠른 편 (N보다 빠르다))
- 구현
- 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다.
- 이진 검색의 경우, 자료에 삽입이나 삭제가 발생했을 떄 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.
binarySearch(int[] a, int key) {
start <- 0;
end <- length(a) - 1;
while(start <= end) {
middle = (start + end) / 2;
if(a[middle] == key)
return true;
else if(a[middle] > key)
end = middle - 1;
else
start = middle + 1;
}
return false;
}import java.util.Arrays;
public class 이진검색 {
// O(logN)
public static void main(String[] args) {
int arr[] = {7, 1, 8, 66, 15, 34, 80, 3, 44, 65};
Arrays.sort(arr);
boolean check = binarySearch(arr, 80);
System.out.println(check);
}
public static boolean binarySearch(int[] arr, int key) {
int start = 0;
int end = arr.length - 1;
while(start <= end) {
int mid = (start + end) / 2;
if(arr[mid] == key)
return true;
else if(arr[mid] > key)
end = mid - 1;
else
start = mid + 1;
}
return false;
}
}
개발 공부!