정렬 알고리즘 1부 - 선택,버블,삽입, 쉘 정렬

선택정렬

선택정렬은 정렬 방법 중에 가장 간단한 방법 중의 하나다. 기본적인 방법은 제일 처음에 있는 키를 가지고 나머지

키와 비교하여 제일 작은 키값을 가지는 데이터와 위치를 바꾼다. 다음에는 두 번째 위치한 데이터의 키를 가지고 세 번째

이후의 데이터가 가지고 있는 키와 비교하여 마찬가지로 제일 작은 키값을 가지는 데이터와 위치를 바꾼다..

이렇게 해서 맨 마지막 바로 전 데이터와 마지막 데이터를 비교하는 순서까지 반복하면 데이터가 오름차순으로 

정렬된다!

void selectionSort(int Keys[], int n){
 int i,Min;
 for(i=0; i < n-1; i++){
    Min = i;
    for(j = i+1; j < n; j++){
        if(&keys[j] < & keys[Min]){
            Min = j;
        }
    }
    swap(&keys[i], &keys[Min]);
 }
}

선택 정렬은 2가지의 기본 연산으로 이뤄지는데 먼저 최솟값을 찾기 위한 비교 연산을 사용하고 두 번째로는 찾은 값과 비교한 대상의

위치를 교환하여 주는 교환 연상을 사용한다.

선택 정렬은 주어진 배열 안에서 자료들의 이동을 최소화하려는 목적으로 만들어진 목적에 맞게 자료의 양이 적을 때 아주 좋은 

성능을 나타낸다. 시간 복잡도는 O(n²)이다. 구현하기 쉬운 알고리즘 중 하나 인 것 같다. 

버블 정렬

버블 정렬은 주어진 데이터에서 2개의 인접한 데이터를 비교하여 오름차순이면 작은 데이터를, 왼쪽으로 내림차순이면 큰 데이터를 

오른쪽으로 위치시키면서 마지막 데이터까지 반복하는 것을 순차적으로 진행하여 정렬하는 방법을 말합니다..

선택 정렬과 같이 구현하기 쉽고 이해하기 쉽습니다.

void bubbleSort(int Keys[], int n){
 int i, j;
 for(i=n-1; i >= 1; i--){
    for(j=0; j<i; j++)
        if(&keys[j]<keys[j+1){
            swap(&keys[j], &keys[j+1]);
 
}
 

버블 정렬의 평균 비교 횟수는 O(n²) 입니다. 버블정렬은 수행 속도가 느리므로 잘 사용하지 않고 안전성은 유사하지만 성능이

아주 미흡하고 최솟값부터 찾아나가는 선택 정렬과 반대로 최댓값을 찾는 작업을 수행하고 대충 정렬하는 것을 동시에

반복 수행하므로 수행시간이 길어지는 단점이 있습니다.

삽입 정렬

삽입 정렬은 매우 간단한 방법으로 적은 양의 데이터를 처리하는 데 매우 유용합니다. 가장 먼저 첫 번째 데이터와 두 번째 데이터를 

비교하여 오름차순으로 정렬한다. 이렇게 정렬한 2개의 데이터를 하나의 서브파일로 간주하고 이것과 세 번째 데이터를 비교 하여

오름차순 정렬이 되도록 알맞은 위치에 세 번째 데이터를 삽입 시킵니다.. 이러한 방법으로 마지막 데이터까지 반복합니다.

void insertionSort(int Keys[], int n){
 int i, j, addKey;
 for(i=1; i < n; i++){
    addKey = keys[i]
    j=i;
    while(keys[j-1]>addKey){
        keys[i] = keys[j-1];
        j=j-1;
    }
        keys[j] = addKey;
  }
}

삽입 정렬의 수행시간은 O(n²)이다.

삽입 정렬은 메모리 사용공간이 별도의 기억공간을 필요로 하지 않기 때문에 리스트의 크기 만큼의 기억공간이 있으면 된다. 

또한 간단하고 안정적이며 적은 비교와 많은 교환이 필요한 작은 레코드 배열에 가장 유리합니다.. 순서가 틀린 레코드의

순서가 전체 레코드 수에 비해 현저하게 적은 경우 효율적이므로 원시 리스트가 부분적으로 정렬되어 있는 경우에 효과적

입니다.. 하지만 매회 서브파일의 크기가 증가하는 단점이 있습니다..

쉘 정렬

쉘 정렬은 삽입 정렬의 확장 개념으로 생각하면 쉽습니다. 먼저 입력 파일 안에 있는 데이터를 적당한 매개변수를 기준으로

그 값만큼 떨어진 데이터들을 하나의 서브파일로 간주하여 그렇게 해서 만들어진 각각의 서브파일에서 삽입 정렬의 방법을

이용하여 데이터를 정렬하게 됩니다. 이후 매개변수의 값을 적당하게 줄여나가면서 위의 방법을 반복하다가 매개변수의 값이

1이 될 때까지 반복하면 됩니다.

쉘 정렬에서 발생하는 비교 횟수는 정렬 간격이 수행속도를 좌우하는 특징이 있습니다. 매개변수는 근사적으로 소수이어야 

한다고 알려져 있는데, 이러한 경우의 알고리즘 수행시간은(O(n(logn)^2)입니다. 최악의 경우에는 O(n^2)의 수행시간 이죠.

쉘 정렬을 구현할 때에는 정렬 간격을 배열에 저장하여 사용하며, 쉘 정렬은 퀵 정렬 다음으로 수행속도가 빠르고

안정적입니다.