[알고리즘] ep1-2) 버블정렬, 선택정렬, 삽입정렬

컴퓨터에서 정렬을 수행하는 이유 중 가장 큰 이유가 바로 이진 탐색이 가능한 데이터를 만들기 위해서이다
이진탐색의 시간복잡도: O(log(n))
 
 
 
ㅇ제자리(in-place): 추가적인 메모리 공간을 거의 사용하지 않고, 주어진 데이터 구조 내에서만 작업을 수행하는 것
일반적으로 어떤 정렬 알고리즘이 정렬 대상 개체를 위해 필요한 메모리에 추가하여 오직 상수 메모리만을 사용한다면, 해당 정렬 알고리즘이 제자리(in-place)에서 수행한다고 얘기한다
 
장점

• 메모리 효율성: 추가적인 메모리 공간을 거의 사용하지 않으므로 메모리 효율성이 높다
• 캐시 효율성: 메모리 내에서 직접 데이터 이동이 이루어지기 때문에 캐시 효율성이 높다

단점

• 복잡한 구현: 일부 복잡한 알고리즘의 경우 제자리 알고리즘으로 구현하기 어려울 수 있다
• 비효율적인 시간 복잡도: 일부 제자리 알고리즘은 시간 복잡도 측면에서 비효율적일 수 있다

 
ㅁstable vs unstable
ㅇstable: 정렬 후 동일한 값의 요소들이 입력 순서와 같은 상대적 순서를 유지하는 성질
e.g. 버블정렬, 삽입정렬, 병합정렬
ㅇunstable: 정렬 후 동일한 값의 요소들의 상대적 순서를 유지하지 않는 성질
e.g. 선택정렬, 힙정렬, 퀵정렬
 
 
 
 
ㅇ버블정렬(bubble sort): 인접하는 2개의 원소를 비교해 정렬하는 방식
"제자리 + stable" O(n^2)
 
(코드)

void bubbleSort(int* arr, int n) {
    int temp;
    for (int i = 0; i < n - 1; i++) {
    	// 마지막 i개의 요소는 이미 정렬되어 있으므로 제외
        for (int j = 0; j < n - i - 1; j++) { 
            if (arr[j] > arr[j + 1]) { // 오름차순
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

성능이 좋지 않아 실무에서는 거의 사용하지 않는다
 
 
 
ㅇ선택정렬(selection sort): 배열을 순차적으로 탐색하여 가장 작은(또는 가장 큰) 원소를 찾아 첫 번째 원소와 교환하는 방식으로 정렬하는 방식
"제자리 + unstable" O(n^2)

 
(코드)

void selectionSort(int* arr, int n) {
    int temp, minIdx;
    for (int i = 0; i < n - 1; i++) {
    	// 최소값의 인덱스를 찾는 과정
        minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[minIdx] > arr[j]) { // 오름차순
                minIdx = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

 
 
 
ㅇ삽입정렬(insertion sort): 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 요소를 하나씩 꺼내서 정렬된 부분에 삽입하는 방식
"제자리 + stable" O(n^2)

"소확행" 이라 생각하자

 
(코드)

void insertionSort(int* arr, int n) {
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        // 오른쪽으로 한 칸씩 땡긴다 (소확행 작업)
        while (arr[j] > key && j >= 0) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 삽입할 공간에 key값을 넣는다
        arr[j + 1] = key;
    }
}

 
 
 
 
 
 
 
 
 
출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan)