[알고리즘 이론] 정렬 알고리즘

정렬 알고리즘이란?

배열 등의 데이터 단위를 사용자에 맞춰 순서대로 배치 시켜주는 알고리즘.

 

 

선택 정렬 

이름과 같이 현제 위치에 들어갈 값을 찾은 후, 정렬하는 알고리즘입니다. 

시간 복잡도의 경우 O(n^2)입니다.

출처-위키피디아

1. 배열의 크기 만큼 반복문문을 돌려준다. 
2. 현제 위치부터 배열의 크기만큼 반복문을 다시 돌려준다. 
3. 가장 작은 값을 찾고, 해당 값을 해당 위치와 스왑한다. 
4. 2로 돌아간다. 

int i,j;
int aLength;

for (i = 0; i < aLength-1; i++)
{
    int jMin = i;
    for (j = i+1; j < aLength; j++)
    {
        if (a[j] < a[jMin])
            jMin = j;
    }

    if (jMin != i) 
        swap(&a[i], &a[jMin]);
}

 

 

버블 정렬 

현제 인덱스의 값과 뒤 인덱스 값을 비교한 후, 큰 값을 뒤로 보내며 정렬하는 알고리즘입니다.

시간복잡도는 O(n^2)입니다.

출처-위키피디아

 

1. 배열 전체를 반복문을 돌려준다. 
2. (배열 크기 - 현 인덱스)값만큼 반복분 돌려준다. 
3. 현 인덱스와 인덱스+1의 값을 비교하여 앞 값이 더 높다면 스왑한다. 
4. 2로 돌아간다. 

vector<int> bubble_sort(vector<int> target) 
{
	int n = target.size();
	int temp;
	for (int i = 0; i < n - 1; i++) 
    {
		for (int j = 0; j < n - i - 1; j++) 
        {
			if (target[j] > target[j + 1]) 
            {
				temp = target[j];
				target[j] = target[j + 1];
				target[j + 1] = temp;
			}
		}
	}
	return target;
}

 

 

삽입 정렬 

인덱스를 점점 높혀가며, 들어갈 위치를 정해 넣어 정렬 알고리즘입니다. 

시간복잡도는 O(n^2)입니다.

출처 - 위키피디아

 

1. 배열의 인덱스 1부터 전체를 반복문 돌려줍니다. 
2. 현제값을 저장합니다.
3. 전 인덱스의 값과 비교하여 더 작다면 전 값을 현제 인덱스로 보냅니다. 
4. 3를 반복합니다. 
5. 적절한 위치에 값을 넣어줍니다. 
6. 2를 반복합니다.

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    remember = data[(j=i)];
    while ( --j >= 0 && remember < data[j] ){
        data[j+1] = data[j];
    }
    data[j+1] = remember;
  }
}

 

 

병합 정렬

배열을 균등한 크기로 분할하고, 분할된 부분을 정렬한 후 다시 분할한 배열을 합치는 형태의 배열 알고리즘 입니다.

시간복잡도는 O(n log n)입니다. 

출처 - 위키피디아

 

1. 리스트를 절반으로 나눕니다. 
2. 분할된 리스트를 각각 정렬합니다. 
3. 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 병합합니다.

void BottomUpMergeSort(A[], B[], n)
{
    for (width = 1; width < n; width = 2 * width)
    {
        for (i = 0; i < n; i = i + 2 * width)
            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        CopyArray(B, A, n);
    }
}

void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    for (k = iLeft; k < iEnd; k++) {
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(B[], A[], n)
{
    for(i = 0; i < n; i++)
        A[i] = B[i];
}

 

 

 

퀵 정렬

하나의 키 값을 가지고 큰 값과 작은 값을 나누며 정렬하는 알고리즘입니다. 

시간복잡도는 O(n log n)입니다.

출처 - 위키피디아

 

1. 리스트에서 하나의 요소를 피벗으로 선택
2. 피벗을 기반으로 두 개의 리스트로 구분
3. 피벗을 제외한 두 개의 부분 리스트에 대해 재귀적으로 퀵 정렬 수행
4. 재귀 호출이 완료된 후, 피벗과 두 부분 리스트를 합쳐서 최종적으로 정렬된 리스트를 만든다. 

#include <algorithm>

void quickSort(int A[], int low, int high) {
    if(low >= high) return; 

    int i = low, j = low;
    int&pivot = A[high];
    for (; j < high; ++j) {
        if ( A[j] < pivot)
            swap(A[i++], A[j]);
    }
    swap(A[i], pivot);

    quickSort(A, low, i-1);
    quickSort(A, i+1, high);
}