Glion 의 안드로이드 개발노트
Java(자바) - 선택정렬, 버블정렬, 삽입정렬, LRU(Least Recently Used) 본문
오늘 학습한 선택정렬, 버블정렬, 삽입정렬, LRU 알고리즘에 대해 정리한다.
1. 선택정렬
주어진 리스트에서 최소값을 찾고, 그 값을 맨 앞의 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체하는 정렬이다.
n개의 리스트가 주어졌을때 시간복잡도는 O(n^2)이다.
전체 배열의 개수가 n일때 인덱스는 n-1까지 존재한다. 0부터 n-2까지 반복하는 i for 문에서 idx를 i 로 두고 j+1부터 n까지 반복하는 j for문을 내부에서 반복하며 array[j] < array[idx] 를 판별하여 idx위치의 값보다 j의 위치의 값이 작으면 idx를 j로 한다.(최솟값 인덱스 탐색)
j for문 반복이 끝나면 array[i]의 값과 array[idx] 값의 위치를 교환해준다.
이 과정을 반복하는 i for 문이 끝나면 최종적으로 array는 오름차순으로 정렬된 배열이 된다.
i for문을 n-2까지만 반복하는 이유는, i가 n-2일때 마지막에 위치한 값과 교환이 되므로 마지막 위치의 값까지 정해지기 때문이다.
1 2 3 4 6 5이고, i가 현재 4일때(n-2), idx 는 4이고, j for 문으로 넘어갔을때 j 는 5부터 시작이므로 arr[5] 는 5, arr[idx] 는 6이다.
arr[5]>arr[idx] 일 경우 idx는 5가 되고, arr[4]와 arr[5]를 교환한다. 앞부분은 이미 최솟값으로 정렬이 되어있기 때문에 여기까지만 해도 전체 배열이 오름차순으로 정렬이 완료된다.
말로 풀어냈더니 무슨 소린지 하나도 모르겠는데, 코드와 그림으로 확인해보자
for (int i = 0; i < n - 1; i++) {
int idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[idx])
idx = j;
}
int tmp = arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
}n에 4를, 배열 arr이 1,4,2,3 이라고 하자.
| 1 | 4 | 2 | 3 |
i가 0부터 2까지 반복한다. idx는 0이다
j가 1부터 3까지 반복하며 arr[j]<arr[idx]인 경우 idx를 j로 교체한다.
j=1 일때, arr[1] < arr[0] => 4 < 1, 성립 안함.
j=2 일때, arr[2] < arr[0] => 2 < 1, 성립 안함.
j=3 일때, arr[3] < arr[0] => 3 < 1, 성립 안함.
arr[i] 와 arr[idx]를 교체한다. i와 idx가 같으므로 교체해도 동일하다.
| 1 | 4 | 2 | 3 |
다음 반복 (i 가 1일때)
idx = 1 이다. j는 2부터 3까지 반복한다.
j=2 일때, arr[2] < arr[1] => 2 < 4, 성립. idx = 2가 된다.
j=3 일때, arr[3] < arr[2] => 3 < 2, 성립 안함.
arr[i] 와 arr[idx]를 교체한다. 다음과 같이 된다.
| 1 | 2(교체) | 4(교체) | 3 |
다음 반복 (i가 2일때)
idx = 2 이다. j는 3부터 3까지 반복한다.
j=3 일때, arr[3] < arr[2] => 3 < 4, 성립. idx = 3이 된다.
arr[i] 와 arr[idx]를 교체한다. 다음과 같이 된다.
| 1 | 2 | 3(교체) | 4(교체) |
반복이 끝났을때 오름차순으로 정렬된 모습을 확인할 수 있다.
2. 버블정렬
서로 인접한 두 원소를 비교하여 정렬하는 알고리즘이다. 마치 물속에서 공기방울이 계속 위로가는 모습과 유사하다고 하여 버블정렬이라고 한다. 1회전을 수행하고 나면 가장 큰 값이 제일 뒤로 이동한다. 시간복잡도는 O(n^2) 이다.
코드는 다음과 같이 구현했다.
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}배열의 길이 n이 4,배열 arr이 1,3,4,2 이라고 하자
| 1 | 3 | 4 | 2 |
i가 0부터 3 전까지, 2까지 탐색한다.
j는 0부터 n-i-1까지 탐색한다. i가 0이면 3 전까지 탐색하고, i가 1이면 2 전까지 탐색한다.
i가 0일때,
j=0, arr[0] > arr[1], 1 > 3, 성립 안함.
j=1, arr[1] > arr[2], 3 > 4, 성립안함.
j=2, arr[2] > arr[3], 4 > 2, 성립함. 교환해준다. 다음과 같이 변한다
| 1 | 3 | 2(교체) | 4(교체) |
i=1 일때, j는 0부터 2 전 까지 탐색한다.
j=0, arr[0] > arr[1], 1 > 3, 성립 안함.
j=1, arr[1] > arr[2], 3 > 2, 성립안함. 교환해준다. 다음과 같이 변한다
| 1 | 2(교체) | 3(교체) | 4 |
3. 삽입정렬
리스트의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하고, 나머지를 뒤로 밀며 정렬한다.
선택정렬이나 버블정렬과 같이 시간복잡도는 O(n^2)이나, 이들보다 빠르다.
2중 for문을 사용하여 구현한다. i는 1번 인덱스부터 배열 전체를 돈다. 여기서 tmp는 array[i]의 값이다. j는 i 바로 앞에서 0번 인덱스까지 역으로 돌며 array[j]가 tmp보다 크면 array[j]를 한칸 뒤로 밀고, array[j] 가 tmp보다 크지 않으면(else) j for문을 break로 탈출한다.
j for문이 끝나면 j 인덱스의 바로 '뒤'에 tmp를 삽입한다. 위의 과정을 반복하여 i for문까지 끝나면 최종적으로 오름차순이 된 배열이 완성된다.
코드로 구현한 내용은 다음과 같다.
for (int i = 1; i < n; i++) {
int tmp = arr[i];
int j; // j for문 scope 밖에서 j를 사용할 것이기 때문에 밖에다 선언해주는 모습이다.
for (j = i - 1; j >= 0; j--) {
if (arr[j] > tmp)
arr[j + 1] = arr[j];
else
break;
}
arr[j+1] = tmp;배열의 길이 n이 5, 배열 arr이 31, 25, 12, 22, 11 이라고 하자.
| 31 | 25 | 12 | 22 | 11 |
i는 1에서 4까지 1씩 증가하며 반복할 것이고, j for문 시작 전, tmp 는 arr[i] 이다.
i가 1일때, tmp 는 25, j는 0부터 0까지 1씩 감소하며 반복한다.(한번만 반복한다)
arr[0] > tmp, 31 > 25, True이므로 arr[1]에 arr[0]을 삽입한다.
| 31 | 31(삽입) | 12 | 22 | 11 |
j 에 -1을 하고 j for문 반복 조건을 벗어났으므로 for문 탈출. arr[j+1] = tmp를 실행한다.
j 는 -1이므로 arr[0]에 tmp를 삽입한다.
| 25(삽입) | 31 | 12 | 22 | 11 |
i가 2일때, tmp 는 12, j는 1부터 0까지 1씩 감소하며 반복한다.
arr[1] > tmp, 31 > 12, True이므로 arr[2]에 arr[1]을 삽입한다.
| 25 | 31 | 31(삽입됨) | 22 | 11 |
j 에 -1을 하고 j 는 0이 된다.
arr[0] > tmp, 25 > 12, True이므로 arr[1] 에 arr[0]을 삽입힌다.
| 25 | 25 | 31 | 22 | 11 |
j 에 -1을 하면 j가 -1이 되어 j for문 반복 조건을 벗어났으므로 for문 탈출. arr[j+1] = tmp를 실행한다.
j 는 -1이므로 arr[0]에 tmp를 삽입한다.
| 12(삽입) | 25 | 31 | 22 | 11 |
i가 3일때, tmp 는 22, j는 2부터 시작하여 0까지 1씩 감소하며 반복한다.
arr[2] > tmp, 31 > 22, True이므로 arr[3]에 arr[2]을 삽입한다.
| 12 | 25 | 31 | 31(삽입됨) | 11 |
j 에 -1을 하고 j 는 1이 된다.
arr[1] > tmp, 25 > 22, True이므로 arr[2] 에 arr[1]을 삽입힌다.
| 12 | 25 | 25(삽입됨) | 31 | 11 |
j 에 -1을 하고 j 는 0이 된다.
arr[0] > tmp, 12 > 22, false이므로 j가 0인 상태에서 for문을 탈출한다.
arr[j+1] = tmp를 실행하면
| 12 | 22(삽입됨) | 25 | 31 | 11 |
i가 4일때, tmp 는 11, j는 3부터 시작하여 0까지 1씩 감소하며 반복한다.
arr[3] > tmp, 31 > 11, True이므로 arr[4]에 arr[3]을 삽입한다.
| 12 | 22 | 25 | 31 | 31(삽입) |
j에 -1을 하고 j는 2가 된다.
arr[2] > tmp, 25 > 11, True이므로 arr[3]에 arr[2]을 삽입한다.
| 12 | 22 | 25 | 25(삽입) | 31 |
j에 -1을 하고 j는 1이 된다.
arr[1] > tmp, 22 > 11, True이므로 arr[2]에 arr[1]을 삽입한다.
| 12 | 22 | 22(삽입) | 25 | 31 |
j에 -1을 하고 j는 0이 된다.
arr[0] > tmp, 12 > 11, True이므로 arr[1]에 arr[0]을 삽입한다.
| 12 | 12(삽입) | 22 | 25 | 31 |
j 에 -1을 하고 j는 -1이 되어 j for문 반복 조건을 벗어났으므로 for문 탈출. arr[j+1] = tmp를 실행한다.
j 는 -1이므로 arr[0]에 tmp를 삽입한다.
| 11(삽입) | 12 | 22 | 25 | 31 |
모든 반복이 끝나고 최종적으로 오름차순으로 정렬이 된다.
4. LRU 알고리즘(Least Recently Used)
LRU 알고리즘은 가장 최근에 사용하지 않는 것을 교체하는 알고리즘이다. 페이징 기법으로 메모리를 관리하는 운영체제에서 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 어떤것을 교체할지 결정하는 페이지 교체 알고리즘 중 하나이다. 주로 캐시에서 메모리를 다루기 위해 사용하며 시간복잡도는 O(n)이다.
설명하기 위해 일정 크기의 캐시가 있고, 작업내용이 들어왔을 경우를 가정한다.
전체 작업 내역을 반복하면서 캐시에 해당 작업이 있는지 확인한다. 해당 작업이 있다면 hit, 없다면 miss로 한다.
miss일땐, 캐시에 존재하는 작업을 한칸씩 뒤로 민다음, 제일 앞에 현재 들어온 작업을 저장한다.
hit일떈, 이미 존재하는 작업의 앞에 있는 작업들을 한칸씩 뒤로 민 다음 현재 들어온 작업(이미 존재하는 작업)을 제일 앞에 저장한다.
위 과정을 들어온 작업 만큼 반복했을때, 모든 작업이 끝났을 때의 캐시의 상태가 나타나게 된다.
코드로 구현하면 다음과 같다.
int[] cache = new int[size];
for (int x : work) { // 각 작업을 반복하면서 작업이 캐시에 존재하는가(hit), 존재하지 않는가(miss)를 판별한다.
int pos = -1; // 위치.
for (int i = 0; i < size; i++) { // 캐시를 탐색하여 hit인지 miss인지 찾는다.
if (x == cache[i])
pos = i;
}
if (pos == -1) { // miss 일때
for (int i = size - 1; i >= 1; i--)
cache[i] = cache[i - 1];
}
else { // hit 일떄
for (int i = pos; i >= 1; i--)
cache[i] = cache[i - 1];
}
cache[0] = x;
}캐시의 사이즈가 5이고, 작업이 2,3,1,2,7 순서대로 들어온다고 할때 각 작업마다 캐시에 존재하는지, 존재한다면 그 위치를 담기위한 변수인 pos를 -1로 초기화 해두고 시작한다.
우선 캐시에 현재 작업 2가 존재하는지 for문으로 탐색하고, 존재한다면 해당 인덱스를 pos 에 저장한다. 존재하지 않으므로 pos는 -1이다.
miss이므로 i 가 size-1, 4부터 1까지 1씩 감소하는 for문을 실행, cache[i] = cache[i-1] 을 실행한다(cache[4]에 cache[3]을, cache[3]에 cache[2]를 ...) 초기에는 캐시가 비어있으므로 변화가 없다.
마지막에 cache[0] 에 현재작업 x를 저장하므로 캐시의 상태는 다음과 같다.
| 2 |
다음 작업 3을 보자.
현재 작업 3이 존재하는지 for문으로 확인했을때 존재하지 않기 떄문에 pos 는 -1 이고, miss 가 되어 캐시에 존재하는 작업을 한칸씩 뒤로 민다. 그리고 마지막에 cache[0]에 현재작업 3을 저장한다.
| 3 | 2 |
다음작업 1도 캐시에 존재하지 않기때문에 위와 같은 과정을 거쳐 캐시의 상태는 다음과 같다.
| 1 | 3 | 2 |
다음작업 2을 보자. 캐시에 존재한다.
존재하기 떄문에 pos에는 2가 저장된다.(현재 들어온 작업과 동일한 캐시에 들어있는 작업의 index)
hit이므로 pos 부터 1까지 반복하는 i for문이 실행되고, cache[i] 에 cache[i-1] 을 한다. 즉, i번째 앞에 있는 작업을 한칸씩 뒤로 미는 것이다.
cache[1]의 작업이 cache[2]에 저장되고, cache[0]의 작업이 cache[1]에 저장된다.
| 1 | 1 | 3 |
마지막에 cache[0]에 현재작업 2를 저장한다.
| 2 | 1 | 3 |
다음작업 7은 캐시에 존재하지 않기 때문에 miss이고, 전체 작업을 한칸씩 뒤로 민다음 제일 앞에 현재작업 7을 삽입한다.
최종적으로 모든 작업이 끝났을때 캐시 메모리의 상태는 다음과 같다.
| 7 | 2 | 1 | 3 |
만일 들어온 작업에 의해 저장되는데, 캐시가 꽉 차게 되면 제일 오래 사용하지 않은 페이지를 버린다.
이 과정은 한칸씩 뒤로 밀리는 과정에서 자연스럽게 사라지게 된다.