[알고리즘] 정렬(삽입, 버블, 퀵)

정렬 (Sort)

• n개의 숫자가 주어졌을 때, 이를 특정한 기준(오름차순, 내림차순 등)에 맞게 정렬하여 출력하는 알고리즘

• 매우 다양한 정렬 알고리즘이 존재하고, 각 알고리즘마다 수행시간이 다르다.

삽입정렬

• k번째 원소를 1부터 k-1까지의 숫자와 비교해 적절한 위치에 끼워 넣고, 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식.

• 자료구조에 따라서 뒤로 밀어내는데 걸리는 시간이 클 수 있다.

• 그리고 역순으로 정렬되어있을 경우에 매우 오래걸린다.

• 반면에 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/삭제하는 경우에는 최고의 정렬 알고리즘이 된다.

• 구현이 매우 쉽다.

이미지 출처 - 나무위키

이진 삽입 정렬

• 이진 탐색을 활용해서 새로운 원소가 위치할 곳을 미리 찾아서 정렬하는 방식

• 원소 크기 비교하는 부분을 logN 수준으로 낮추어 조금 더 빠르게 정렬을 수행할 수 있다.

시간복잡도 & 공간복잡도

시간복잡도

• 최악의 경우 : O(n^2)

• 최선의 경우 : O(n)

공간복잡도

• O(1)

코드

#include<stdio.h>
#include<stdlib.h>

#define MAX_SIZE 100000
int main(void) {
    int list[MAX_SIZE]; int i,j,temp;
    srand((unsigned int)time(NULL));
    for (i = 0;i<MAX_SIZE;i++) list[i] = rand()%MAX_SIZE+1;
    int key;
      for(i=1; i<MAX_SIZE; i++){
        key = list[i]; 
        for(j=i-1; j>=0 && list[j]>key; j--) list[j+1] = list[j]; 
            list[j+1] = key;
      }
    return 0;
}

버블정렬

• 서로 인접한 원소를 차례로 검사해 나가면서 정렬하는 방식

  1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ... , n-1번째와 n번째를 정렬한 뒤, 다시 1번째와 2번째 ~ n-2번째와 n-1번째를 비교해나가는 방식 (최대 n(n-1)/2 번 정렬)

• 1회전 할 때 마다 마지막 한 개가 정렬되므로 원소들이 거품처럼 올라오는 것처럼 보여서 버블 정렬이다.

  1회전 마다 하나씩 정렬에서 제외됨

• 대부분의 상황에서 최악의 성능을 보여주지만, 이미 정렬된 자료에서는 한 번만 돌면 되기 때문에 최선의 성능을 보여준다.

• 가장 손쉽게 구현하여 사용할 수 있지만, 알고리즘적 관점에서는 대단히 비효율적인 방식이다.

• SWAP이 MOVE보다 더 복잡하기 때문에 거의 쓰이지 않는다.

시간복잡도 & 공간복잡도

시간복잡도

O(n^2)

공간복잡도

O(1)

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100000
int main(void){
    int list[MAX_SIZE]; 
    int i,j,temp;
    srand((unsigned int)time(NULL));
    for (i = 0;i<MAX_SIZE;i++) list[i] = rand()%MAX_SIZE+1;

    for (i=0;i<MAX_SIXE;i++){
        for (j=0;j<MAX_SIZE-i ; j++){
            if(list[j] > list[j+1]){
                //SWAP
                temp = list[j];
                list[j] = list[j+1];
                list[j+1] = temp;      
            } 
        }
    }
    return 0;
}

퀵정렬

• 'quick'이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능

• 거의 모든 언어에서 제공하는 정렬함수는 퀵 정렬 혹은 이를 변형한 알고리즘을 사용

• 적절한 원소 하나를 pivot으로 정해서, 그보다 작은 것을 앞으로 빼내고, 큰 것을 뒤로 보내서 pivot을 기준으로 작은것, 큰 것으로 나눈 뒤에 각각에서 다시 피벗을 정해서 나누어진 공간의 크기가 0이나 1이 될 때 까지 정렬한다.

• 이렇게 pivot을 잡고 작은 원소들을 왼쪽으로, 큰 원소들을 오른쪽으로 나누는 방식을 partition step이라고 하며, 이 것을 어떻게 하느냐에 따라 성능차이가 발생한다.

퀵소트 예시(출처-위키피디아)

• 두꺼운 테두리안의 5가 pivot이다. 파란색은 pivot보다 작은 수, 빨간색은 pivot보다 큰 수이다

시간복잡도 & 공간복잡도

시간복잡도

• 최악의 경우 : O(n^2)

피벗을 계속 최댓값이나 최솟값으로 잡는 경우

따라서 피벗을 랜덤으로 정하거나, 몇 개를 뽑아 중앙값으로 정하는 등의 방식을 사용하기도 한다.

공간복잡도

O(logN)

코드

#include <stdio.h>
#define MAX_SIZE 100000
#define SWAP(x,y,t) ( (t)=(x), (x)=(y), (y)=(t))

int list[MAX_SIZE];
int partition(int list[], int left, int right) { //분할 알고리즘  
    int pivot, temp, low, high;
    low = left;
    high = right + 1;
    pivot = list[left]; //제일 왼쪽원소를 pivot으로 설정 
    do {
        do low++; // 피봇 다음부터 low 
        // list[low] < pivot 일 때 low 증가  
        while (low <= right && list[low] < pivot);
        do high--; //list[right] 부터 시작 
        // list[high] > pivot일 때 high 감소  
        while (high >= left && list[high] > pivot);
        if (low < high) SWAP(list[low], list[high], temp);
    } while (low < high); 
    SWAP(list[left], list[high], temp);
    return high; //pivot index 
}
void quick_sort(int list[], int left, int right)
{
    if (left<right) {
        int q = partition(list, left, right); //pivot index
        quick_sort(list, left, q - 1); //피봇 제외하고 다시 퀵소트  
        quick_sort(list, q + 1, right);
    }
}
int main(void) {
    int i;
    srand(time(NULL));
    for (i = 0; i < MAX_SIZE; i++)
        list[i] = rand() % MAX_SIZE+1;
    quick_sort(list, 0, MAX_SIZE - 1);

    return 0;
}

참고자료

[https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98](https://namu.wiki/w/정렬 알고리즘)

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