5장 정렬

계모가 3만명의 학생 정보를 주며 17,213등이 누구냐고 알아보라고 함, 텍스트 에디터와 C컴파일러 쓸 수 있게 해줌, 동점자는 없다고함(착하다...) 오늘 못 알아오면 맴매 맞는다고함(못됐다...)

• 콩쥐의 해결책: 정렬 알고리즘

  정렬의 목적 : 찾으려고 하는 것을 쉽게 찾고자 하는데 있음(탐색을 쉽게 하려고)

• 버블 정렬

  버블 정렬을 소개합니다

  버블 정렬은 알고리즘이 데이터를 정렬하는 과정이 마치 물 속 깊으느 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름

  버블 정렬(Bubble Sort)은 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행

  

  

  

  

  

  

  

  

  

  

  6뽀글뽀글 위로 올라오고 뒤로 가면서 완료됨, 6을 제외하고 나머지에 대해 위의 내용을 반복

  버블 정렬은 얼마나 빠를까요?

  버블 정렬은 데이터 집합을 한번 순회할 때마다 정렬해야 하는 데이터 집합의 범위가 하나씩 줄어들므로, 데이터 집합의 범위를 n개라고 한다면 n-1만큼 반복하면 정렬이 마무리 된다. 한번의 반복에서 데이터의 탐색과 교환도 n-1번만큼 이루어진다.

  예제는 5 + 4 + 3 + 2 + 1 = 15 번 반복하게 된다.

  • 버블 정렬의 비교 횟수

    = (n-1)+(n-2)+...+(n-(n-2))+(n-(n-1))

    = (n-1)+(n-2)+...+3+2+1

    

    

  콩쥐가 버블정렬로 3만개 데이터를 연산하려면 약 4억5천만번 반복해야됨 ㅋㅋㅋㅋ

  거품을 내는 코드를 작성해 봅시다

  • 예제 BubbleSort.c

#include <stdio.h>     void bubbleSort(int dataSet[], int length) { int i = 0; int j = 0; int temp = 0;     // n-1만큼 반복 for( i = 0 ; i < length-1; i++ ) { // n-(i+1) = 1씩 줄어듬 for( j = 0 ; j < length-(i+1); j++ ) { if( dataSet[j] > dataSet[j+1] ) { temp = dataSet[j+1]; dataSet[j+1] = dataSet[j]; dataSet[j] = temp; } } } }     void main() { int dataSet[] = { 6,4,2,3,1,5 }; int length = sizeof(dataSet)/sizeof(dataSet[0]); int i = 0;     bubbleSort(dataSet, length);     for( i = 0 ; i < length ; i++ ) { printf("%d ", dataSet[i]); } printf("\n"); }

• 삽입 정렬

  삽입 정렬은 무엇인가요?

  삽입 정렬(Insertion Sort)은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘

  삽입 정렬의 과정은 다음과 같다

  • 데이터 집합에서 정렬 대상이 되는 요소들을 선택한다. 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 늘어날 때마다 1개씩 커진다. 정렬 대상의 최대 범위는 '데이터 집합의 크기-1'이 된다.
  • 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인한다, 그렇지 않다면 이 요소를 정렬 대상에서 뽑아내고 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다. 여기서 적절한 곳이라 함은, 데이터 집합의 가장 왼쪽을 기준으로 했을 때 자신보다 더 작은 요소가 없는 위치를 말한다.
  • 뽑아 든 요소를 삽입할 적절한 곳을 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한 자리씩 오른쪽으로 이동시키고, 새로 생긴 빈자리에 삽입한다.
  • 전체 데이터 집합이 정렬이 완료될 때까지 1~3을 반복한다.

  

  

  

  

  

  

  

  

  삽입 정렬은 버블 정렬보다 빠를까요?

  예제에서 정렬을 위한 반복은 5회 수행 된다 그리고 데이터 집합 내 요소들간의 비교는 정렬 대상의 범위가 2개 일 때 한 번, 3개일 때 2번, 4개일 때 3번... 6개일 때 5번 수행된다.

  • 삽입 정렬의 비교 횟수

    

  

  삽입 정렬 예제

  • 예제 insertSort

#include <stdio.h> #include <string.h>     void insertSort(int dataSet[], int length) { int i = 0; int j = 0; int value = 0;     for( i = 1; i < length ; i++ ) { if( dataSet[i-1] < dataSet[i] ) continue;     value = dataSet[i];     for( j = 0 ; j < i ; j++ ) { if( dataSet[j] > value ) { memmove(&dataSet[j+1], &dataSet[j], sizeof(dataSet[0]) * (i-j)); dataSet[j] = value; break; } } } }     void main() { int dataSet[] = { 6,4,2,3,1,5 }; int length = sizeof(dataSet)/sizeof(dataSet[0]); int i = 0;     insertSort(dataSet, length);     for( i = 0 ; i < length ; i++ ) { printf("%d ", dataSet[i]); } printf("\n"); }

• 퀵 정렬

  빠른 정렬, 퀵 정렬

  퀵 정렬(Quick Sort)은 '분할 정복(Divide and Conquer)'에 기반한 알고리즘이다.

  퀵 정렬은 다음과 같은 과정으로 분할 정복을 이용해 정렬을 수행한다.

  • 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값은 오른편에 위치 시킨다.
  • 기준 요소 왼편에는 기준 요소보다 작은 요소들이 모여 있고 오른편에는 큰 요소들이 모이게 된다. 이렇게 나눈 데이터 집합들을 다시 1에서와 같이 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할한다.
  • 1과 2의 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게 된다.

  

  

  

  

  

  

  

  

  

  

  

  

  퀵 정렬이 퀵 정렬을 호출합니다

  • 데이터 검색, 교환

    하나의 변수는 왼쪽부터 오른쪽 방향으로 데이터 집합을 검사하면서 기준보다 큰 요소를 찾고, 또 다른 하나의 변수는 오른쪽부터 왼쪽 방향으로 검사하면서 기준보다 작은 요소를 찾는다. 그리고 이 두 변수가 찾아낸 두 요소를 교환한다. 그리고 변수들은 서로 만날 때까지 검사를 계속 진행하면서 교환해야 될 요소를 찾아내고 교환을 수행한다. 두 변수가 같은 위치에서 만나면 기준 요소를 왼쪽 데이터의 집합의 마지막 요소와 교환하면 된다.

    

    

    

    

    

  • 반복되는 분할 과정

    재귀 호출(Recursive Call)을 이용하여 반복되는 분할 과정을 처리

    void QuickSort(int dataSet[], int left, int right)

    {

    if( left < right )

    {

    int index = partition(dataSet, left, right);

       

    QuickSort(dataSet, left, index-1);

    QuickSort(dataSet, index+1, right);

    }

    }

  • 예제 QuickSort.c

#include <stdio.h>     void swap(int* a, int *b) { int temp = *a; *a = *b; *b = temp; }     int partition(int dataSet[], int left, int right) { int first = left; int pivot = dataSet[first];     ++left;     while( left <= right ) { while( dataSet[left] <= pivot ) ++left;     while( dataSet[right] > pivot ) --right;     if( left < right ) --right;     if( left < right ) swap( &dataSet[left], &dataSet[right] ); else break; }     swap(&dataSet[first], &dataSet[right]);     return right; }     void quickSort(int dataSet[], int left, int right) { if( left < right ) { int index = partition(dataSet, left, right);     quickSort(dataSet, left, index-1); quickSort(dataSet, index+1, right); } }     void main() { int dataSet[] = { 6,4,2,3,1,5 }; int length = sizeof(dataSet)/sizeof(dataSet[0]); int i = 0;     quickSort(dataSet, 0, length-1);     for( i = 0 ; i < length ; i++ ) { printf("%d ", dataSet[i]); } printf("\n"); }

quickSort()함수는 데이터 집합인 dataSet배열과 dataSet 내에ㅔ서의 정렬 대상 범위 값인 left, right를 매개 변수로 받는다. quickSort()함수는 left가 right보다 크거나 같으면 이 둘이 만났다느느 뜻이므로 실행을 종료한다. 반대로 left가 right보다 작으면 내부 코드 블록으로 들어가서 partition()함수를 실행한 후에 자기 자신, 즉 quickSort()를 재귀 호출한다. 42행의 quickSort()호출은 partition() 함수에 의해 나누어진 왼쪽 데이터 집합을 43행의 호출은 오른쪽 데이터 집합을 정렬 대상으로 삼아 정렬을 수행한다.

partition()함수는 정렬 대상의 첫 번째 요소를 기준 요소(pivot)로 지정하고 while루프를 통해 분할을 수행한다. 이 루프 안에 있는 두 개의 루프는 left와 right의 위치를 옮긴다. 19행의 루프는 dataSet의 왼쪽에서 출발해서 pivot보다 큰 요소를 찾을 때까지 탐색을 하며 left를 1씩 증가시킨다. 그러다가 pivot보다 큰 요소를 찾으면 left에 그 요소가 위치한 인덱스를 저장하고 종료한다. 그리고 22행의 루프는 dataSet의 오른쪽에서 출발해서 pivot보다 작은 요소를 찾아 그 요소의 위치를 right에 저장한다.

그리고 left와 right를 25행에서 비교한 후 left가 right보다 찾은 요소들을 교환한다. 만약 left가 right보다 크거나 같다면 서로 만났다는 뜻이니 루프ㅡ를 종료한다.

분할 작업이 끝나면 31행에서 기준 요소와 분할에 의해 새로 생긴 왼쪽 데이터 집합의 오른쪽 끝에 있는 요소를 교환한다. 그 후에 마지막으로 기준 요소의 새 위치를 반환한다.

quickSort() 함수는 partition() 함수가 반환한 새로운 기준 요소의 위치를 이용해서 42행에서 왼쪽 데이터 집합의 범위를, 43행에서 오른쪽 데이터 집합의 범위를 결정한다.

퀵 정렬은 빠릅니다!

• 퀵 정렬 알고리즘 성능 분석

  퀵정렬의 재귀 호출 깊이

  데이터 집합을 나누기 위해 필요한 비교 횟수

• 최선의 경우

  퀵 정렬은 데이터 집합이 어떻게 정렬되어 있는지가 성능을 좌지우지한다. 데이터가 미리 정렬되어 있거나 역순으로 정렬되어 있는 경우에 최악의 성능을 보인다. 하지만 데이터 요소들이 이리저리 흩어져 있는 경우 최고의 성능이 나온다.

  

  퀵 정렬의 재귀 호출 깊이

  32개의 조각으로 나누려면 다섯 번의 재귀 호출이 필요하다.

  

  최선의 경우 데이터 비교 횟수

  = 재귀 호출의 깊이 * 각 재귀 호출 단계에서의 비교 횟수

  

• 최악의 경우

  

  최악의 경우, 다음 그림과 같이 매 재귀 호출마다 데이터 집합의 분할이 1 : n-1로 이루어진다.

  

  이렇게 되면 재귀 호출의 깊이는 n-1이 되고, 재귀 호출마다 정렬 대상의 범위도 1씩 줄어든다

• 평균의 경우

  

  

• C 표준 라이브러리 퀵 정렬 함수

  qsort() 함수를 소개합니다

  C언어의 표준 라이브러리(stdlib.h)에 퀵 정렬 알고리즘이 구현된 함수가 제공된다.

  void qsort(

  void* base, /* 데이터 집합 배열의 주소 */

  size_t num, /* 데이터 요소의 개수*/

  size_t width, /* 한 데이터 요소의 크기*/

  int( __cdecl *compare)(const void*, const void*) /* 비교 함수에 대한 포인터*/

  );

  마지막 매개 변수에 함수포인터를 가리킬 함수는 다음과 같은 원형을 가져야 한다.

  int compare((void*) &elem1, (void*) &elem2);

  compare 함수는 필요한 기능에 맞춰 구현하면 된다

  int compare( const void *_elem1, const void *_elem2)

  {

  int *elem1 = (int*)_elem1;

  int *elem2 = (int*)_elem2;

     

  if( *elem1 > *elem2 )

  return 1;

  else if( *elem1 < *elem2 )

  return -1;

  else

  return 0;

  }

  qsort() 함수를 테스트 해봅시다

  • 예제 QuickSort2.c

#include <stdlib.h> #include <stdio.h> #include <string.h>     int compareScore(const void* _elem1, const void *_elem2) { int* elem1 = (int*)_elem1; int* elem2 = (int*)_elem2;     if( *elem1 > *elem2 ) return 1; else if( *elem1 < *elem2 ) return -1; else return 0; }     void main() { int dataSet[] = { 6,4,2,3,1,5 }; int length = sizeof(dataSet)/sizeof(dataSet[0]); int i = 0;     qsort((void*)dataSet, length, sizeof(int), compareScore);     for( i = 0 ; i < length ; i++ ) { printf("%d ", dataSet[i]); } printf("\n"); }

콩쥐가 되어 보세요