정렬

정렬

정렬이란 사용자가 원하는 순서대로 원소들을 배치하는 것이다. 정렬을 할 수 있는 자료구조에는 배열, 리스트, 그래프가 있다. 정렬은 종류에 따라 속도의 차이가 있다. 아래의 영상을 보면 각각의 정렬 알고리즘들이 정렬을 하는데 걸리는 속도를 한눈에 볼 수 있다.

@동영상

오늘 우리는 속도가 N^2인 정렬 알고리즘을 공부할 것이다.

먼저 버블정렬을 살펴보자. 버블정렬은 인접한 두 원소를 비교해 나가면서 가장 큰 원소를 뒤로보내는 정렬은 해나가는 정렬이다. 이 때 작업을 n-1번 반복하는데 이유는 n-1번째에는 n번째 역시 정렬되있기 때문이다.

xxxxxxxxxx
void BubbleSort(int* arr, int size){
        int i, j;
        int temp;
        for( i = 0 ; i < size -2 ; i++){
                for(j = i ; j < size-1 ; j++){
                        if(arr[j] > arr[j+1]){
                                temp = arr[j];
                                arr[j] = arr[j+1];
                                arr[j+1] = temp;
                        }
                }
        }
}

선택정렬은 버블정렬을 개선한 정렬이다. 버블정렬에서는 모든 원소를 밀어내면서 정렬했지만, 선택정렬은 가장 큰 값을 찾아 맨 뒤 원소와 교체한다. 따라서 매번 스왑을 해주는 버블정렬보다 근소하게 빠르다.

xxxxxxxxxx
void Sellection(int* arr, int size){
        int i, j;
        int temp;
        int m;
        for( i = 0 ; i < size - 1 ; i++){
                m = i;
                for( j = i ; j < size ; j++){
                        if(arr[j] < arr[m]){
                                m = j;
                        }
                }
                temp = arr[i];
                arr[i] = arr[m];
                arr[m] = temp;
        }
}

삽입정렬은 새로운 배열을 만들어 원소 하나씩 정렬해 가면서 삽입해 나간다고 생각하면 된다.

xxxxxxxxxx
void insertSort(int* arr, int size){
        int i, j;
        int m;
        for( i = 1 ; i < size; i++ ){
                m = arr[i];
                for(j = i-1 ; j >= 0 ; j--){
                        arr[j+1] = arr[j];
                        if(m > arr[j+1]){
                                break;
                        }
                }
                arr[j+1] = m;
        }
}