15 일차

정렬과 탐색

∙ 정렬 (sort)

- 주어진 데이터를 정해진 기준에 따라 순서를 재배열하는 작업

- 가장 기본적이고 중요한 알고리즘 중의 하나

 

∙ 다양한 정렬 알고리즘 (sorting algorithm)

1. 알고리즘 단순 & 시간 복잡도가 느리고, 비효율적

- 버블 정렬(bubble sort)

- 선택 정렬(selection sort)

- 삽입 정렬(insertion sort)

2. 알고리즘 복잡 & 대용량 데이터에 대해서 빠르게 동작, 효율적

- 쉘 정렬(shell sort)

- 병합 정렬(merge sort)

- 퀵 정렬(quick sort)

- 힙 정렬(heap sort)

- 기수 정렬(radix sort)

 

∙ 정렬 알고리즘의 평가 척도

- 비교 횟수 & 이동 횟수

- 모든 경우에 최적인 정렬 알고리즘은 없음 -> 응용에 맞게 선택

 

∙ 정렬 알고리즘의 안정성

- 안정된(stable) 정렬 : 같은 값을 갖는 원소의 순서가 정렬 후에도 유지됨

- 안정되지 않은 정렬 : 같은 값을 갖는 원소의 순서가 정렬 후에도 보장되지 않음

 

∙ 버블 정렬 (bubble sort)

- 정렬되지 않은 부분에서 인접한 두 원소의 크기를 비교하여 교환하는 작업을 반복

void buble_sort(int data[], int n)
{
	for (int i = 0 ; i < n - 1; i++){
    	// data[n-1]부터 data[i]까지 이동하면서
        for (int j = n -1; j > i; j--){
        	// 인접한 두 원소를 비교 & 교환
        	if (data[j] < data[j-1])
            	swap(data[j], data[j-1]);
        }
    }
}

- for 반복문 내부 문장의 실행 횟수? => O(n^2)

 

∙ 선택 정렬 (selection sort)

- 정렬되지 않은 원소들 중에서 최솟값 원소를 찾아 맨 왼쪽 원소와 교환

void selection_sort(int data[], int n)
{
	for (int i = 0; i < n -1; i++){
    	int idx = i;
    	// data[i], data[i+1],...data[n-1]에 대해
        for (int j = i + 1; j < n; j++){
        	// 최소값을 갖는 인덱스을 알아낸 후
        	if (data[j] < data[idx])
            	idx = j;
        // data[i]와 data[idx]를 교환	
        swap(data[i], data[idx]);
        }
    }
}

- 시간복잡도 => O(n^2)

 

 

∙ 삽입 정렬 (insertion sort)

- 정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분의 알맞은 위치에 삽입하는 과정을 반복

void insertion_sort(int data[], int n)
{
	for (int i = 1; i < n; i++){
    	// data[i]를 임시 변수(key)에 복사한 후
    	int key = data[i];
        int j = i - 1;
        // data[i-1]부터 data[0]까지 차례로 검사하면서
        while (j >= 0 && data[j] > key){
        	data[j+1] = data[j];
            j--;
        }
        // key를 삽입하기에 적절한 위치를 찾을 때까지
        // 각각의 원소 값을 오른쪽 원소로 복사하고
        // 적절한 위치에 key값을 삽입(복사)
        data[j+1] = key;
}

 

 

∙ 전체 소스코드

#include <iostream>
#include <algorithm>

using namespace std;

void buble_sort(int data[], int n)
{
    for (int i = 0 ; i < n - 1; i++){
        // data[n-1]부터 data[i]까지 이동하면서
        for (int j = n -1; j > i; j--){
            // 인접한 두 원소를 비교 & 교환
            if (data[j] < data[j-1])
                swap(data[j], data[j-1]);
        }
    }
}

void selection_sort(int data[], int n)
{
    for (int i = 0; i < n -1; i++){
        int idx = i;
        // data[i], data[i+1],...data[n-1]에 대해
        for (int j = i + 1; j < n; j++){
            // 최소값을 갖는 인덱스을 알아낸 후
            if (data[j] < data[idx])
                idx = j;
        // data[i]와 data[idx]를 교환
        swap(data[i], data[idx]);
        }
    }
}

void insertion_sort(int data[], int n)
{
    for (int i = 1; i < n; i++){
        // data[i]를 임시 변수(key)에 복사한 후
        int key = data[i];
        int j = i - 1;
        // data[i-1]부터 data[0]까지 차례로 검사하면서
        while (j >= 0 && data[j] > key){
            data[j+1] = data[j];
            j--;
        }
        // key를 삽입하기에 적절한 위치를 찾을 때까지
        // 각각의 원소 값을 오른쪽 원소로 복사하고
        // 적절한 위치에 key값을 삽입(복사)
        data[j+1] = key;
    }
    
}

int main()
{
    int data[] = {4, 2, 3, 5, 1};
    //buble_sort(data, 5);
    //selection_sort(data, 5);
    insertion_sort(data, 5);
    for (auto n : data){
        cout << n << ", ";
    }
    cout << endl;
}