[알고리즘] 버블정렬(Bubble sort), 선택정렬(Selection Sort), 삽입정렬(Insertion Sort), 퀵 정렬(Quick Sort)

버블정렬(Bubble sort)에 대해 설명하고 예제소스를 구현해보아라

• 오름차순으로 정렬한다.
• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 
• 구현은 간단하지만 비효율적이다.
• 시간 복잡도 : O(n^2)

void bubble_sort(int list[], int n)
{
    int temp;
    for (int i = n - 1; i > 0; i--) {
        // 0 ~ (i-1)까지 반복
        for (int j = 0; j < i; j++) {
            // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
            if (list[j] < list[j + 1]) {
                temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
}

---

선택정렬(Selection Sort)에 대해 설명하시고 예제소스를 구현해보아라

• 오름차순으로 정렬한다.
• 원소를 넣을 위치를 정해두고 어떤 원소를 넣을지 선택하는 알고리즘
• 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫번째에 놓고, 두번째 자료를 세번재 자료부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두번재에 놓고 ... 이러한 과정을 반복하여 정렬을 수행한다.
• 구현은 간단하지만 비효율적이다.
• 시간 복잡도 : O(n^2)

void selectionSort(int arr[], int size) {
    int minIndex;
    int temp;
    for (int i = 0; i < size - 1; i++) {

        minIndex = i;
        
        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

---

삽입정렬(Insertion Sort)에 대해 설명하시오 예제소스를 구현해보아라

• 오름차순으로 정렬한다.
• 삽입 정렬은 두번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
• 즉, 두번째 자료는 첫번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입 될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한칸 씩 뒤로 이동시킨다.
• 처음 Key값은 두 번재 자료부터 시작한다.
• 시간복잡도 : O(n^2)

void insertion_sort(int arr[], int size)
{
    int i, j;
    int key;

    for (i = 1; i < size; i++)
    {
        key = arr[i];
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] < key) break;
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = key;
    }
}

---

퀵 정렬(Quick Sort)에 대해 설명하시고 예제소스를 구현해보아라

• 오름차순을 기준으로 정렬한다.
• 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot)이라고 한다. 피벗을 기준으로 피벗보다 작은 요소들은 왼쪽으로, 피벗보다 큰 요소들은 오른쪽으로 옮겨진다. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 이 과정을 더 이상 분할이 불가능할 때까지 반복한다.
• 다른 정렬 알고리즘에 비해 속도가 빠르므로 사용빈도가 높다.
• 시간복잡도 : 평균 O(nlogn) 최악 O(n^2)

void swap(int *arr,int a, int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}
 
void quick_sort(int *arr, int start, int end)
{
    int pivot = arr[start];
    int left = start+1;
    int right = end;
 
    while(left <= right)
    {
 
        while(arr[left] < pivot)  { left++; }  //pivot보다 작은 경우는 건너뛰고 크거나 같은경우 멈춤
        while(arr[right] > pivot) { right--; } //pivot보다 큰 경우는 건너뛰고 작거나 같은경우 멈춤
 
        if(left <= right){ swap(arr, left, right); }
    }
 
    //1개로 쪼개질때 까지
    if(start < end)
    { 
        swap(arr, start, right);  	   //pivot값과 arr[right] 값 swap
 
        myQuickSort(arr, start, right-1);  //앞 부분
        myQuickSort(arr, right+1, end);    //뒷 부분
    }
 
    return;
}

 

 

[출처 및 참고 사이트]

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

https://blockdmask.tistory.com/177