이 글은 <자료구조와 알고리즘> 교과시간에 배운
탐색과 정렬 알고리즘에 대해서 정리한 글 입니다.
탐색
1. 선형 탐색 (순차 검색)
- 배열에서 요소를 찾을 때 처음부터 끝까지 순서대로 요소를 찾는 방법
- 검색 종료 조건 1 : 원하는 값을 찾았다 → 검색 성공
- 검색 종료 조건 2 : 원하는 값을 못 찾고 배열의 끝을 지나갔다 → 실패
- 소스코드 - while문 사용 버전
int seqSearch(int[] a, int n, int key){ // a : 검색 할 배열 // n : 배열의 길이 // key : 검색할 값, 목표 int i = 0; // 배열의 인덱스를 가리키는 변수 while (i < n) { if(a[i] == key) { //검색 종료 조건 1, 검색에 성공 return i; } i++; } return -1; //검색 종료 조건 2, 검색 실패 } - 소스코드 : for문 사용 버전
int seqSearch(int[] a, int n, int key){ for(int i = 0; i < n; i++){ if(a[i] == key) return i; } return -1; }
2. 선형 탐생 - 도치법
- 종료 조건이 2개인 기존의 선형 검색에서, 종료 조건을 1개로 만들었다.
- 배열의 마지막에 찾는 값을 추가한다. → 이 값을 보초라고 한다.
- 선형검색 코드와 비슷, 뒤에 보초를 추가해주는 것만 다르다.
- 소스 코드
int seqSearchSen(int[] a, int n, int key) { int i = 0; a[n] = key; //보초를 추가 한다. while (true) { if(a[i] == key){ break; } i++; } return i == n ? -1 : i; //만약 i가 n이라면 (= 마지막 요소까지 검색 했다면), 검색 실패 }
3. 이진 탐색
- 정렬 된 데이터에서 검색 하는 알고리즘
- 기준값을 정하고, 기준값과 찾는 값의 대소 비교로 검색하는 범위를 좁혀 나간다.
- 소스 코드 (오름차순으로 된 코드 기준)
int binSearch(int[] a, int n, int key){ int pl = 0; //왼쪽 범위의 초기 값 : 0번 int pr = n - 1; // 오른쪽 범위의 초기 값 : 마지막 번호 do { int pc = (pl + pr) / 2; // 기준값 : pl과 pr의 가운데 if(a[pc] == key) return pc; // 검색 성공 else if(a[pc] < key) //찾는 값이 현재 기준보다 오른쪽에 있다면 pl = pc + 1; else if(key < a[pc]) //찾는 값이 현재 기분값보다 왼쪽에 있다면 pr = pc - 1; } while (pl <= pr); //범위가 서로 바뀌지 않았을때만 실행 return -1; //검색 실패 }
정렬
- 오름차순 정렬 : 값이 점점 커진다 → 작은 값이 앞에 온다.
- 내림차순 정렬 : 값이 점점 작아진다 → 큰 값이 앞에 온다.
1. 버블 정렬
- 이웃한 순차적으로 두 수의 크기를 비교 → 교환, 과정을 반복
- 처음부터 끝까지 값을 비교해서 가는 과정을 패스라고 한다.
- 1번 패스를 완료하면 맨 앞에는 가장 작은 값이 위치한다.
- 소스 코드
void bubbleSort(int[] a, int n) { for(int i = 0; i < n; i++) { // 패스의 반복 for(int j = n - 1; j > i; j--) { //뒤에서 부터, 앞으로 값을 비교해간다. if(a[j - 1] > a[j]){ // 바로 앞에 있는 요소가 더 크다면 swap(a, j - 1, j); // 두 수를 교환 해준다. } } } }
2. 단순 선택 정렬
- 가장 작은 요소를 선택하고, 위치를 이동 시켜준다.
- 참고 : https://youtu.be/uCUu3fF5Dws
- 소스 코드
void selectionSort(int[] a, int n) { for(int i = 0; i < n - 1; i++) { int min = i; // 최소값을 기록한다. for(int j = i + 1; j < n; j++) { if(a[min] > a[j]) //min보다 더 작은 값을 발견했다면 min = j; } swap(a, min, i); // 가장 작은 값과 맨 앞의 요소와 교환한다. } }
3. 단순 삽입 정렬
- 순차적으로 요소 하나를 선택 → 앞의 요소들과 비교하면서 옮긴다.
- 참고 : https://www.youtube.com/watch?v=fIe7gdgMvMU
- 소스 코드 (몰라도 됨)
void insertSort(int[] a, int n){ for(int i = 1; i < n; i++){ int temp = a[i]; //현재 선택한 값을 저장 int j; for(j = i - 1; j >= 0 && a[j - 1] > temp; j--){ // 맨 처음 요소까지 또는 선택한 값 a[j] = a[j - 1]; //앞의 값을 뒤에 대입 } a[j] = temp; //마지막에 값을 삽입한다. } } - 장점 : 정렬을 마쳤거나 마친 상태에 가까우면 → 정렬 속도가 빠르다.
- 단점 : 삽입할 위치가 멀리 있다 → 값을 대입하는 횟수가 많다.
4. 쉘 정렬
- 단순 삽입 정렬의 장점은 살리고, 단점은 보완
- 정렬할 배열을 그룹을 나눈다 → 그룹별로 삽입 정렬을 수행한다
void shellSort(int[] a, int n) {
for(int h = 4; h > 0; h /= 2) {
for(int i = h; i < n; i++) {
int temp = a[i];
int j;
for(j = i; j >= 0 && a[j] > temp; j -= h){
a[j + h] = a[j];
}
a[j + h] = temp;
}
}
}5. 퀵 정렬
- 가장 빠른 알고리즘
- 참고 : https://youtu.be/7BDzle2n47c
- 기준 값인 pivot를 만들고, 그 값을 기준으로 그룹을 나눈다.
- pivot 값보다 작으면 왼쪽에, 더 크면 오른쪽에 위치 한다.
- 소스 코드
void quickSort(int[] a, int left, int right) { int pl = left; int pr = right; int x = a[(pl + pr) / 2]; // 피벗 값, pl과 pr의 중앙 값 do { while (a[pl] < x) pl++; // pl이 가리키는 위치가 피벗보다 작을때 -> pl을 전진 while (x < a[pr]) pr--; // pr이 가리키는 위치가 피벗보다 클때 -> pr을 전진 if(pl <= pr) swap(a, pl++, pr--); // pl과 pr이 교차하지 않았다면 -> pr과 pl의 위치를 서로 교환 } while (pl <= pr); // pl과 pr이 교차하지 않았을때 -> 계속 반복 if(left < pr) quickSort(a, left, pr); // left와 pr사이에 남은 간격이 있다면 -> 그 부분을 다시 정렬 if(pl < right) quickSort(a, pl, right); // pl과 right 사이에 남은 간격이 있다면 -> 그 부분을 다시 정렬 }
천재 개발자가 되고 싶어요