Sorting Algorithm   정렬 알고리즘

(2018-10-04)

Selection Sort, 선택 정렬

1. 정렬 알고리즘 (Sorting Algorithm)

  ㅇ 정렬 : 수많은 자료를 특정 목적에 맞게 순서있게 재배열하는 것
      - 탐색의 효율성, 이론 설명, 실용성 등을 위해서도 정렬 알고리즘이 필요함

  ※ 100개 이상의 정렬 알고리즘이 개발되어 왔음


2. 정렬 알고리즘 주요 종류

  ㅇ 선택 정렬 (Selection Sort)
     - 특징 : 가장 큰/가장 작은 자료를 선택하는 과정을 반복적으로 수행
     - 정렬 방법
        . 처음과 나머지 자료들과 비교하면서, 제일 큰/작은 자료를 맨 왼쪽에 두며, 위치 교환
        . 다음과 나머지 자료들과 비교,위치 교환을 반복해가며 정렬해나감
     - 기본 연산 둘 : 비교 연산, 교환 연산
     - 비교 필요 횟수 : 총 n(n-1)/2회의 데이터 비교가 필요함
        . 설사 정렬되어 있더라도, 총 n(n-1)/2회의 데이터 비교가 필요함
     - 시간복잡도 : O(n2)
        . 데이터량이 적을때는 좋은 성능을 보임
     
Input  : 정렬 전 Data[], int n
Output : 정렬 후 Data[]

void SelectionSort(int Data[], int n) 
{
    int i, j, min;
    for (i=0; i < n-1; i++) 
    {
        min = i;
        for (j=min+1; j < n; j++)
            if (Data[j] < Data[min])  min = j;
        if (min != i)
            swap(&Data[i],&Data[min]);
    }
}
ㅇ 교환 정렬 (Exchange Sort) - 정렬 방법 . 가장 큰 또는 가장 작은 자료를 선택하는 과정을 반복적으로 수행 .. 첫째 루프에서 가장 작은 수가 첫째 자리에 들어가고, .. 둘째 루프에서 둘째 자리에 그 다음 수가 들어가는 식으로 반복 정렬됨
Input  : int n, unsorted_array Data[1,...,n]
Output : sorted_array Data[1,...,n]

void exchange (int n, array Data[]) {
   int i,j ;
   for (i = 1 ; i <= n-1 ; i++)
      for (j = i+1 ; j <= n ; j++)
         if (Data[j] < Data[i])
            exchange Data[i] and Data[j] ;
}
ㅇ 삽입 정렬 (Insertion Sort) - 특징 . 크기가 작은 정렬 문제에 효율적 - 정렬 방법 . 원래 배열 첫 원소부터 뽑아서, 적절한 위치에 삽입하면서 반복 수행 . for 루프 마다, .. Data[1,..,j-1]은 정렬된 배열이 되고, .. Data[j+1,...,n]은 아직 미정렬 배열이 됨
Input  : 정렬 전 Data[], int n
Output : 정렬 후 Data[]

void insertionSort (Data[],n) {
   int i,j,key ;
   for j = 2 to n
      key = Data[j] ;
      i = j - 1 ;
      while ( i > 0 and Data[i] > key )
         Data[i+1] = Data[i] ;
         i = i - 1 ;
      Data[i+1] = key ;
}
ㅇ 버블 정렬 (Bubble Sort) ㅇ 퀵 정렬 (Quick Sort)


[알고리즘 종류] 1. 알고리즘 분류 2. 탐색 알고리즘 3. 정렬 알고리즘 4. 그래프 알고리즘 5. 해쉬 알고리즘 6. 해싱 탐색 7. 최대 최소 구하기 8. 유클리드 알고리즘

 
        최근수정     요약목록(시험중)     참고문헌