이미 정렬된 두 자료를 병합하는 것을 일반화 하여 정렬하는 알고리즘

자료 배열에 접근하는 방법이 순차적이어서 자료를 차례대로 읽어가며 비교를 하며

다른 메모리를 정렬에 이용한다.

1. 병합 병렬할 size = 1

2. size가 자료크기 N보다 작을 때 size의 크기로 배열을 분할하여 두 분할씩 차례로 병합

3. size = size * 2,   2번으로..

장점 : N logN의 성능을 가진다. 빠르다.

단점 : 추가적인 메모리로 정렬 할 배열과 똑같은 크기의 배열이 필요하다.

void Merge_Sort( int arr[], int len )

{

int i, j, k, first, second, size;

int *b;

b = (int*)malloc(sizeof(int)*len );

for( size = 1 ; size < len ; size *= 2 )

{

first =- 2*size;

second = first + size;

while( second + size*2 < len )

{

first = second + size;

second = first + size;

i = first;

j = second;

k = first;

while( i < first + size || ( j < second + size&& j < len ) )

{

if( arr[i] <= arr[j] )

{

if( i < first + size )

b[k++] = arr[i++];

else

b[k++] = arr[j++];

}

else

{

if( j < second + size && j < len )

b[k++] = arr[j++];

else

b[k++] = arr[i++];

}

}

}

for( i = 0 ; i < len ; i++ )

arr[i] = b[i];

}

free(b);

}

이미 정렬된 자료인 경우 : 삽입, 거품, 퀵

자료가 섞여 있는 경우 : NlogN의 성능을 가지는 정렬방법들

반쯤 정렬된 경우 : 퀵, 쉘, 병합

역순으로 정렬된 자료 : 개선된 퀵, 쉘, 병합, 힙(최악 : 선택,삽입,거품)

추가적인 메모리 소요가 필요한 정렬 : 기수, 병합

우선순위 큐의 일종으로 우선 순위가 높은 요소를 효율적으로 선택 할 수 있는 자료구조.

힙을 트리를 이용하여 구현하며 트리는 배열로 구현.

힙 : 우선순위가 키 값의 크기에 정해지는 우선순위 큐. 어떤 키가 다른 특정한 두 키보다 큰 값을

가져야 한다는 조건이 만족해야 함( 트리구조 )

Upheap : 새로 삽입된 노드가 힙의 규칙에 맞게 지위가 상승하는 작동

Downheap : 힙의 상단을 차지하던 노드가 힙의 규칙에 맞게 지위에 떨어뜨리는 동작

힙 삽입, 추출시 위 동작들을 이용하여 힙을 완성 시킨다.

가장 널리 사용되는 정렬 방법중 하나.

연속적인 분할을 해서 정렬하는 방법으로 자료 값 중 Pivot값을 하나 정하여

왼쪽은 작은 값, 오른쪽은 큰값을 배치한다.

나누어진 왼쪽,오른쪽을 다시 분할하여 위 방법으로 정렬하는 방법

재귀의 깊이가 log2N이 되어 가장 빠른 성능을 나타낸다

난수에 대한 정렬에서 빠르다

하지만 정렬이 되거나 역순으로 배열된 자료에 대해선 느리다. 추가 메모리가 필요하다.

1. 배열에서 Pivot값을 하난 정한다.(보통 맨 마지막 값)

2. 배열의 왼쪽과 오른쪽에서 각각 탐색을 시작한다.

3. 왼쪽에서 Pivot보다 큰값, 오른쪽에서 Pivot보다 작은값이 나오면 둘을 교환한다.

4. 왼쪽에서 탐색하던 것이 오른쪽 보다 커지면 탐색을 종료한다.

5. Pivot값을 왼쪽과 오른쪽 탐색의 교차지점과 교환한다.

6. Pivot에서 왼쪽, 오른쪽 부분을 위와 같은 방법으로 다시 정렬 한다

7. 각 정렬되는 부분의 길이가 1보다 작거나같으면 정렬을 종료한다.

     left    right       pivot

3 5 2 1 4     3        1            4

3 5 2 1 4    5        1                4        : left롸 right 교환

3 1 2 5 4        1        5            4

3 1 2 5 4        2        5            4

3 1 2 5 4        5           5        4

3 1 2 4 5                                3      : pivot값을 중심으로 변경

3 1 2 4 5         3        1            2

1 3 2 4 5        1        3               2    : left와 right 교환

1 3 2 4 5        3        3            2

1 2 3 4 5           1                    2       : pivot값을 중감으로 변경

#include <stdio.h>

void Print_Arr( int arr[], int size )

{

for( int i = 0 ; i < size ; i++ )

{

printf("%d", arr[i] );

if( i < size ) printf(" ");

else printf("\n");

}

printf("\n");

}

void Quick_Sort( int arr[], int size )

{

int Pivot, temp;

int i, j;

if( size > 1 )

{

Pivot = arr[size-1];

i = -1;

j = size - 1;

while( 1 )

{

while( arr[++i] < Pivot );

while( arr[--j] > Pivot );

if( i >= j ) break;

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

temp = arr[i];

arr[i] = arr[size-1];

arr[size-1] = temp;

Quick_Sort( arr, i );

Quick_Sort( arr+i+1, size-i-1 );

}

}

void main()

{

int arr[20] = {5,1,4,0,100,.................};

Print_Arr( arr, 20 );

Quick_Sort( arr, 20 );

Print_Arr( arr, 20 );

}

인접한 자료를 비교하면서 정렬하는것으로 결국은 최대값이 맨 뒤로 가면서 정렬됨.

속도가 좋지 않다.. 그냥 이런방법도 있다는거만 알아두자

1. 배열 처음부터 인접한 정렬을 비교하여 교환

2. 인접한 배열을 순서대로 비교

3. 최대값들이 정렬되는 배열 뒷부분을 제외하고 반복.

4. 배열의 수 만큼 과정이 반복되면 정렬 끝

void bubble_sort( int arr[], int size )

{

int i, j, temp;

for( i = 0 ; i < size - 1 ; i ++ )

{

for( j = 0 ; j < size - 1 ; j ++ )

{

if( arr[j-1] > arr[j] )

{

temp = arr[j-1];

arr[j-1] = arr[j];

arr[j] = temp;

}

}

}

}

가장 간단한 정렬, 정렬 할 숫자들에서 가장 작은 수를 선택하고 그 수를 앞쪽으로 배치하는 것을

숫차들의 수 만큼 반복하여 정렬하는 방법

데이터가 작을때 정말 효율이 좋다.

하지만 데이터가 많을수록 속도가 현저히 떨어진다.

1. 주어진 배열에서 가장 작은 값을 찾는다.

2. 가장 작은 값을 배열의 처음과 교환한다.

3. 배열에 앞에 배치된 최소값을 이후부터 1, 2 과정을 반복한다.

4. 배열의 수 만큼 과정이 반복되었으면 정렬을 완료하고 끝낸다.

#include <stdio.h>

void Print_Arr( int arr[], int size )

{

for( int i = 0 ; i < size ; i ++ )

{

printf("%d", arr[i] );

if( i < size ) printf(" ");

else printf("\n");

}

printf("\n");

}

void Selection_Sort( int arr[], int size )

{

int Min;

int Min_Index;

int i, j;

for( i = 0 ; i < size - 1 ; i++ )

{

Min_Index = i;

Min = arr[i];

for( j = i + 1 ; j < size ; j++ )

{

if( Min > arr[j] )

{

Min = arr[j];

Min_Index = j;

}

}

arr[Min_Index] = arr[i];

arr[i] = Min;

}

}

void main()

{

int arr[20] = {8,2,12,55,28,39,40,46,100,......};

Print_Arr( arr, 20 );

Selection_Sort( arr, 20 );

Print_Arr( arr, 20 );

}

일정한 간격을 기준으로 같은 위치에 있는 원소들끼리 묶음을 만들어서

묶음끼리 삽입정렬을 수행하고 간격 K가 1이 될때까지 정렬을 시행하는 것

간격 K=1일땐 일반 삽입정렬과 똑같은 알고리즘을 수행 하지만

간격을 줄여가면 이미 어느정도 정렬이 되어있기 때문에 원래의 삽입정렬보다 효과적이다.

쉘 정렬이 선택,버블,삽입에 비해 훨씬 빠르다.

ex)

44, 33, 22, | 11, 55, 66, | 88, 99, 100, | 111, 222

간격 K = 3 인 경우

묶음 1 : 44, 11, 88, 111

묶음 2 : 33, 55, 99, 222

묶음 3 : 22, 66, 100

#include <stdio.h>

void Print_Arr( int arr[], int size )

{

for( int i = 0 ; i < size ; i++ )

{

if( i < size ) printf(" ");

else printf("\n");

}

printf("\n");

}

void Shell_Sort( int arr[], int size );

void main()

{

}

void Shell_Sort( int arr[], int size )

{

int i, j, k;

int i_Interval, i_MaxInterval = 1;

int temp;

while( i_MaxInterval * 3 + 1 > size )                

{

i_MaxInterval = i_MaxInterval * 3 + 1;        // interval 은 n= 3*n+1이 가장빠르다는 연구 결과가 있단다.

}

for( i_Interval = i_MaxInterval ; i_Interval > 0 ; i_Interval /= 3 )

{

for( i = 0 ; i < i_Interval ; i++ )

{

for( j = i + i_Interval ; j < size ; j+= i_Interval )

{

temp = arr[j];

k = j;

while( k > i_Interval - 1 && temp < arr[k-i_Interval] )

{

arr[k] = arr[k-i_Interval];

k -= i_Interval;

}

arr[k] = temp;

}

}

}

}

삽입정렬은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아낸뒤 다시 적당한 곳에

삽입하는 알고리즘 이다.

탐색하는 데이터의 정렬된 앞 부분을 비교해서 자신의 위치에 맞는 곳에 삽입 된다.

평균 소요 시간이 O(n*n)

최악은 역순으로 정렬된 상태.

선택이나 버블에 비해 다소 빠르다.

#include <stdio.h>

void Print_Arr( int arr[] );

void Insert_Sort( int arr[], int size );

void main()

{

int arr[10] = {8,2,12,55,28,39,40,46,100,77};

Print_Arr( arr );

Insert_Sort( arr, 10 );

Print_Arr(arr);

}

void Print_Arr( int arr[] )

{

for( int i = 0 ; i < 10 ; i++ )

{

printf("%d", arr[i] );

if( i < 10 ) printf(" ");

else printf("\n");

}

printf("\n");

}

void Insert_Sort( int arr[], int size )

{

int i, j, key;

for( i = 1 ; i < size ; i++ )

{

key = arr[i];

for( j = i-1 ; j >= 0 ; j-- )

{

if( arr[j] > key ) arr[j+1] = arr[j];

else break;

}

arr[j+1] = key;

}

}

데이터량이 적을 때 주기억장치 내에서 정렬 하는 기법

특징 : 속도가 빠르다

1. 내부 정렬

2. 외부 정렬