정렬

알고리즘의 의미

: 문제를 해결하기 위한 일련의 명령이나 반복되는 절차

정렬 알고리즘

찾고자 하는 데이터를 빠르고 쉽게 찾을 수 있게 하는 것이 목적

* 버블 정렬

- 데이터 집합 내의 이웃 요소들끼리의 교환을 통해 정렬 수행

이웃 요소들끼리 비교 비교 비교.... 마지막 까지 가서 마지막 요소는 제외하고 다시 반복!!!

- 버블 정렬의 비교 횟수 : n(n-1)/2

* 삽입 정렬

- 데이터 집합을 돌면서 정렬이 필요한 요소를 뽑아내 이를 적당한 곳에 삽입해 나감

like 카드 정리 하기ㅋㅋ

비교 범위를 늘려가면서 정렬이 필요한 아이를 적당한 위치로 이동시킴

- 삽입 정렬의 비교 횟수 : n(n-1)/2

- 데이터 집합이 정렬이 되어 있으면 비교를 하지 않음!! => 평균적으로 삽입 정렬이 더 나은 성능을 보임ㅋ

+ 메모리 내용을 이동시키는 기능의 함수

   memmove(새로운 메모리 주소, 원본 데이터 주소, 이동시킬 데이터 양)

* 퀵 정렬

1. 데이터 집합 내 임의의 기준 요소를 선택

2. 무조건 기준 요소보다 작으면 기준보다 왼쪽, 크면 오른쪽으로

3. 왼쪽에 있는 데이터 집합 내에서 다시 임의의 기준 요소를 선택해 2를 반복

- 좋은 기준 요소를 선택하면 최상의 성능 발휘

- 데이터 집합의 정렬 상태에 따라 성능 좌우

- 이상적인 경우 퀵 정렬의 비교 횟수 : nlong_2n

  이상적이지 않은 경우 퀵 정렬의 비교 횟수 : n(n-1)/2

- C언어의 표준 라이브러리에 퀵 정렬 함수 제공 = >qsort()

void qsort( void *base, size_t num, size_t width, int(_cecl *compare) (const void *, const void *) );

            데이터 집합 주소/데이터 갯수/한 데이터 크기/비교 함수에 대한 포인터

출처 : 뇌를 자극하는 알고리즘 (한빛미디어)