C언어 :: 버블정렬과 선택정렬 알고리즘 & 구현 소스

버블정렬과 선택정렬은 정렬되지 않은 배열을 정렬하는 가장 기초적이면서 방법이다.

→버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다.

[그림 8-1] 정렬되지 않은 데이터

① 가장 작은 데이터인 1을 가장 앞에 위치한 15와 교환한다. 가장 작은 데이터가 가장 앞에 위치하게 된다.

② 첫 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 3을 두 번째 데이터인 11과 교환한다.

③ 첫 번째, 두 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 8을 세 번째 데이터인 15와 교환한다.

④ 첫 번째, 두 번째, 세 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 11을 네 번째 데이터인 11과 교환한다. 같은 데이터이므로 위치의 변화는 없다.

⑤ 데이터들에 대한 정렬이 완료된다.

 

[네이버 지식백과] 버블 정렬 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))

내가짜본

버블정렬 소스(c언어)

→선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. 

[그림 8-3] 정렬되지 않은 데이터

① 첫 번째 데이터인 15와 두 번째 데이터인 11을 비교해 큰 데이터를 뒤로 위치시킨다. 15가 크므로 둘의 위치를 바꾼다.

② 두 번째 데이터인 15와 세 번째 데이터인 1을 비교하는데, 앞에 위치한 15가 크므로 둘의 위치를 바꾼다.

③ 마찬가지 방식을 적용해 세 번째 데이터인 15와 네 번째 데이터인 3의 위치를 바꾼다.

④ 마찬가지 방식을 적용해 네 번째 데이터인 15와 마지막 데이터인 8의 위치를 바꾼다. 가장 큰 데이터인 15가 가장 뒤에 위치하게 된다.

⑤ 처음부터 다시 시작한다. 첫 번째 데이터인 11과 두 번째 데이터인 1의 크기를 비교하는데 앞에 위치한 11이 크므로 둘의 위치를 바꾼다.

⑥ 마찬가지 방식을 적용해 두 번째 데이터인 11과 세 번째 데이터인 3의 위치를 바꾼다.

⑦ 마찬가지 방식을 적용해 세 번째 데이터인 11과 네 번째 데이터인 8의 위치를 바꾼다. 두 번째로 큰 데이터인 11이 뒤에서 두 번째에 위치하게 된다.

⑧ 처음부터 다시 시작한다. 첫 번째 데이터인 1과 두 번째 데이터인 3의 크기를 비교하는데 앞에 위치한 1이 작으므로 그대로 둔다.

⑨ 두 번째 데이터인 3과 세 번째 데이터인 8의 크기를 비교하는데, 앞에 위치한 3이 작으므로 그대로 둔다. 세 번째로 큰 데이터인 8이 뒤에서 세 번째에 위치하게 된다.

⑩ 처음부터 다시 시작한다. 첫 번째 데이터인 1과 두 번째 데이터인 3의 크기를 비교하는데, 앞에 위치한 1이 작으므로 그대로 둔다. 데이터들에 대한 정렬이 완료된다.

 

[네이버 지식백과] 선택 정렬 (컴퓨터 개론, 2013.3.10, 한빛아카데미(주))

내가짜본

선택정렬 소스(C언어)

두 정렬방법의 공통점과 차이점

-공통점 : 배열을 정렬하는 기초적인 방법으로 효과적이지 못하다.

-차이점 : 버블정렬은 인접한데이터 끼리 서로 비교를 통해 서로 데이터를 바꾸어 비효율적이지만 그에비에 선택정렬은 가장 작은 값을 먼저 찾은다음 서로 데이터를 바꾸어 비교적 효율적이다.