SeSAC 26일차 / 정렬 알고리즘

SeSAC 26일차(2023-08-25)
정렬 알고리즘

---

 

삽입 정렬

• 삽입 정렬(Insertion Sort)
  • 배열을 정렬된 부분(앞부분)과 정렬 안된 부분(뒷부분)으로 나누고, 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복
  • 이를 반복하면 정렬 안된 부분은 아무 원소도 남지 않고, 정렬된 부분에 모든 원소가 있게 된다.
  • 시간 복잡도: O(n의 2제곱)

 

 

버블 정렬

• 버블 정렬(Bubble sort)
  • 인접한 두 수를 비교하여 오름차순이나 내림차순
  • 이웃하는 원소끼리 자리 이동으로 원소들이 이동

 

 

병합 정렬

• 병합 정렬(Merge Sort)
  • 둘 이상의 부분 집합으로 나눠서 각 부분 집합을 정렬한 다음, 부분 집합들을 다시 정렬된 형태로 합치는 방식

 

퀵 정렬

• 퀵 정렬(Quick Sort, 분할 정복)
  • 데이터 집합 내에서 임의의 기준(pivot)을 정하고 해당 pivot으로 집합을 기준으로 두 개의 부분 집합으로 나눈다.
  • 한쪽 부분은 피벗 값보다 작은 값, 다른 한 쪽은 큰 값들만 넣는다.
  • 더 이상 쪼갤 부분 집합이 없을 때까지 실행

 

실습

• Project: SortProject
• package: test.sort
• Main-class: TestSort

 

• 삽입 정렬

private static void insertSort(ArrayList<Integer> data, int size){
    int key = 0;
    int i = 0;
    int j = 0;

    for(i = 1; i < data.size(); i++) {
        key = data.get(i);

        for(j = i-1; j >= 0; j--) {
            if(data.get(j) > key) {
                data.set(j+1, data.get(j));
            } else {
                break;
            }
        }
        data.set(j+1, key);
    }
}

• 버블 정렬

private static void bubbleSort(ArrayList<Integer> data, int size) {
    int temp = 0;
    int i = 0;
    int j = 0;

    for (i = 0; i < data.size() - 1; i++) {
        for (j = 0; j < data.size() - 1 - i; j++) {
            if (data.get(j) > data.get(j + 1)) {
                temp = data.get(j);
                data.set(j, data.get(j + 1));
                data.set(j + 1, temp);

            }
        }
    }
}

• 병합 정렬

//병합 정렬 알고리즘
private static ArrayList<Integer>newData;

private static void mergeSort(ArrayList<Integer> data, int size){
partition(0, size-1);//전체 데이터를 2개로 나누고 병합 정렬 수행
}

private static void partition(int left, int right){
    if (left < right) {
        int mid = (left + right) / 2;//전체 데이터를 2개로 나누기 위해 중간 값을 선정
partition(left, mid);//앞 부분을 다시 2개로 나눈다. (재귀호출로 나눌 수 없을 때까지 나눈다.)
partition(mid + 1, right);//뒷 부분을 다시 2개로 나눈다. (재귀호출로 나눌 수 없을 때까지 나눈다.)
merge(left, right);//정렬
}
}

private static void merge(int left, int right){
newData= new ArrayList<Integer>(data);//복사의 개념이 아니고 크기를 같게 만들기위함.

    //절반짜리 arr을 newData에 복사
for (int i = left; i <= right; i++) {
newData.add(data.get(i));
    }

    int mid = (left + right) / 2;

    int tempLeft = left;
    int tempRight = mid+1;
    int curIndex = left;

//newData를 순환하여 왼쪽 절반과 오른쪽 절반 비교해서 더 작은 값을 data에 복사
while (tempLeft <= mid && tempRight <= right) {// left와 right를 비교해서 순서를 바꿔주는 작업
if (newData.get(tempLeft) <=newData.get(tempRight)) {
data.set(curIndex++,newData.get(tempLeft++));
        } else {
data.set(curIndex++,newData.get(tempRight++));
        }
    }

//왼쪽 절반에 남은 원소들을 원래 배열에 복사
int remain = mid - tempLeft;
    for (int i = 0; i <= remain; i++) {// newData에 있는 앞자리 값을 원본 데이터 data에 복사해 넣는 작업
data.set(curIndex + i,newData.get(tempLeft + i));
    }
}

• 퀵 정렬

//퀵 정렬 알고리즘
private static void quickSort(ArrayList<Integer> data, int size){
quick(0, size - 1);
}

private static void quick(int left, int right) {
    if (left < right) {
        int p =partitionQuick(left, right);//피봇 값의 최종 위치 확정

quick(left, p-1);//피봇 기준 왼쪽 다시 정렬
quick(p+1, right);//피봇 기준 오른쪽 다시 정렬
}
}

private static int partitionQuick(int left, int right){
    int pivot =data.get(right);//맨 마지막 값을 피봇으로 선정
int i = left - 1;

    for(int j = left; j <= right - 1; j++){// right-1은 피벗을 제외한 마지막 값의 위치
if(data.get(j) <= pivot) {//배열 순회하며 피봇이랑 같거나 작은 값 탐방
i++;// i인덱스 위치와 교체
Swap(data, i, j);
        }
    }
// partition구분 종료 후 pivot의 값을 최종 위치(i+1)값과 교체
Swap(data, i+1, right);
    return i + 1;
}

private static void Swap(ArrayList<Integer> data, int a, int b){
    int temp = data.get(a);
    data.set(a, data.get(b));
    data.set(b, temp);
}

 

자습

• 탐색(search)
  • 상태공간 안에서 시작 상태(초기 상태)에서 목표 상태까지의 경로를 찾는 것
• 상태공간(state space)
  • 상태들이 모여있는 공간
• 연산자
  • 다음 상태를 생성하는 것

 

탐색 트리

• 연산자를 적용하기 전까지 탐색 트리는 미리 만들어져 있지 않다. 현재 상태에 연산자를 가할 때마다 새롭게 생성 된다. (동적 생성)
• 상태 = 노드(node)
• 초기 상태 = 루트 노트(root node)
• 연산자 = 간선(edge)
• 확장이 끝난 노드(닫혀있는 노드)
• 열려있는 노드(생성되었지만 아직 확장되지 않은 노드)
• 아직 생성되지 않은 노드

 

기본적인 탐색 기법

• 탐색 알고리즘
  • 맹목적인 탐색
    • 깊이 우선 탐색
    • 너비 우선 탐색
    • 균일 비용 탐색
  • 경험적인 탐색
    • 탐욕적인 탐색
    • A* 탐색
• 맹목적인 탐색(blind search method)
  • 목표 노드에 대한 정보를 이용하지 않고 기계적인 순서로 노드를 확장하는 방법
  • 매우 소모적인 탐색이다.
• 경험적인 탐색(heuristic search method)
  • 목표 노드에 대한 경험적인 정보를 사용하는 방법
  • 효율적인 탐색이다.
  • 경험적인 정보는 휴리스틱(heuristic)이라고 한다.
• 탐색에서는 중복된 상태를 막기 위하여 2개의 리스트를 사용
  • OPEN 리스트
    • 확장은 되었으나 아직 탐색하지 않은 상태들이 들어있는 리스트
  • CLOSED 리스트
    • 탐색이 끝난 상태들이 들어 있는 리스트
• b, d, m
  • b: 탐색 트리의 최대 분기 계수
  • d: 목표 노드의 깊이(정답의 깊이)
  • m: 트리의 최대 깊이

 

탐색 성능

• 완결성(completeness)
  • 반드시 해답을 찾을 수 있는지의 여부
• 최적성(optimality)
  • 가장 비용이 낮은 해답을 찾을 수 있는지의 여부
• 시간 복잡도(time complexity)
  • 해답을 찾는데 걸리는 시간
• 공간 복잡도(space complexity)
  • 탐색을 수행하는데 필요한 메모리 양

 

깊이 우선 탐색

• 깊이 우선 탐색(depth-first search, DFS)
  • 탐색 트리에서 해가 존재할 가능성이 존재하는 한 앞으로 계속 전진하여 탐색하는 방법
  • 시간 복잡도: O(b의 m제곱), b는 분기 계수 및 m은 트리의 최대 깊이
  • 공간 복잡도: O(bm)

 

너비 우선 탐색

• 너비 우선 탐색(breadth-first search, BFS)
  • 루트 노드의 모든 자식 노드 들을 탐색한 후에 해가 발견되지 않으면 한 레벨 내려가서 동일한 방법으로 탐색을 계속하는 방법

 

경험적인 탐색 방법

• 경험적인 탐색 방법(heuristic search method) 혹은 휴리스틱 탐색 방법
  • 문제 영역에 대한 정보나 지식을 사용하는 탐색 방법
  • 이때 사용되는 정보는 휴리스틱 정보(heuristic information)라고 한다.
• 언덕 등반 기법
  • 평가 함수의 값이 좋은 노드를 먼저 처리하는 기법
  • 평가 함수는 제 위치에 있지 않은 타일의 개수 사용
  • 언덕 등반 기법 알고리즘
    1. 현재 위치를 기준으로 각 방향의 높이 판단 (노드의 확장)
    2. 모든 위치가 현 위치보다 낮다면 그 곳을 정상이라고 판단 (목표 상태인지 확인)
    3. 현 위치가 정상이 아니라면 확인된 위치 중 가장 높은 곳으로 이동 (후계 노드의 선택)

 

 

오늘의 실습 코드

https://github.com/yubin-im/SeSAC/tree/be725ed88d0b101bfc08348cca8df1cfd40baf77/20230822/test/sort