08-01 버블 정렬(Sorting)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

1.정렬(Sorting)

 1)정의

 -기준에 따라 데이터를 순서대로 체계적으로 정리하는 알고리즘.

 -정렬의 목적은 데이터의 탐색을 용이하기 위한 목적이 있다.

 

2.버블 정렬(Bubble Sorting)

 1)정의

  -자료구조를 순회하면서 서로 인접한 두 가지 데이터를 검사하여 정렬하는 알고리즘.

 2)오름차순 정렬

 

  -위의 그림의 자료구조에서 왼쪽 데이터부터 시작하는 오름차순으로 정렬하려고 할 때

   5과 1는 서로 인접한 데이터이다.

  -5과 1을 검사했을 때 5가 1보다 크므로 오름차순을 기준으로 5는 오른쪽으로 이동하게 된다.

  -이와 같은 방법으로 두 개씩 데이터를 검사하여 수 차례 반복한다.

  -한 차례 자료구조를 순회했지만 6만이 자료구조의 마지막 데이터로 제대로 된 위치에 이동했다.

  -그러므로 마지막 데이터를 제외한 나머지 데이터를 다시 버블 정렬을 시행하고 그 작업을

 정렬이 완료될 때까지 반복한다.

3)버블 정렬성능 측정

 -위의 그림에서 6개의 데이터로 된 자료구조를  처음 버블 정렬을 해서 데이터를 검사한 횟수는 5이다.

 

 -다시 정렬을 시행 했을 때 검사 횟수는 4. 이 과정을 일반화하면 하나의 식이 완성된다.

 

 -n개가 데이터의 개수를 의미한다.

 -위의 자료에서 데이터의 개수는 6개이고 위의 식으로 계산하면 15개라는 버블 정렬의 비교횟수가 나온다.

 -버블정렬이 검사 및 순회하는 횟수가 정렬의 성능에 직결된다.

 -적은 개수의 데이터에는 성능 상 문제가 되지 않지만

 -수백 수천의 개수의 데이터에 사용하기에는 문제가 있다.

 

3.버블 정렬 예제

-버블 정렬 함수

-테스트