6-1 ~ 6-3
선택정렬
1. arr[0]과 뒤에 있는 수들을 비교한다
2. 비교한 수 중에서 가장 작은것과 자리를 바꾼다
3. 최솟값은 arr[0]에 들어가있을테니 arr[1]부터 다시 위의 과정을 반복한다
4. 순서대로 정렬된다
버블정렬
1. arr[0]과 arr[1]의 크기를 비교
2. arr[1]이 더 크다면 순서를 바꾼다
3. 바뀐 arr[1]과 arr[2]를 다시 비교
4. arr[1]이 더 크다면 순서를 바꾼다
5. 이를 반복하다보면 가장 큰 수가 가장 뒤로 간다
6. 총 배열의 길이가 n이라 하면 다음은 첫번째부터 n-1번째까지 진행한다
7. 순서대로 정렬된다
삽입정렬
1. arr[0]과 arr[1]의 크기를 비교
2. 두 개의 순서를 바꾼다
3. arr[0]과 arr[1] 그리고 arr[2]를 비교한다
4. 이 때 arr[2]를 앞, 사이 혹은 뒤에 배치시킨다 (정렬)
5. 뒤의 배열값들도 반복
6. 순서대로 정렬된다
6-5
Arrays.sort(arr);sort를 쉽게 해보자!
6-7
좌표 정렬
class Point implements Comparable<Point>{
public int x,y;
생성자()
@Override
public int compareTo(Point o){
if (this.x == o.x) { // x좌표가 같다면
return this.y - o.y; // y좌표 오름차순
} else {
return this.x - o.x; // x좌표 오름차순
}
}
}Point라는 class를 만든 뒤 Comparable이라는 interface를 상속해온다. 그리고 x좌표 y좌표를 할당해준 뒤 compareTo라는 메서드를 오버라이딩 해온다. 이 때 오름차순으로 정렬 시켜주려면 return값은 음수가 되게 해야한다. (this.y = 10, o.y = 20 -> 계산 : -10)
혹은 반대로 내림차순으로 정렬하려면 부호를 반대로 하면 될 것이다. 좌표를 정렬해야할 때 이 방법은 외워서 쓰자.
ArrayList<Point> arr = new ArrayList<>();
for (~~) {
int x = ~
int y = ~
arr.add(new Point(x,y));
}
Collections.sort(arr);Point class로 만든 것을 ArrayList 안에 넣어주어 arr 리스트를 만든다. 그리고 Point(x,y)객체를 만들어서 arr에 추가해준다.
또한 위에서 Comparable interface를 상속받아 만들어놓은 것이 있다면 Collections.sort(arr)를 해주었을 때 위에서 정의한 기준대로 정렬이 된다.
6-8
이분 검색
앞에서 풀어본 방식과 비슷하다.
lt = 0, rt=(나올 수 있는 값중 최댓값)으로 셋팅해놓는다.
그리고 mid = (lt + rt) / 2 를 한 뒤 mid에서의 값을 구한다.
만약 mid보다 작아야 한다면 rt = mid - 1로 맞춰서 다시 위를 반복하고, mid보다 커야 한다면 lt = mid + 1로 맞춰서 반복한다.
6-9 ~ 6-10
정리하기는 좀 애매하다. 그냥 다시 풀어보자.
