[자료구조] Sorting

Sorting36

---

이번 포스트에서는 선택 정렬, 삽입 정렬, 병합 정렬 및 빠른 정렬과 같은 몇 가지 중요한 정렬 알고리즘을 소개한다.

선택 정렬과 삽입 정렬의 두 가지 알고리즘에 중점을 둘 것이다.

Quadratic Sorting Algorithms

2차 정렬 알고리즘

선택정렬

각 값 i(n-1에서 1까지)에 대해 다음을 수행

• data[0]에서 data[i]까지 가장 큰 원소를 찾는다.
• Swap it with data[i].

c++ 코드

void  selectionSort(int data[ ], size_t n)  {
  size_t  i, j, index_of_largest ;
  int  largest ;

  if (n==0) return  ;
  for ( i = n-1; i >0 ; --i)  {
    largest = data[0] ;
    index_of_largest = 0 ;
    // 가장 큰 index 찾기 아래 코드
    swap(data[i], data[index_of_largest]) ;  
  } 	
}

// 가장 큰 index 찾기 코드

for (j=1; j<=i ; ++j)   {
  if (data[j] > largest)  {
    largest = data[j] ;
    index_of_largest = j ;
  }
}

선택정렬 : 분석

얼마나 많은 비교 작업을 수행해야 할까?

삽입정렬

각 값 i(1에서 n-1까지)에 대해 다음을 수행

• data[i]에 대해 0과 i-1 사이에서 적절한 인덱스 j를 찾는다.
• 인덱스 j에서 i-1까지 각 데이터를 오른쪽으로 한 셀 이동한 후 data[i]를 해당 위치에 복사한다.

c++코드

void  insertionSort(int data[ ], size_t n)  {
  size_t  i, j;
  int  next ;

  if (n==0) return  ;
  for ( i = 1; i  < n ; ++i)  {
    next = data[i] ;
    j = i ;
    /* 다음의 삽입 인덱스 j 찾기 */
    data[j] = next  ;  
  } 	
}

//다음 삽입 인덱스 j 찾기 함수
while (j >0 && next < data[j-1]){
  data[j] = data[j-1] ;
  --j ;
}

삽입정렬 : 분석

얼마나 많은 비교 작업을 수행해야 할까?