각 정렬의 특징 및 장단점 & 시간복잡도 + 코드

선택정렬 (Selection Sort)

선택정렬은 앞에서부터 차례대로 먼저 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행하는 정렬 방법이다. 코드가 직관적이기에 구현도 비교적 간단하다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하며 정렬을 위한 비교 횟수는 많으나 교환 횟수는 상당히 적다는 것이 장점이다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있다. 선택 정렬이 가장 적합한 자료 상태는 역순 정렬이다. 즉, 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 최적의 효율을 보여준다. 반대로 이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 되는 때에는 최악의 처리 속도를 보여준다는 단점도 있다.

예시)

선택 정렬은 배열 내의 기준이 되는 수(A[0]) 와 나머지의 수를 비교하여 오름차순일 경우 낮은 수, 내림차순일 경우 높은 수를 앞으로 보내는 방식이다.

첫 번째 FOR문

첫번째 for문에서 기준값 [0]번째 Index의값과 나머지 값을 비교하여 가장 낮은수를 앞으로 보내준다.(오름차순 기준)

두 번째 FOR문

그 다음부터는 기준값을 [0]번째 Index에서 [1]번째 Index값으로 바꿔준 뒤 [0]번째에 있는 수를 제외한 나머지 숫자와 다시 비교를 한다. 이 작업을 정렬이 완료될 때까지 반복하는 것이 선택 정렬이다.

 

#define num 20
	
int number[num] = {15,3,23,64,77,46,42,174,68,78,91,5,76,310,84,342,176,120,33,41};
int temp;
for(int i = 0 ; i < num-1 ; i ++) {
    for(int j = i+1 ; j < num ; j ++) {
        if(number[i] < number[j]) {
            temp = number[j];
            number[j] = number[i];
            number[i] = temp;
       }
    }
}
         
for(int i = 0 ; i <  num ; i ++) {
      printf("[%d]",number[i]);
}

버블정렬 (Bubble Sort)

버블정렬은 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식을 말하며 코드가 간단하므로 구현이 간편하다. 정렬을 하는 방식이 물속에서 물위로 올라오는 물방울 모양과 같다하여 버블정렬이라고 한다. n개의 원소에 대하여 n개의 메모리를 사용한다. 데이터를 하나씩 비교할 수 있어서 정밀하게 비교가 가능하나 비교횟수가 많아지므로 성능면에서는 좋은 방법이 아니다. 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소를 마지막 자리로 정렬하는 식으로 정렬이 된다. 

예시)

버블정렬은 배열내의 두개의 인접한 Index를 비교하여 더 큰 숫자를 뒤로 보내 차곡차곡 쌓아 정렬하는 방법이다 즉 배열의 뒷쪽부터 정렬.

 

① for문에서 [0]번째 Index와 [1]번째의 Index값을 비교하여 더 큰 숫자를 뒤로 보내준다.

② for문에서도 마찬가지로 [1]번째 [2]번째의 Index값을 비교하여 더 큰 숫자를 뒤로 보내주는 식으로 ④번처럼 배열의 끝까지 정렬을 다 했으면 다시 배열의 처음으로 돌아와 정렬이 완료될때까지 반복하는것이 버블 정렬이다.

 

#define num 20

int number[num] {11,234,23,4,1,5,6,2,65,764,825,46,72,47,26,69,793,25,498,245};
int temp;
for(int i = 0 ; i < num ; i ++) {
     for(int j = 0 ; j < num -i -1 ; j ++) {
                if(number[j]>number[j+1]) {
                    temp = number[j];
                    number[j] = number[j+1];
                    number[j+1] = temp;
         }
    }
}
         
for(int i = 0 ; i < 20 ; i ++) {
     printf("[%d]",number[i]);
}

삽입정렬 (Insertion Sort)

버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해서 고안된 방법이 삽입정렬이다. 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방법이다. 버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 삽입정렬은 기본적으로 버블정렬의 비교횟수를 줄이고 크기가 적은 데이터 집합을 정렬하는 루팅을 작성할 시 버블정렬보다 탁월한 성능 효율을 보여준다. 정렬된 값은 한번도 교환이 일어나지 않고 N-1의 비교만 일어난다.

예시)

삽입정렬은 기준이 되는 숫자와 그 앞에있는 숫자를 비교하여 조건에 맞게 정렬을 하는 방법이다.

0번째 인덱스는 앞쪽에있는 숫자가 없기 때문에 정렬의 시작은 1번째 인덱스로 시작을 다. 

 

#define num 7
char number[num]  = {'C','A','D','G','F','E','B'};
for (int i = 1; i < num; i++) {
    int target = number[i];  // 기준
    int cur = i - 1;   // 비교할 대상
    while (cur >= 0 && target < number[cur]) {
        // 비교대상이 큰 경우 오른쪽으로 밀어냄
        number[cur + 1] = number[cur];   
        cur--;
    }
    number[cur + 1] = target;  // 기준값 저장
}

for (int i = 0; i < num; i++) {
    printf("[%c]",number[i]);
}

합병 정렬 (Merge Sort)

작은 단위로 잘게 쪼개어 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합해가면서 정렬하는 방식이다. 알고리즘 중에 가장 간단하고 쉽게 떠올릴 수 있는 방법이며 안정성이 있여 상당히 좋은 성능을 나타낸다. 하나 큰 결점이 있다면 공간이 많이 필요하다는 점이다. 정렬을 하기 위해서는 데이터 전체 크기만한 메모리가 더 필요하다.

예시)

①분할과정

먼저 정렬할 숫자들을 원소단위로 분할한다.

②병합과정

그런 뒤 분할한 원소들을 합치면서 정렬한다.

 

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

void merge(int low, int mid, int high);
void mergeSort(int low, int high);
void printArr(int a[], int n);
void copyArray(int start, int end);

//배열크기
#define number 100000
// 빈 배열 
static int mergeArr1[number];
// 정렬되지 않은 배열 
static int mergeArr2[number];

// 합병정렬함수 
void mergeSort(int low, int high) {
    int mid;
    if(low < high) {
        mid = (low + high)/2;
        mergeSort(low, mid);
        mergeSort(mid+1, high);
        merge(low, mid, high);
	}
}

void merge(int low, int mid, int high) {

    int i = low;
    int j = mid+1;
    int k = low;

    while (i<=mid && j<=high) {
        if(mergeArr2[i] < mergeArr2[j]) {
           mergeArr1[k++] = mergeArr2[i++];
        } else if(mergeArr2[i] >= mergeArr2[j]) {
           mergeArr1[k++] = mergeArr2[j++];
        }
    }
    // 남은 영역 조사후 mergedArr으로 복사

    if(i>=mid) {
        while(j<=high) {
           mergeArr1[k++] = mergeArr2[j++];
        }
    }

    if(j>=high) {
        while(i<=mid) {
           mergeArr1[k++] = mergeArr2[i++];
        }
    }
    copyArray(low, high);
}

// 배열 출력 함수 
void printArr(int a[], int n) {
     int i;
     for (i=0; i<n; i++) {
        printf("%d ", a[i]);
     }
     printf("\n");
}

void copyArray(int start, int end) {
    int i;
    for (i=start; i<=end; i++) {
        mergeArr2[i] = mergeArr1[i];
    }
}

int main(int argc, char *argv[]) {

    int i,n;
	 
    printf("몇개의 숫자로 정렬하시겠습니까?\n");
    scanf("%d",&n);

    for(i = 0 ; i < n ; i++)
	mergeArr2[i]=rand()%1000;
  
    printf("정렬전 배열 : ");
    printArr(mergeArr2,n);

    mergeSort(0, n-1);

    printf("정렬후 배열 : ");
    printArr(mergeArr2,n); 

    system("PAUSE");

    return 0;
}

퀵 정렬 (Quick Sort)

연속적인 분할에 의한 정렬방식이다. 처음 하나의 축(Pivot)을 먼저 정하여 이 축의 값보다 작은 값은 왼쪽에 큰 값은 오른쪽으로 위치시킨뒤 왼쪽과 오른쪽의 수 들은 다시 각각의 축으로 나누어져 축값이 1이 될 때까지 정렬한다. 가장 많이 사용되는 정렬법이나 안정성이 떨어진다는 단점이 있다. 

 

☞ 먼저 PIVOT을 정한다. 대부분 정렬속도를 위하여 가운데 숫자를 PIVOT으로 정하는게 효율적이다.

 

☞ PVIOT값과 LEFT값을 비교하여 LEFT값이 PIVOT보다 크다면 PIVOT값과 RIGHT값을 비교한다.

RIGHT값이 PIVOT보다 크다면 RIGHT커서를 왼쪽으로 이동시킨후 다시 PIVOT값과 비교한다.

 

☞ RIGHT값이 PIVOT보다 작다면 LEFT값과 RIGHT값을 바꾼 뒤 LEFT값을 오른쪽으로 한칸 옮긴다.

 

☞ LEFT값과 RIGHT값이 만날때까지 무한 반복한다.

 

☞ LEFT커서와 RIGHT커서가 만나면 해당값과 PIVOT값을 비교한다. PIVOT값이 크면 오른쪽에 위치시키고 PIVOT값보다 작으면 왼쪽에 위치시킨다.

 

☞ 이전 PIVOT을 기준으로 이전PIVOT보다 작은값과 큰값으로 나누고 이전 PIVOT값보다 작은값을 기준으로 새로운 PIVOT을 설정한다.

 

☞ 다시 앞에서 한 방식으로 PIVOT을 기준으로 LEFT값과 RIGHT값을 교환한다.

 

☞ 정렬이 완료된다.

 

#include <stdio.h>
#include <stdlib.h> //랜덤함수 호출

void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (low <= right && pivot >= arr[low]) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
        while (high >= (left+1)  && pivot <= arr[high]) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
    }
    Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
void QuickSort(int arr[], int left, int right)
{
    if (left <= right)
    {
        int pivot = Partition(arr, left, right); // 둘로 나누어서
        QuickSort(arr, left, pivot - 1); // 왼쪽 영역을 정렬한다.
        QuickSort(arr, pivot + 1, right); // 오른쪽 영역을 정렬한다.
    }
}
 
//메인함수
int main()
{
    int n,i;
    int arr[100];

	
    printf("몇개의 숫자로 정렬하시겠습니까?\n");
    scanf("%d",&n);

    for(i = 0 ; i < n ; i++)
        arr[i]=rand()%1000;

    printf("정렬전 배열 :");
    for(i = 0 ; i < n ; i++)
        printf("%d ", arr[i]);
    printf("\n");

    QuickSort(arr,0,n-1);

    printf("정렬후 배열 :");
    for(i = 0 ; i < n ; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

힙정렬 (Heap Sort)

힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘이다. 처음에는 나무 아래에서 위로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꾼다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려간다. 시간복잡도가 O(nlogn)인 정렬 알고리즘 중에서는 부가적인 메모리가 전혀 필요없다는 게 큰 장점인 정렬 방식이다.

쉘 정렬 (Shell Sort)

삽입정렬의 개념을 확대하여 일반화한 정렬 방법이다. 알고리즘이 간단하여 프로그램으로 쉽게 구현할 수 있다. 수행 능력도 삽입 정렬보다 우수한 것으로 평가한다. 멀리 있는 레코드들끼리 비교 및 교환될 수 있으므로, 어떤 데이터가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블정렬 방식의 단점을 해결할 수 있다.

기수 정렬(Radix Sort)

데이터의 비교를 통한 정렬이 아닌 분산 정렬을 이용한 정렬 방법이며 자릿수가 있는 데이터(정수, 문자열 등)에만 사용 가능하다. 각 자리수를 기준으로 점차 정렬을 진행한다.

정렬 별 장단점 비교

정렬 별 시간복잡도, 공간복잡도 비교

 

 

[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도 (tistory.com)