1. 정렬 알고리즘
•
정의) 데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일
•
분류)
◦
안정 정렬(Stable Sort) : 동일한 값들은 정렬 전의 위치 유지
▪
버블 정렬, 삽입 정렬, 합병 정렬
◦
불안정 정렬(Unstable Sort) : 동일한 값들이 정렬 후 순서가 바뀜
▪
퀵 정렬, 선택 정렬, 힙 정렬
•
정리) 각각의 상황에 맞는 효율적인 방법 선택
2. 버블 정렬
•
정의) 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식
•
과정)
◦
앞에서부터 두 개씩 보며 두 수가 정렬되게 끔 자리를 바꿔줌
▪
두 개씩 구간을 모두 훑고나서 정렬이 확정된 맨 마지막 자리는 다음 반복 땐 보지 않음
◦
위 과정을 배열에 아무 변화가 없을 때까지 반복함
▪
배열에 아무 변화가 없을 때 == 특정 루프의 전체 영역에서 swap이 한 번도 발생하지 않았을 때 (ex. i가 같을 때 swap 한 번도 안 한 경우)
•
예시) 6 5 3 8
◦
5 6 3 8 → i=0, j=0
◦
5 3 6 8 → i=0, j=1
◦
5 3 6 8 → i=0, j=2 → {8}은 정렬 확정
◦
3 5 6 8 → i=1, j=0
◦
3 5 6 8 → i=1, j=1 → {6,8}은 정렬 확정
◦
3 5 6 8 → i=2, j=0 → {3,5,6,8}은 정렬 확정
•
특징)
◦
매번 반복할 때마다 가장 큰 수가 제일 뒤로 감 (오름차순 정렬 기준)
◦
시간 복잡도 : 최선 O(N) , 평균 O(N^2) , 최악 O(N^2)
•
코드)
void bubbleSort (int[] arr) {
int n = arr.length; // n=4
for(int i = 0; i < n-1; i++) { // i=0,j=0~2 / i=1,j=0~1 / i=2,j=0
for(int j = 0; j < n-1-i; j++) {
if (arr[j] > arr[j+1]) // 큰 게 앞에 있다면
swap(arr[j], arr[j+1]); // 자리 바꿔서 큰 걸 뒤로 보내기
}
}
}
Java
복사
3. 선택 정렬
•
정의) 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방식
•
과정)
◦
정렬 안 된 부분에서 최소값 또는 최대값을 찾고, 정렬 안 된 부분의 가장 앞에 있는 데이터와 swap
◦
위 과정을 반복함
•
예시) 4 3 1 2
◦
1 3 4 2 → {1}은 정렬 확정
◦
1 2 4 3 → {1,2}은 정렬 확정
◦
1 2 3 4 → {1,2,3,4}은 정렬 확정
•
특징)
◦
매번 반복할 때마다 가장 작은 수가 제일 앞으로 감 (오름차순 정렬 기준)
◦
시간 복잡도 : 최선 O(N^2), 평균 O(N^2) , 최악 O(N^2)
•
코드)
void selectionSort (int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
Java
복사
참고